希尔排序

文章目录

1. 1. 概念
2. 2. 图示
3. 3. 复杂度
4. 4. 参考阅读

概念

希尔排序（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)

参考阅读

理解希尔排序的排序过程