第14课希尔排序

所属模块： 排序算法 难度： Intermediate 标签： shell-sort, gap, diminishing 上一课： 第13课 - 插入排序 下一课： 第15课 - 归并排序

学习目标

完成本课学习后，你将能够：

理解希尔排序作为插入排序改进版的核心思想。
掌握“间隔序列”（Gap Sequence）在希尔排序中的作用。
实现一个完整的希尔排序算法。
分析希尔排序的时间复杂度及其与直接插入排序的比较。

核心概念

在上一课学习直接插入排序时，我们知道它的时间复杂度在最坏情况下是 O(n²)。造成这个结果的一个主要原因是，插入排序每次只移动相邻的元素。如果一个很小的元素恰好在数组的最右端，它需要一步一步地移动到最左端，效率很低。

希尔排序（Shell Sort）由Donald Shell于1959年提出，是对插入排序的一种改进。它的核心思想是：先让数组中任意间隔为 gap 的元素都有序，然后逐渐缩小 gap，直到 gap 为1时，算法就退化为了直接插入排序。

为什么这样更高效？ 想象你在整理一队高矮不一的学生。如果每次只能交换相邻的两个学生（直接插入排序），一个最矮的学生可能需要非常长的时间才能移动到队伍最前面。但如果你先按照“每5个位置”来比较，让每组内部相对有序（比如位置1,6,11…的为一组，位置2,7,12…的为另一组），队伍就已经大致有序了。然后再按“每2个位置”来比较，最后按“每1个位置”比较时，大部分元素已经离自己的正确位置不远，移动的次数就会大大减少。

这个“间隔”的大小，我们称之为 间隔序列（Gap Sequence）。如何选择间隔序列是希尔排序性能的关键。一个经典的序列是 Knuth序列：gap = 1, 4, 13, 40, 121, ... （即 gap = 3 * gap + 1，直到 gap < n/3 时停止）。本课我们将使用这个序列。

算法步骤总结：

根据数组长度 n，计算出一个最大的初始间隔 gap。
对所有间隔为 gap 的子序列进行直接插入排序。
缩小间隔 gap（例如使用 gap = gap // 3）。
重复步骤2和3，直到 gap 为1。最后一次排序就是纯粹的直接插入排序。

代码示例

下面是一个使用Knuth间隔序列的希尔排序的Python实现。代码注释详细解释了每一步的操作。

def shell_sort(arr):
    """
    希尔排序 (使用Knuth间隔序列)
    :param arr: 待排序列表
    """
    n = len(arr)
    
    # 1. 计算初始间隔 (Knuth序列: 1, 4, 13, 40, ...)
    # 我们从 gap=1 开始，通过公式 gap = 3*gap + 1 来生成序列，
    # 找到第一个大于等于 n//3 的 gap，然后回退一步。
    gap = 1
    while gap < n // 3:
        gap = gap * 3 + 1  # gap序列: 1 -> 4 -> 13 -> 40 -> ...
    
    # 2. 逐步缩小间隔，进行分组插入排序
    while gap > 0:
        # 从第 `gap` 个元素开始，对每个元素进行其所在间隔子序列的插入排序
        for i in range(gap, n):
            temp = arr[i]  # 暂存当前要插入的元素
            j = i
            # 内部循环：在间隔为 `gap` 的子序列中，寻找 `temp` 的正确插入位置
            # 条件：j >= gap 且 前一个间隔元素 arr[j-gap] 大于 temp
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]  # 将较大的元素向后移动
                j -= gap  # 向前移动一个间隔
            arr[j] = temp  # 将 temp 插入到正确位置
        
        # 缩小间隔
        gap //= 3
    
    return arr

# 测试代码
if __name__ == "__main__":
    test_array = [64, 34, 25, 12, 22, 11, 90]
    print("原始数组:", test_array)
    sorted_array = shell_sort(test_array)
    print("排序后数组:", sorted_array)
    
    # 预期输出:
    # 原始数组: [64, 34, 25, 12, 22, 11, 90]
    # 排序后数组: [11, 12, 22, 25, 34, 64, 90]

代码解析：

计算初始间隔： 我们使用一个 while 循环生成Knuth序列，直到 gap 超过数组长度的三分之一。此时我们停止，并使用这个 gap 作为第一轮的间隔。循环外的 gap //= 3 确保了每次循环后 gap 按照序列缩小。
分组插入排序核心： 外层的 while gap > 0 控制排序轮次。内部的 for i in range(gap, n) 遍历了每个需要处理的元素。关键的内层 while 循环在间隔为 gap 的“虚拟子序列”中执行了插入排序的逻辑，只不过比较和移动的步长变成了 gap。

实践练习

练习1：基础实现 修改上面的代码，不使用Knuth序列，而是采用更简单的间隔序列：gap 初始值为 n//2，之后每次循环 gap = gap // 2。测试它是否能正确排序数组 [12, 34, 54, 2, 3]。

练习2：间隔序列对比 使用练习1中的间隔序列 (gap = n//2, n//4, ..., 1) 和Knuth序列，分别对一个长度为20的逆序数组（如 [20, 19, 18, ..., 1]）进行排序。观察并记录两种实现的“比较”或“赋值”次数差异（可以通过在代码中添加计数器实现）。你发现了什么？

练习3：扩展应用 希尔排序是不稳定的排序算法。请构造一个简单的例子，证明它的不稳定性。提示：不稳定意味着排序后，相等的元素相对顺序可能发生改变。考虑一个包含重复元素的数组，如 [4a, 2, 4b, 1]，其中 4a 和 4b 是值相等但不同的元素。

常见错误

混淆内层和外层循环的作用： 初学者容易将 for i in range(gap, n) 的循环体写错。要记住，这个循环的目的是：以 i 为起点，将其视为待插入元素，在其左侧间隔为 gap 的序列中寻找插入位置。内层 while 循环才是移动元素和定位的步骤。
间隔更新逻辑错误： 在Knuth序列中，回退一步的操作容易被忽略。正确的顺序是：先生成一个大于 n//3 的 gap，然后在主循环开始前，将其回退到序列中的前一个值（在我们的代码中，通过先找再在外层循环中用 gap // 3 来缩小实现）。
忽略边界条件： 在内层 while 循环中，j >= gap 的条件至关重要。如果缺少这个条件，当 j 减小到小于 gap 时，arr[j - gap] 就会造成索引越界错误。

小结

核心思想： 希尔排序通过引入间隔序列，先对间隔较大的子序列排序，使数组“基本有序”，再进行精细的间隔为1的插入排序，从而大幅减少了元素移动的总次数。
性能提升： 相比直接插入排序的 O(n²)，希尔排序的性能依赖于间隔序列的选择。使用Knuth等良好序列时，其平均时间复杂度可降至 O(n^(3/2)) 或更优，是一种亚二次（sub-quadratic） 的排序算法。
关键实现： 实现的关键在于正确设置间隔序列，并在每个间隔下，正确地执行以该间隔为步长的插入排序。
算法特性： 希尔排序是不稳定的、原地排序算法，其空间复杂度为 O(1)。

希尔排序巧妙地利用了“宏观调控”的思想，是理解算法优化如何影响性能的一个经典范例。掌握了它，你就能更好地理解后续更高级的排序算法（如归并排序、快速排序）所采用的“分治”策略。下一课，我们将学习一种完全不同思想的、高效且稳定的排序算法——归并排序。

练习编辑器

rust

第14课 希尔排序