vlambda博客
学习文章列表

前言

直接插入排序当待排序数据的顺序和期望排序结果相反时，排序效率是最差的；上次聊到的折半插入排序只是减少有序列表的比较次数，而对于整体数据遍历次数还是没有得到优化；接下来要说的希尔排序就是针对整体数据进行优化，从而提升排序效率。

正文

1.1 希尔排序算法思想

希尔排序(Shell's Sort)是直接插入排序算法的改进版，又称“缩小增量排序”（Diminishing Increment Sort）;

算法思想

将待排序数据根据指定步长进行分组，分别进行直接插入排序；减小步长，重复分组，重复直接插入排序，直到步长为1时进行最后一次插入排序。

对于第一次步长可以根据需要自定义，但一般推荐会设置为元素个数除以2(lenght/2)，后续的步长依次是上一次步长除以2(stepk=stepk-1/2)，直到步长为1，如下图：

上面说到步长可以理解为增量，而减少步长的过程，也就是缩小增量，即希尔排序又称为缩小增量排序。

分组原理(第一次分组的step1=6/2=3)：

• 第一组：0索引位的元素为2，0+step1的索引位为3，对应的元素是1，3+step1越界了，则第一组的元素为2、1；

• 第二组：1索引位的元素为5，1+step1的索引位为4，对应的元素是9，4+step1越界了，则第二组的元素为5、9；

• 第三组：2索引位的元素为6，2+step1的索引位为5，对应的元素是3，5+step1越界了，则第三组的元素为6、3；此时元素就分组完成了；

接下来的分组就依次递减步长，即上一次步长除以2取整；然后根据新算出来的步长继续将上一次的排序的结果分组即可；直到步长递减到为1时，整体进行最后一次直接插入排序为止；

1.2 希尔排序算法实现与解析

代码实现(升序)：

运行结果如下：

步骤解析：

上图步骤说明：

• 将原始数据array复制到新数组中arrayb中，这步的主要目的是后续不需要声明额外临时变量，也为了后续核心代码实现逻辑简单易懂，减少过多的判断；0索引位也充当为哨兵位；

• 第一步根据元素个数算出第一次步长step1=3，根据步长将待排序数据进行虚拟分组，索引位为1的元素和索引位为1+step的元素为一组，索引位为2的元素和索引位为2+step的元素为一组，索引位为3的元素和索引位为3+step的元素为一组；则将待排序数据分为2、1；5、9；6、3 三组；

• 第二步开始遍历每一组数据，针对每一组数据进行直接插入排序；首先是第一组数据2、1，将待排序数据1放入哨兵位(即0索引位)，哨兵位的数据1和有序列表中的2进行比较，2大于1，则需要腾出空位，所以2移到分组中索引位为4的位置；然后将哨兵位的数据1插入到腾出的空位中；

• 第三步遍历第二组数据5、9，首先将待排序数据9放入哨兵位(即0索引位)，哨兵位的数据9和有序列表中的5进行比较，5小于9，则不需改变位置；

• 第四步遍历第三组数据6、3，首先将待排序数据3放入哨兵位(即0索引位)，哨兵位的数据3和有序列表中的6进行比较，6大于3，则需要腾出空位，所以6移到分组中索引位为6的位置；然后将哨兵位的数据3插入到腾出的空位中；

• 分组排序完成之后，最终得出第一次分组排序结果：

第一次分组排序完成之后，调整步长，继续进行分组，由于第二次计算出的步长step2=step1/2=1，即将所有上一次分组的数据全部为一组进行最后一次直接插入排序即可；这里就不在重复演示了，具体步骤和之前说到的直接插入排序一样，参照这篇。

通过第二次插入排序完成之后就得到最后的排序结果啦。

1.3 希尔排序算法分析

时间复杂度

时间复杂度最坏情况和直接插入排序的时间复杂一样，都是O(n²)，但有其他大神经过大量演示，希尔排序的时间复杂度一般为O(n^(1.3~2))，比O(n²)性能好。

空间复杂度
在算法核心部分只采用了固定的几个中间变量((i,j,step,arrayb[0]))，所以算法过程中消耗的内存是一个常量，则空间复杂度为O(1)；

稳定性
由于在排序过程中是根据步长将原始数据进行分组，这样就可能会导致相同的元素分到不同组，在最终排序时就不能保证原来两个相同元素的顺序啦，所以希尔排序是不稳定的。

综上所述，希尔排序的时间复杂度为O(n²)，空间复杂度为O(1)，是不稳定算法；

总结

到这里，插入排序的三种排序介绍完毕，下期开始介绍交换排序；这里先总结一下插入排序的相关关键点(下图绿色部分)；如下：

感谢小伙伴的：点赞、收藏和评论，下期继续~~~

一个被程序搞丑的帅小伙，关注"Code综艺圈"，跟我一起学~~~