希尔排序

定义

希尔排序（Shell Sort）也称缩小增量排序，是插入排序的改进版本：按固定间隔将数组分成若干子序列分别做插入排序，再逐步缩小间隔，最终间隔为 1 时完成整体排序。

插入排序的弱点在于每次只能把元素移动 一位。元素离目标位置很远时，要经历大量相邻交换，最坏 $O(n^2)$。但它对 近乎有序 的数据很快（最好 $O(n)$）。

希尔排序的优化思路是：先用 较大间隔 做插入排序，让元素能一次跨越多个位置，快速接近目标区域；间隔逐步缩小后，数组已「大致有序」，最后的间隔为 1 的插入排序只需少量调整。换言之，用粗粒度的预排序，降低细粒度插入排序的工作量。

特性：平均 $O(n\log n)$ ~ $O(n^{3/2})$ · 最好 $O(n\log n)$ · 最坏 $O(n^2)$ · 空间 $O(1)$ · 原地 · 不稳定

过程

间隔 $h$ 即同组元素在原数组中下标之差。分组时从下标 $0,1,\dots ,h-1$ 各起一条链：下标 $i$ 与 $i+h,i+2h,\dots$ 归为同一子序列，组内 做插入排序，各组互不影响。完成一趟后缩小 $h$，并在 写回后的新数组 上重新分组；$h=1$ 时即对整个数组做普通插入排序。

下面采用常见希尔增量（初始 $h=\lfloor n/2\rfloor$，每趟减半至 $1$），以 [8, 3, 1, 2, 7, 5, 6, 4] 为例。$h=4$ 时，下标 $0$ 与 $4$ 同组得 8、7，下标 $1$ 与 $5$ 同组得 3、5，共 $h$ 组。各趟分组与组内排序如下（同组元素按下标先后列出）：

间隔	组数	各组元素	排序结果
4	4	[8, 7]、[3, 5]、[1, 6]、[2, 4]	[7, 8]、[3, 5]、[1, 6]、[2, 4]
2	2	[7, 1, 8, 6]、[3, 2, 5, 4]	[1, 6, 7, 8]、[2, 3, 4, 5]
1	1	[1, 2, 6, 3, 7, 4, 8, 5]	[1, 2, 3, 4, 5, 6, 7, 8]

性质

稳定性

希尔排序是 不稳定 排序算法。间隔大于 1 时，组内插入排序的交换跨度为 $h$，元素会与不 相邻 的位置互换——一次换位可能 跨过 中间的相等键，从而打乱它们的相对顺序。

以 [8, 5a, 5b, 1] 为例（5a、5b 值均为 5），间隔序列为 2、1。间隔 2 时分两组：下标 0,2 为 [8, 5b]，下标 1,3 为 [5a, 1]，组内各自做插入排序：

步骤	说明	结果
组 0,2	5b < 8，交换	[5b, 5a, 8, 1]
组 1,3	1 < 5a，交换	[5b, 1, 8, 5a]

组 0,2 交换时，5b 从下标 2 跳到 0，跨过了 中间的 5a。输入时 5a 在 5b 前面，此趟结束后 5b 已位于 5a 之前，相对顺序被打乱；间隔 1 排完得 [1, 5b, 5a, 8]，也无法恢复。

时间复杂度

时间复杂度与 增量序列 的选取有关。

情况	复杂度	说明
最好	$O(n\log n)$	已有序时内层可提前 break
最坏	$O(n^2)$	希尔增量（$n/2,n/4,\dots ,1$）可退化至此
平均	$O(n\log n)$ ~ $O(n^{3/2})$	取决于增量序列；实践中优于简单二次排序

下文代码采用 Knuth 增量（$1,4,13,\dots$，即 $3h+1$），可进一步降低复杂度上界。

空间复杂度

$O(1)$。原地排序，仅使用常数个辅助变量。

代码实现

采用 Knuth 增量序列（初始 gap 取不超过 len/3 的最大 $3h+1$），保存 key 后移元素，减少不必要的交换：

void shell_sort(int* arr, int len) {
    int gap = 1;
    while (gap < len / 3) gap = gap * 3 + 1;
 
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
        gap /= 3;
    }
}

参考阅读

• OI Wiki - 希尔排序 (2026-06-10)
• 菜鸟教程 - 希尔排序 (2026-06-10)