看过前几篇选择排序、插入排序和冒泡排序后,你认为哪个排序效率相对高点呢?我猜一定是插入排序,插入排序在部分已经正序的数组中效率要优于其他两个,今天再介绍一种插入排序的增强版-希尔排序。希尔排序又称“缩小增量排序”,由DL.Shell于1959年提出而得名。


想想插入排序,元素一步一步从后往前找合适的位置插入,你是否感觉一步步移动比较慢,能否加大步长呢?
希尔排序基本思想:把数组按步长gap分组,对每组中的数据进行直接插入排序方法进行排序,然后逐步减小步长,每组包含的数据也越来越多,当步长值为1时,也就变成了直接插入排序,因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高。

流程

原数组:5          8          3         1         2        4        6         6        10         1

gap = n/ 2 =5 时: (n=10)

把相隔距离为5的元素分成一组,共5组,即a组{5,4} ,b组{8,6},c组{3,6},d组{1,10},e组{2,1}

这一轮排序后为:4          6          3         1         1        5        8         6        10         2

gap = 5 / 2 = 2 时:

把相隔距离为2的元素分成一组,共2组,即a组{4,3,1,8,10},b组{6,1,5,6,2}

这一轮排序后为:1          1          3         2         4        5        8         6        10         6

gap = 2  / 2 = 1 时:

1          1          3         2         4        5        8         6        10         6

把相隔距离为1的元素分为一组,共1组,即{1,1,3,2,4,5,8,6,10,6}

这一轮排序后为:1          1          2         3         4        5        6         6        8         10

PS : 如果数组长度不是偶数,自己可以画一画是怎么分组的。

代码(C#)

经过实践证明,2等分的方式并不是最优选择,步长为1,4,13,40,121,364,1093…相对来说效率更高一点。

总结

  • 希尔排序是插入排序的增强版
  • 时间复杂度和步长有关
  • 稳定性:不稳定 如:5  5  2  8  6

如果转载,请给出原文链接,谢谢!


微信支付宝

如果本文帮助到您,请随意打赏作者