排序算法（六）：希尔排序

希尔排序是对插入排序的一种改进，也叫递减增量排序，算法过程中通过对增量值的递减调整，形成每一个增量值对应的一个或多个待排序分组，分别对分组执行插入排序，最后调整增量值为一，对最后的分组排序后即完成排序过程。

插入排序过程是从待排序集合中每次选择一个元素，通过不断比较和交换位置，移动到已排序集合的适当位置上。插入排序每次只排序一个元素，并且当前元素的排序完成后，对下一个元素的排序过程并无影响，而希尔排序完成某一个增量的排序后，对下一个增量的排序是有辅助作用的。

算法过程

希尔排序算法中有一个关键概念：增量（increment），或者称之为步长或间隔（gap）更容易理解，它的作用是将序列中间隔为增量值大小的元素，提出出来作为一个分组。例如间隔大小为

时，从第一个元素开始，以

为间隔取元素形成第一个分组，然后从第二个元素开始，以同样间隔取元素形成分组，直到形成

个分组，则原始序列的元素已全部分散在这

个分组里。

算法步骤：

1. 根据增量

值大小，将序列拆分为

个分组

1. 对每个分组执行插入排序算法，并对

值按指定规则调整大小

1. 重复步骤 1, 2，直到

值为 0

示例

当初始序列为：5, 3, 4, 0, 2, 1, 8, 6, 9, 7 gap 值为 3 时

元素以 3 为间隔，拆分为 3 个分组，因为从第 4 个元素开始，后续所有元素都已经在三个分组里：

所以希尔排序就是将序列拆分为

个子序列，这里称之为分组，然后对每个分组执行插入排序。由此可知，希尔排序与插入排序的不同之处在于：希尔排序是不断的对分组进行排序，以此来完成最后的排序，而插入排序是直接对原始序列进行排序。并且希尔排序的最后一次排序一定是插入排序，因为最后一次排序的增量值为一。

希尔排序的复杂度影响因素就是增量值的调整规则。常见的增量值有

，即对序列的长度不断折半作为增量大小。还有

，在下面的示例中选择的就是这种方式。

step 1 序列为：5, 3, 4, 0, 2, 1, 8, 6, 9, 7 因为

为 10，

，所以

初始值为 3，

，

初始值为 7

因为

值为 7，所以序列被拆分为 7 个分组，分别为：

1. 5, 6
2. 3, 9
3. 4, 7
4. 0
5. 2
6. 1
7. 8

对每个分组执行插入排序，不过很明显可以发现一个情况，这 7 个分组都是有序状态的，所以序列状态不变。

step 2 序列为：5, 3, 4, 0, 2, 1, 8, 6, 9, 7

，

，

，

因为

值为 3，所以序列被拆分为 3 个分组，分别为：

1. 5, 0, 8, 7
2. 3, 2, 6
3. 4, 1, 9

对每个分组执行插入排序后，3 个分组变为：

1. 0, 5, 7, 8
2. 2, 3, 6
3. 1, 4, 9

以第 3 个分组为例，由 4, 1, 9 变为 1, 4, 9，可以发现一个很明显的事实，在这个分组里，4 和 1 位置相差一，即只需要比较和交换一次即可确定这个元素的，而且这个顺序很可能在后续的排序过程中不会变化，相对于直接对原始序列执行插入排序算法，两个元素位置相差 3 而言，大大降低了比较和交换的次数。

当然，在不同的增量值变化规则中，可能会存在上一轮调整过的元素次序，在下一轮排序被颠倒的情况，不过总体上序列中元素是朝向有序的方向变化的，并且随着增量值的递减，序列将会变得越发有序，也就是说每一轮的排序，对下一轮都是有辅助作用的。而且给增量值的变化设定一个较为科学的规则，能够极大降低希尔排序的时间复杂度。 step 3 序列为：0, 2, 1, 5, 3, 4, 7, 6, 9, 8

，

，

，

因为

值为 1，所以序列只有 1 个分组，该轮排序过程完全等同于插入排序。

代码示例

def shellSort(arr):
    k = int(math.log2(len(arr) + 1))  # 2^k - 1 <= len(arr)
    while k > 0:
        gap = 2 ** k - 1  # 间隔大小
        for index in range(0, gap):  # 分组的个数
            for i in range(gap + index, len(arr), gap):  # 对分组执行插入排序
                tmp = arr[i]
                while i > index and tmp < arr[i - gap]:
                    arr[i] = arr[i - gap]
                    i = i - gap
                arr[i] = tmp
        k = k - 1

示例代码中存在四层循环，最外层循环用于对增量值进行递减，确保希尔排序的最后一轮排序间隔大小为一，以此来保证排序的正确性。第二层循环是增量值对应的分组个数，第三和第四层循环结构基本与插入排序完全相同，作用就是对每个分组执行插入排序操作。

算法分析

希尔排序是一种不稳定排序算法，排序过程中，存在两个元素跨多个位置的替换。对于

个元素的序列，由插入排序的结论可知，插入排序的最好情况为序列处于已排序状态，每个元素的插入排序过程只需要进行一次比较即可，即

个元素的序列，排序的比较复杂度为

，交换复杂度为

；最坏情况为序列处于逆序状态，比较和交换复杂度为

。对于希尔排序而言，若分组的个数为

，则每个分组的元素个数近似为

。

• 最好情况下希尔排序的每个增量值对应的比较次数

近似为：

...

...

...

因为

，所以对于希尔排序，最好情况下的比较复杂度为

，交换复杂度为

。

• 对于插入排序而言，最坏情况即为序列为逆序的状态，不过对于希尔排序，逆序并不一定为最坏情况，因为增量值的变化规则是人为设定的，所以不确定是否针对增量值的变化规则而特意设定一组序列。此处不妨以逆序作为示例分析一下希尔排序的复杂度。忽略每一轮排序对下一轮排序的影响，则有：

...

...

...

总时间复杂度为：

。但是观察示例过程中 step 1 和 step 3 的序列，经过两轮排序后，step 3 的序列已经较 step 1 显得更为有序，所以从大方向看，每一轮的排序对下一轮的排序是有序辅助效果的。即使给出的初始序列为逆序状态，当增量值减为一的时候，此时的序列一定相对于最初状态有序很多。当增量值变化规则为

时，比较和交换的时间复杂度最坏为

。

希尔排序属于原地排序算法，不需要申请额外的存储空间。它是在插入排序的基础上进行了改进，实际就是除了最后的插入排序外，对多个子分组也执行了排序。所以看到该算法的第一印象就是，它额外做了这么多工作，复杂度应该大于插入排序才对。所以导致希尔排序最坏复杂度低于插入排序的原因就是，通过合理的增量值设置，可以将本来需要多次比较和交换才能调整到正确位置的元素，只需要很少次的比较和交换就可完成。

引用

Shellsort & Algorithmic Comparisons

What is the benefit of Shell Sort versus Insertion/Bubble Sort?