希尔排序

文章目录

概念

希尔排序(shell sort)这个排序方法又称为缩小增量排序。
该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数增量(increment)<小于 n>作为间隔将全部元素分为 increment 个子序列,所有距离为 increment 的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。
然后缩小间隔 increment,重复上述子序列划分和排序工作。直到最后取 increment=1,将所有元素放在同一个子序列中排序为止。
由于开始时,increment 的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期 increment 取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

图示

希尔排序

复杂度

希尔排序是非稳定排序算法,该排序算法复杂度与步长密切相关。

步长序列 最坏情况下复杂度
n/2^i O(n^2)
2^k -1 O(n^(3/2))
2^i3^j O(n log^2 n)

参考阅读

理解希尔排序的排序过程