希尔排序

发布日期: 2025-04-28

文章字数: 964

希尔排序是基于插入排序的简单改进，通过预处理增加数组的局部有序性，突破了插入排序的$O(n^2)$时间复杂度。

`h`有序数组

一个数组是h有序的，是指这个数组中任意间隔为 h（或者说间隔元素的个数为 h-1）的元素都是有序的。

这个概念用文字不好描述清楚，直接看个例子吧。比方说 h=3 时，一个 3 有序数组是这样的：

nums:
[1, 2, 4, 3, 5, 7, 8, 6, 10, 9, 12, 11]
 ^--------^--------^---------^
    ^--------^--------^---------^
       ^--------^--------^----------^

 1--------3--------8---------9
    2--------5--------6---------12
        4--------7--------10---------11

可以看到，数组中任意间隔为 3的元素都是有序的。

另外，按照这个定义，当一个数组完成排序的时候，其实就是 1 有序数组。

希尔排序要发表看法了：

你插入排序的问题是，上来就想着一步到位，直接把乱序数组变成 1 有序数组。而我希尔排序不着急，比方说，我先把乱序数组变成一个 16 有序数组，然后再变成 8 有序数组，4 有序数组，2 有序数组，最后变成 1 有序数组，完成排序。

这个1, 2, 4, 8, 16...的序列称之为「递增函数」，我上面举的例子的递增函数就是 $2^(k-1)$

那么如何把一个数组变成 h 有序数组呢？基于插入排序的代码改动几个地方就行了，直接看希尔排序的代码吧：

# 希尔排序，对 h 有序数组进行插入排序
# 逐渐缩小 h，最后 h=1 时，完成整个数组的排序
def sort(nums):
    n = len(nums)
    # 我们使用的生成函数是 2^(k-1)
    # 即 h = 1, 2, 4, 8, 16...
    h = 1
    while h < n // 2:
        h = 2 * h

    # 改动一，把插入排序的主要逻辑套在 h 的 while 循环中
    while h >= 1:
        # 改动二，sorted_index 初始化为 h，而不是 1
        sorted_index = h
        while sorted_index < n:
            # 改动三，把比较和交换元素的步长设置为 h，而不是相邻元素
            i = sorted_index
            while i >= h:
                if nums[i] < nums[i - h]:
                    # swap(nums[i], nums[i - h])
                    tmp = nums[i]
                    nums[i] = nums[i - h]
                    nums[i - h] = tmp
                else:
                    break
                i -= h
            sorted_index += 1

        # 按照递增函数的规则，缩小 h
        h //= 2

递增函数的选择是关键

希尔排序的性能和递增函数的选择有很大关系，上面的代码中我们使用的递增函数是 $h = 2^k-1$。因为这是最简单的，但这并不最优的选择。

比方说《算法4》中给的递增函数是 $h = (3^k - 1) / 2$，即1，4，13，40，121 ...这个递增函数的选择是比较合理的。代码如下，主要修改 h 的初始化和更新逻辑：

# 把生成函数换成 (3^k - 1) / 2
# 即 h = 1, 4, 13, 40, 121, 364...
def sort(nums):
    n = len(nums)
    h = 1
    while h < n / 3:
        h = 3 * h + 1

    while h >= 1:
        sorted_index = h
        while sorted_index < n:
            i = sorted_index
            while i >= h:
                if nums[i] < nums[i - h]:
                    tmp = nums[i]
                    nums[i] = nums[i - h]
                    nums[i - h] = tmp
                else:
                    break
                i -= h
            sorted_index += 1
        # 按照递增函数的规则，缩小 h
        h //= 3