希尔排序

注： ACM = Association for Computing Machinery，国际计算机学会，世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。

希尔排序是直接插入排序的改进版本。因为直接插入排序对那些几乎已经排好序的数列来说，排序效率极高，达到了 O(n) 的线性复杂度，但是每次只能将数据移动一位。希尔排序创造性的可以将数据移动 n 位，然后将 n 一直缩小，缩到与直接插入排序一样为 1，请看下列分析。

希尔排序属于插入类排序算法。

有一个 N 个数的数列：

我们取数列长度的一半为增量，以后每次减半，直到增量为1。

举个简单例子，希尔排序一个 12 个元素的数列：[5 9 1 6 8 14 6 49 25 4 6 3]，增量 d 的取值依次为：6，3，1：

越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为 1 的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。

在最好情况下，也就是数列是有序时，希尔排序需要进行 logn 次增量的直接插入排序，因为每次直接插入排序最佳时间复杂度都为：O(n)，因此希尔排序的最佳时间复杂度为：O(nlogn)。

所以，希尔排序最坏时间复杂度为 O(n^2)。

不同的分组增量序列，有不同的时间复杂度，但是没有人能够证明哪个序列是最好的。Hibbard 增量序列：1，3，7，···，2n−1 是被证明可广泛应用的分组序列，时间复杂度为：Θ(n^1.5)。

希尔排序的时间复杂度大约在这个范围：，具体还无法用数学来严格证明它。

希尔排序不是稳定的，因为每一轮分组，都使用了直接插入排序，但分组会跨越 n 个位置，导致两个相同的数，发现不了对方而产生了顺序变化。

二、算法实现

按照之前分析的几种排序算法，一般建议待排序数组为小规模情况下使用直接插入排序，在规模中等的情况下可以使用希尔排序，但在大规模还是要使用快速排序，归并排序或堆排序。