网站建设招聘信息,wordpress 多域名插件,合肥建站免费模板,wordpress标签关联前言直接插入排序当待排序数据的顺序和期望排序结果相反时#xff0c;排序效率是最差的#xff1b;上次聊到的折半插入排序只是减少有序列表的比较次数#xff0c;而对于整体数据遍历次数还是没有得到优化#xff1b;接下来要说的希尔排序就是针对整体数据进行优化#xf… 前言直接插入排序当待排序数据的顺序和期望排序结果相反时排序效率是最差的上次聊到的折半插入排序只是减少有序列表的比较次数而对于整体数据遍历次数还是没有得到优化接下来要说的希尔排序就是针对整体数据进行优化从而提升排序效率。正文1.1 希尔排序算法思想希尔排序(Shells Sort)是直接插入排序算法的改进版又称“缩小增量排序”Diminishing Increment Sort;算法思想将待排序数据根据指定步长进行分组分别进行直接插入排序减小步长重复分组重复直接插入排序直到步长为1时进行最后一次插入排序。对于第一次步长可以根据需要自定义但一般推荐会设置为元素个数除以2(lenght/2)后续的步长依次是上一次步长除以2(stepkstepk-1/2)直到步长为1如下图image-20210407235130599上面说到步长可以理解为增量而减少步长的过程也就是缩小增量即希尔排序又称为缩小增量排序。分组原理(第一次分组的step16/23)第一组0索引位的元素为20step1的索引位为3对应的元素是13step1越界了则第一组的元素为2、1第二组1索引位的元素为51step1的索引位为4对应的元素是94step1越界了则第二组的元素为5、9第三组2索引位的元素为62step1的索引位为5对应的元素是35step1越界了则第三组的元素为6、3此时元素就分组完成了接下来的分组就依次递减步长即上一次步长除以2取整然后根据新算出来的步长继续将上一次的排序的结果分组即可直到步长递减到为1时整体进行最后一次直接插入排序为止1.2 希尔排序算法实现与解析代码实现(升序)代码运行结果如下结果步骤解析步骤上图步骤说明将原始数据array复制到新数组中arrayb中这步的主要目的是后续不需要声明额外临时变量也为了后续核心代码实现逻辑简单易懂减少过多的判断0索引位也充当为哨兵位第一步根据元素个数算出第一次步长step13根据步长将待排序数据进行虚拟分组索引位为1的元素和索引位为1step的元素为一组索引位为2的元素和索引位为2step的元素为一组索引位为3的元素和索引位为3step的元素为一组则将待排序数据分为2、15、96、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插入到腾出的空位中分组排序完成之后最终得出第一次分组排序结果第一次分组排序完成之后调整步长继续进行分组由于第二次计算出的步长step2step1/21即将所有上一次分组的数据全部为一组进行最后一次直接插入排序即可这里就不在重复演示了具体步骤和之前说到的直接插入排序一样参照这篇大牛领导单独找我聊了两句搞框架的同时别忘了算法。通过第二次插入排序完成之后就得到最后的排序结果啦。1.3 希尔排序算法分析时间复杂度时间复杂度最坏情况和直接插入排序的时间复杂一样都是O(n2)但有其他大神经过大量演示希尔排序的时间复杂度一般为O(n(1.3~2))比O(n2)性能好。空间复杂度在算法核心部分只采用了固定的几个中间变量((i,j,step,arrayb[0]))所以算法过程中消耗的内存是一个常量则空间复杂度为O(1)稳定性由于在排序过程中是根据步长将原始数据进行分组这样就可能会导致相同的元素分到不同组在最终排序时就不能保证原来两个相同元素的顺序啦所以希尔排序是不稳定的。综上所述希尔排序的时间复杂度为O(n2)空间复杂度为O(1)是不稳定算法总结到这里插入排序的三种排序介绍完毕下期开始介绍交换排序这里先总结一下插入排序的相关关键点(下图绿色部分)如下总结感谢小伙伴的点赞、收藏和评论下期继续~~~一个被程序搞丑的帅小伙关注Code综艺圈跟我一起学~~~
