希尔排序

场景引入

插入排序有一个很好的性质：对基本有序的数据效率极高（接近 O(n)）。希尔排序的核心思路就是利用这个性质——先让数据"大致有序"，再用插入排序收尾。

希尔排序是第一个突破 O(n²) 的排序算法（1959 年由 Donald Shell 提出），它的时间复杂度取决于增量序列的选择，最优可达 O(n log²n)。

核心思路

希尔排序也叫缩小增量排序，思路是：

1. 选择一个递减的增量序列，例如 n/2, n/4, ..., 1
2. 对于每个增量 gap，将数组分成 gap 组，每组内部用插入排序
3. 随着 gap 缩小，每组包含的元素越来越多，但数组也越来越接近有序
4. 当 gap = 1 时，就是一次完整的插入排序——但此时数组已经基本有序，效率很高

为什么分组排序能加速？

插入排序的瓶颈在于：元素只能一位一位地移动。如果一个很小的元素在数组末尾，它需要移动 n-1 次才能到达正确位置。

希尔排序通过大步长的分组排序，让元素能够快速跨越长距离。例如 gap = 4 时，一个元素一次就能移动 4 个位置。经过几轮大步长排序后，元素基本就在正确位置附近了。

算法流程图

代码实现

function shellSort(arr) {
  const n = arr.length;

  // 增量序列：n/2, n/4, ..., 1
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 对每个子序列执行插入排序
    for (let i = gap; i < n; i++) {
      const key = arr[i];
      let j = i - gap;
      while (j >= 0 && arr[j] > key) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = key;
    }
  }

  return arr;
}

Knuth 增量序列

Shell 的原始增量序列 n/2, n/4, ... 并不是最优的。Knuth 提出的增量序列 1, 4, 13, 40, 121, ...（即 (3^k - 1) / 2）在实践中表现更好：

function shellSortKnuth(arr) {
  const n = arr.length;

  // 计算初始增量
  let gap = 1;
  while (gap < n / 3) gap = gap * 3 + 1; // 1, 4, 13, 40, 121, ...

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      const key = arr[i];
      let j = i - gap;
      while (j >= 0 && arr[j] > key) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = key;
    }
    gap = Math.floor(gap / 3);
  }

  return arr;
}

增量序列对比

不同的增量序列对性能影响很大：

增量序列	最坏时间复杂度	提出者
n/2, n/4, ..., 1	O(n²)	Shell (1959)
1, 4, 13, 40, ... (3^k-1)/2	O(n^1.5)	Knuth (1973)
1, 5, 19, 41, 109, ...	O(n^(4/3))	Sedgewick (1986)

Shell 的原始序列在某些情况下仍然是 O(n²)，比如 gap 序列中的值都是偶数时，奇数位置和偶数位置的元素在最后一轮之前完全没有比较过。Knuth 序列避免了这个问题。

复杂度分析

	时间复杂度	空间复杂度
最好	O(n log n) — 已有序	O(1)
平均	O(n^1.3)*	O(1)
最坏	O(n²)（Shell 序列）/ O(n^1.5)（Knuth 序列）	O(1)

*平均复杂度是经验值，精确分析至今仍是开放问题。

稳定性：不稳定。分组排序时，相同值的元素可能被分到不同组，排序后相对顺序可能改变。

原地排序：是。只需要常数级额外空间。

深入理解

• 希尔排序的本质是"用大步长让元素快速接近目标位置，再用小步长精细调整"
• 增量序列的选择至关重要——选错了可能退化到 O(n²)
• 虽然理论复杂度不如 O(n log n) 算法，但希尔排序代码简单、原地、常数因子小，在中小规模数据上表现不错
• 理解希尔排序有助于理解"预处理让数据接近有序"这一优化思路，TimSort 中也有类似的思想

LeetCode 练习

• LC 912. 排序数组 — 可用希尔排序实现