实现 Shell 排序：从理论到实践代码

Source: Dev.to

什么是 Shell 排序？

Shell 排序是对插入排序的改进，而插入排序是最基本的排序算法之一。插入排序会比较并插入数组中相邻的元素。
相比之下，Shell 排序会在固定间隔分开的元素上反复执行类似插入的操作，并逐渐减小间隔大小。当间隔减小到 1 时，算法的行为就完全等同于插入排序。

这就提出了一个重要问题：如果 Shell 排序最终会变成插入排序，那么改进到底来自哪里？

复杂度概览

• 插入排序

  • 时间复杂度： (O(n^2)) 到 (O(n))
  • 空间复杂度： (O(1))

• Shell 排序（取决于间隔序列）

  • 时间复杂度： 大约 (O(n^{1.3})) 到 (O(n \log n))
  • 空间复杂度： (O(1))

在实际使用中，当输入规模超过约 1,000 个元素时，性能差异会变得明显。

示例问题

你有 10,000 名工程师的整数分数，顺序是随机的，需要将分数相近的工程师配对。

1. 按分数对工程师排序。
2. 将排序后列表中相邻的元素配对。

如果第 1 步使用插入排序，最坏情况下可能需要多达十亿次操作（(O(n^2))）。Shell 排序将平均时间降低到大约 (O(n^{1.3})) 到 (O(n \log n))，具体取决于间隔序列。

插入排序思路

对于每个索引 (i) 从 1 到 (n-1)：

1. 将 (A_i) 的值存入临时变量 x。
2. 当 (A_j > x)（其中 (j = i-1, i-2, \dots)）时，将 (A_j) 向右移动一位。
3. 将 x 插入到正确的位置。

插入排序可以看作是间隔大小为 1 时的特殊 Shell 排序。

Shell 排序思路

1. 选择一个初始间隔值 g。
2. 对于每个索引 (i) 从 g 到 (n-1)：
   • 将 (A_i) 存入临时变量 x。
   • 当 (A_j > x)（其中 (j = i-g, i-2g, \dots)）时，将 (A_j) 移动到 (A_{j+g})。
   • 将 x 插入到 (A_{j+g})。
3. 缩小间隔并重复步骤 2‑3，直到间隔变为 1。

Shell 排序实现

模式 1：间隔序列作为输入提供

def insertion_sort(array, n, gap):
    for i in range(gap, n):
        # Store the value of A[i] in a temporary variable x
        x = array[i]
        j = i - gap
        while j >= 0 and array[j] > x:
            # Shift A[j] to A[j+gap]
            array[j + gap] = array[j]
            j -= gap
        # Insert x into A[j+gap]
        array[j + gap] = x

def shell_sort(array, n, gap_sequence):
    for gap in gap_sequence:
        insertion_sort(array, n, gap)

n 表示数组中的元素数量。

模式 2：在算法内部生成间隔序列

def insertion_sort(array, n, gap):
    for i in range(gap, n):
        x = array[i]
        j = i - gap
        while j >= 0 and array[j] > x:
            array[j + gap] = array[j]
            j -= gap
        array[j + gap] = x

def shell_sort(array, n):
    # Create the gap sequence (using the classic n//2, n//4, …, 1 scheme)
    gap_sequence = []
    gap = n // 2
    while gap > 0:
        gap_sequence.append(gap)
        gap //= 2
    if not gap_sequence:
        gap_sequence.append(1)

    for gap in gap_sequence:
        insertion_sort(array, n, gap)

Shell 排序的最优间隔序列仍是一个未解之谜。如果你发现任何错误，欢迎指出。