希尔排序(Shell Sort)属于插入排序的一种。它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序(Diminishing Increment Sort)。

通过一个简单的例子来理解希尔排序。👉第三趟排序:gap=2/1=1。整个数列为1组。对其进行插入排序:

总的来说,希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,小的基本在前,大的基本在后。然后缩小增量,到增量为1时,其实多数情况下只需微调即可,不会涉及过多的数据移动。