排序算法之：插入排序的变体——希尔排序（Shell Sort）的步长序列优化与性能分析

我们先看一个具体问题：

给定一个长度为 n 的整数数组 arr，使用希尔排序对其进行升序排序。
希尔排序的核心在于选择一个递减的步长序列（gap sequence），对每个步长执行间隔为 gap 的插入排序。
请设计一个高效的步长序列，并分析其时间复杂度。

第一步：希尔排序的基本思想

希尔排序是插入排序的改进版，目的是通过“大步长”的预处理，让元素更快地移动到最终位置附近，从而减少后续小步长插入排序的比较和移动次数。

基本步骤：

1. 选择一个递减的步长序列：\(gap_1 > gap_2 > \dots > gap_t = 1\)。
2. 对每个步长 \(gap_k\)，将数组分成 \(gap_k\) 个子序列（每个子序列由间隔为 \(gap_k\) 的元素组成），分别对这些子序列进行插入排序。
3. 最后一步一定是 \(gap = 1\)，即普通的插入排序，此时数组已经“几乎有序”，插入排序效率很高。

第二步：示例演示

假设数组为 \([8, 3, 9, 1, 4, 2, 7, 6, 5]\)，我们使用步长序列 \([5, 2, 1]\)。

• gap = 5：将数组分为 5 个子序列（间隔 5 的元素组成一组）：

  • 子序列1（索引 0,5）：[8, 2] → 插入排序后 [2, 8]
  • 子序列2（索引 1,6）：[3, 7] → 已有序
  • 子序列3（索引 2,7）：[9, 6] → [6, 9]
  • 子序列4（索引 3,8）：[1, 5] → 已有序
  • 子序列5（索引 4）：[4] → 不变
    操作后数组变为 \([2, 3, 6, 1, 4, 8, 7, 9, 5]\)。

• gap = 2：分为 2 个子序列：

  • 子序列1（索引 0,2,4,6,8）：[2, 6, 4, 7, 5] → 插入排序后 [2, 4, 5, 6, 7]
  • 子序列2（索引 1,3,5,7）：[3, 1, 8, 9] → 插入排序后 [1, 3, 8, 9]
    操作后数组变为 \([2, 1, 4, 3, 5, 8, 6, 9, 7]\)。

• gap = 1：普通插入排序，此时数组已较有序，只需少量调整 → 最终有序数组 \([1, 2, 3, 4, 5, 6, 7, 8, 9]\)。

第三步：步长序列的选择与性能影响

步长序列是希尔排序性能的关键。不同的序列导致时间复杂度不同。

常见步长序列及其理论/经验性能：

1. Shell 原始序列（1959）：\(gap_k = \lfloor n / 2^k \rfloor\)，即 n/2, n/4, …, 1。

   • 最坏情况时间复杂度：\(O(n^2)\)（例如对某些倒序数组）。
   • 实际中简单但效率不高。

2. Hibbard 序列：\(gap_k = 2^k - 1\)，即 1, 3, 7, 15, 31, …，直到 gap < n。

   • 最坏情况时间复杂度：\(O(n^{3/2})\)。
   • 数学证明可降低比较次数。

3. Sedgewick 序列：通过经验公式 \(gap_k = 9 \times 4^k - 9 \times 2^k + 1\) 或 \(4^k - 3 \times 2^k + 1\) 等交错生成。

   • 是目前已知较好的序列之一，最坏情况时间复杂度约为 \(O(n^{4/3})\)，平均接近 \(O(n \log n)\)。
   • 许多标准库的实现采用类似序列。

4. Tokuda 序列：\(gap_k = \lceil (9 \times (9/4)^{k-1} - 4) / 5 \rceil\)。

   • 在实验数据中表现优异。

第四步：算法实现（以 Sedgewick 序列为例）

def shell_sort(arr):
    n = len(arr)
    # 生成 Sedgewick 序列（只生成小于 n 的步长）
    gaps = []
    k = 0
    while True:
        gap1 = 9 * (4**k) - 9 * (2**k) + 1
        gap2 = 4**k - 3 * (2**k) + 1
        if gap1 > 0 and gap1 < n:
            gaps.append(gap1)
        if gap2 > 0 and gap2 < n and gap2 != gap1:
            gaps.append(gap2)
        if gap1 >= n and gap2 >= n:
            break
        k += 1
    gaps.sort(reverse=True)  # 从大到小
    
    for gap in gaps:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 对间隔 gap 的子序列进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
    return arr

解释：

• 先生成所有小于 n 的 Sedgewick 步长，按从大到小排序。
• 对每个步长，从 gap 开始向后遍历，将当前元素 temp 插入到同子序列的前面正确位置（间隔为 gap 的比较与移动）。

第五步：性能分析

1. 时间复杂度：

   • 希尔排序的时间复杂度依赖于步长序列，没有统一的公式。
   • 对于 Shell 原始序列，最坏 \(O(n^2)\)。
   • 对于 Hibbard 序列，最坏 \(O(n^{3/2})\)。
   • 对于 Sedgewick 序列，最坏 \(O(n^{4/3})\)，平均接近 \(O(n \log n)\)。
   • 实际应用中，希尔排序在中等规模数据上表现优秀，比 \(O(n \log n)\) 的算法常数因子小。

2. 空间复杂度：\(O(1)\)（原地排序）。

3. 稳定性：不稳定。因为间隔交换可能改变相同元素的相对顺序。

第六步：步长序列的优化方向

• 目标：让步长之间互质，以增加元素之间的混合程度。
• 经验法则：避免步长之间成倍数关系，否则某些位置可能在整个过程中从未被比较/交换。
• 现代研究：通过大量实验找出在平均情况下比较次数、移动次数最少的序列。

例如，Sedgewick 序列通过混合指数和多项式的形式，使得排序过程中元素能够更均匀地分散到各个位置，从而减少后续步骤的工作量。

第七步：总结

希尔排序的核心是 步长序列 的设计，它通过大步长的预处理使数组“基本有序”，从而让最后一步的插入排序非常高效。虽然理论上最坏时间复杂度不如 \(O(n \log n)\) 的算法，但在实际中，由于缓存友好性和较小的常数因子，它在某些场景下仍然很有竞争力。优化步长序列是一个经验与理论结合的问题，Sedgewick 序列是目前公认的优秀选择之一。