希尔排序

2026 大纲 七（六）希尔排序（又称缩小增量排序）。

让插入排序的两个"快"条件错开满足

直接插入排序在两种情况下很快：① $n$ 很小时；② 序列基本有序时。

麻烦在于，这两个条件对一个给定的输入通常都不成立。希尔排序的办法是——分几趟，让它们错开满足：

• 大增量的那几趟：按间隔 $d$ 把序列分成 $d$ 组，每组只有约 $n/d$ 个元素，满足条件 ①。而且此时一次移动能跨 $d$ 格，远距离的逆序对被成批消除。
• 小增量的那几趟（尤其最后 $d=1$ 那趟）：前面已经把序列搓得相当有序了，满足条件 ②。

一趟做完之后，序列达到一个叫 $d$-有序 的状态：

任意 $i$ 都有 $A[i]\le A[i+d]$。 等价说法是：把下标按模 $d$ 分成 $d$ 组，每组内部各自有序。

🔴 $d$-有序 $\ne$ 整体有序。 前缀通常仍然是乱的（$A[0]$ 未必最小），只有"隔着 $d$ 看"才有序。所以希尔排序一趟下来 0 个元素就位。

还有一条性质保证了这个方案能收敛：对已 $d_1$-有序的序列再做 $d_2$-有序处理，结果仍保持 $d_1$-有序。有序性单调累积，不会白干。

先动手看一眼

加载可视化中...

代码：就是把步长 1 换成 $d$

void ShellSort(int A[], int n) {
    for (int d = n / 2; d >= 1; d /= 2) {      // 增量序列 n/2, n/4, ..., 1
        for (int i = d; i < n; i++) {          // 从第 d 个元素起，交替处理各组
            int temp = A[i];                   // 暂存待插元素
            int j = i - d;                     // 同组的前驱在 i-d 处
            while (j >= 0 && A[j] > temp) {    // 与直接插入排序唯一的差别：步长 d 而不是 1
                A[j + d] = A[j];               // 后移一个"步长"
                j -= d;
            }
            A[j + d] = temp;
        }
    }
}

组内用的就是直接插入排序——真题直接问过"希尔排序的组内排序采用的是什么"，答案就是它。整段代码与直接插入排序的差别只有一处：步长从 1 换成了 $d$。

三处细节：

第一，没有显式的"分组再分别排序"。 外层 i 从 $d$ 一直走到 $n-1$，交替处理各组的元素（$i=d$ 属第 0 组、$i=d+1$ 属第 1 组……）。效果与"一组一组排完"完全等价，因为不同组的元素之间从不比较，处理次序不影响结果。

第二，j >= 0 不能省。 这里没有哨兵可用——A[0] 是真实数据，$d$ 组各有各的"组内起点"，一个哨兵挡不住 $d$ 个方向。这是希尔排序与直接插入排序在写法上唯一实质性的差别。

第三，边界：n <= 1 时 d = 0，外层条件不成立直接返回；n = 2 时 d = 1，退化成一趟普通插入排序。都正确。

反推增量：真题反复用到的手法

真题给出某一趟（或某两趟）的排序结果，问采用的增量是多少。做法是固定的：

🔴 对每个候选增量 $d$，把下标按 $modd$ 分成 $d$ 组，检查每组内部是否升序。只有"全部组都有序"的那个 $d$ 才可能。

拿一个真题设定演示。第 1 趟结果是 9, 1, 4, 13, 7, 8, 20, 23, 15（下标 0～8），候选增量 2、3、4、5：

候选 $d$	分组（按下标 $modd$）	各组元素	是否全有序
2	{0,2,4,6,8},	{9,4,7,20,15},	❌ 组 0 里 $20>15$
3	{0,3,6}, {1,4,7},	{9,13,20}, {1,7,23},	✅ 全部升序
4	{0,4,8}, {1,5}, {2,6},	{9,7,15}, …	❌ 组 0 里 $9>7$
5	{0,5}, {1,6}, {2,7}, {3,8},	{9,8}, …	❌ 组 0 里 $9>8$

答案是 3。手法上有两个提速点：一是从组 0 开始查，发现一个逆序就立刻排除，不必把所有组都列完；二是候选增量越大，每组元素越少、越容易有序，所以大增量往往不是先被排除的那个，别按顺序死磕。

给两趟结果反推增量序列时道理一样，只是要逐趟各自验证：第一趟结果要对第一个增量 $d_1$ 满足 $d_1$-有序，第二趟结果要对 $d_2$ 满足 $d_2$-有序。⚠️ 注意第二趟的验证对象是第二趟的结果，不是原始序列。

还有一类问法是给出几趟的序列变化，问用的是哪种排序算法。希尔排序的指纹是：看不出任何"前缀有序"或"后缀就位"，但按某个间隔跳着看就是有序的。

⚠️ 与归并排序最容易混：希尔的有序是跳着的（间隔 $d$），归并的有序是连续段（段长 $2^k$）。判之前先问一句："是隔着看有序，还是连着一段有序？"

不稳定：跨组跳跃越过了从未比较的元素

最小反例是 {2a, 2b, 1, 3}（$n=4$，$d=2,1$）：

趟	增量	分组与组内排序	结果
初始	—	—	2a 2b 1 3
1	$d=2$	组0：$A[0]=2a,A[2]=1$ → 排成 $1,2a$（2a 从下标 0 跳到下标 2） 组1：$A[1]=2b,A[3]=3$ → 已有序，不动	1 2b 2a 3
2	$d=1$	整体插入排序，此时已有序，无移动	1 2b 2a 3

2a 与 2b 被分到了不同的组（下标 0 与 1 对 $d=2$ 不同余），各组独立排序时互相看不见对方——2a 因为组内的 1 比它小而被迫后跳两格，跳的过程中越过了与它相等的 2b，而这次"越过"从来没有经过两者之间的一次比较。

对比直接插入排序：2a 想越过 2b 必须先与它比较一次，而 A[j] > temp 在相等时为假，越不过去。希尔排序把这次比较从流程里删掉了。

🔴 一句话记法：跨组跳跃 = 越过了从未与之比较的元素 = 可能不稳定。 快速排序（枢轴远距离换位）、简单选择排序（远距离交换）、堆排序（堆顶与末元素交换）不稳定的根源都是同一句话。

同一个"跨距离访问"的机制还带来第三个后果：只能用于顺序表。算法每一步都要访问 A[j-d]、A[j+d]，顺序表上是一次下标加减（$O(1)$），链表上要从当前结点重新走 $d$ 步（$O(d)$），而且单链表无法反向走。

复杂度取决于增量序列

🔴 希尔排序是本章唯一时间复杂度取决于增量序列的算法。 谈它的复杂度必须先说清用的是哪个序列。

增量序列	取值方式	示例（$n=16$）	最坏时间复杂度
Shell 原始序列	$d_i=\lfloor n/2^i\rfloor$	8, 4, 2, 1	$O(n^2)$
Hibbard 序列	$d_i=2^i-1$	15, 7, 3, 1	$O(n^{1.5})$
Knuth 序列	$d_i=(3^i-1)/2$	13, 4, 1	$O(n^{1.5})$ 量级

没有特别说明时按 Shell 原始序列，此时最好 $\mathrm{\Theta }(n{\log }_{2}n)$、平均约 $O(n^{1.3})$、最坏 $O(n^2)$，空间 $O(1)$。

增量序列必须满足两条约束：

① 最后一个增量必须为 1。 只有 $d=1$ 那一趟会比较相邻元素。若最后一趟增量是 2，下标为奇数与偶数的两组元素从头到尾没有互相比较过一次，结果必然不是有序的。

② 各增量之间不应有 1 之外的公因子。 这一条正好解释了 Shell 原始序列为什么最坏还是 $O(n^2)$——$n/2,n/4,\dots$ 全是 2 的倍数，下标同奇偶的元素在最后一趟之前从不跨组交流，前面几趟等于空转，所有工作都堆到 $d=1$ 那一趟。

逐趟推演：两个例子与执行流程图（第一次学、或想手动模拟就展开）

工作原理示意（$d=4,2,1$）：

原始序列:  [8, 5, 2, 9, 3, 7, 1, 6]

d=4:  分组 {8,3} {5,7} {2,1} {9,6}  →  各组插入排序
      [3, 5, 1, 6, 8, 7, 2, 9]        ← 此时"隔 4 看"处处有序

d=2:  分组 {3,1,8,2} {5,6,7,9}      →  各组插入排序
      [1, 5, 2, 6, 3, 7, 8, 9]        ← "隔 2 看"处处有序（隔 4 看仍有序）

d=1:  整体插入排序（此时逆序对极少，移动次数很少）
      [1, 2, 3, 5, 6, 7, 8, 9]

例一（$n=10$，Shell 原始增量 $d=5,3,1$）：{49, 38, 65, 97, 76, 13, 27, 49*, 55, 04}

第一趟 $d=5$——分成 5 组，每组 2 个：

组0: A[0]=49, A[5]=13  →  13, 49
组1: A[1]=38, A[6]=27  →  27, 38
组2: A[2]=65, A[7]=49* →  49*, 65
组3: A[3]=97, A[8]=55  →  55, 97
组4: A[4]=76, A[9]=04  →  04, 76

结果：13 27 49* 55 04 49 38 65 97 76

第二趟 $d=3$——分成 3 组：

组0: A[0]=13, A[3]=55, A[6]=38, A[9]=76  →  13, 38, 55, 76
组1: A[1]=27, A[4]=04, A[7]=65           →  04, 27, 65
组2: A[2]=49*, A[5]=49, A[8]=97          →  49*, 49, 97

结果：13 04 49* 38 27 49 55 65 97 76

第三趟 $d=1$——整体插入排序，结果：04 13 27 38 49* 49 55 65 76 97

注意最终结果里 49*（原本在下标 7）排在了 49（原本在下标 5）前面——两个相等元素的次序被翻转了。

例二（$n=8$，$d=4,2,1$）：{49, 38, 65, 97, 76, 13, 27, 49*}

趟	增量	分组	结果
1	$d=4$	{49,76} {38,13} {65,27}	49 13 27 49* 76 38 65 97
2	$d=2$	{49,27,76,65}	27 13 49 38 65 49* 76 97
3	$d=1$	整体	13 27 38 49 49* 65 76 97

这一例最终 49 仍在 49* 前面——没出事不等于稳定。判定不稳定只需要一个反例，判定稳定则必须证明所有输入都不会出事。

Shell 原始序列最坏情形的构造（想看清"空转"是怎么发生的就展开）

取 $n$ 个互不相同的数，把较大的一半按升序放在偶数下标上，较小的一半按升序放在奇数下标上。此时对 $d=n/2,n/4,\dots ,2$ 的每一趟，同组元素的下标同奇偶（因为增量都是偶数），而各奇偶类内部本来就有序——这些趟一次移动都做不了，全是空转。所有工作都堆到最后一趟 $d=1$，而那一趟面对的序列有约 $n^2/8$ 个逆序对，退化成 $O(n^2)$ 的插入排序。

$n$	$d\ge 2$ 各趟的移动次数	$d=1$ 那一趟的移动次数	$n^2/8$
16	全为 0	36	32
64	全为 0	528	512
256	全为 0	8 256	8 192
1024	全为 0	131 328	131 072

Hibbard 序列 $1,3,7,15,\dots$ 相邻两项互素，就没有这个毛病，最坏能压到 $O(n^{1.5})$。

三种复杂度的来历，以及与直接插入、折半插入的对照

最好情况（初始已有序）：每趟对每个 $i\ge d$ 做恰好 1 次比较（A[j] > temp 立刻为假）、0 次移动。对 Shell 原始增量，趟数 $t=\lfloor {\log }_{2}n\rfloor$，总比较次数

$$\sum _k(n-d_k)=n\cdot t-\sum _k{d}_k\approx n{\log }_{2}n-n$$

即 $\mathrm{\Theta }(n{\log }_{2}n)$。（$n=1024$ 时实测恰为 $10\times 1024-1023=9217$ 次比较、0 次移动。）

平均情况：希尔排序的精确分析涉及尚未完全解决的数学问题，至今没有公认最优的增量序列。教材给出的经验结论是：当 $n$ 在某个特定范围内时，所需的比较和移动次数约为 $n^{1.3}$；增量序列取 $d_k=2^{t-k+1}-1$ 时可证明为 $O(n^{1.5})$。

对比项	直接插入排序	希尔排序
平均时间复杂度	$O(n^2)$	约 $O(n^{1.3})$
一次移动跨越的距离	1 个位置	$d$ 个位置
优化的是	—	移动次数
稳定性	稳定	不稳定
存储结构	顺序表、链表均可	只能顺序表
适用场景	$n$ 小或基本有序	$n$ 中等、初始无序

与折半插入排序放在一起看，插入排序的两条改进路线就很清楚了：折半插入只优化查找（比较次数 $O(n^2)\to \mathrm{\Theta }(n{\log }_{2}n)$），移动不变，总复杂度不变；希尔优化移动（让元素一步跨 $d$ 格），比较也跟着减少，总复杂度真的降了。

$O(n^2)$ 插入排序的瓶颈在移动，谁动了移动谁才真正提速。

考点速记

三条结论：

1. 一趟后是 $d$-有序（隔 $d$ 看有序），不是整体有序，0 个元素就位；一趟指一个增量，不是一个组。
2. 跨组跳跃同时导致三件事：提速、不稳定、只能用顺序表。
3. 复杂度取决于增量序列，Shell 原始序列最坏 $O(n^2)$。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 由某趟结果反推增量：给一趟排序结果和四个候选增量，问用的可能是哪个。逐个候选按 $modd$ 分组，检查每组是否升序；发现一个逆序立刻排除。
• 由两趟结果反推增量序列：给初始序列和前两趟结果，问两趟采用的增量依次是什么。逐趟各自验证，第二趟验的是第二趟的结果。
• 由序列变化判断算法：给一张"初始 / 第 1 趟 / 第 2 趟"的表，问用的是哪种排序。希尔的指纹是"看不出前缀有序也看不出后缀就位，但隔着某个间隔看是有序的"。⚠️ 别和归并混——一个是跳着有序，一个是连续段有序。
• 组内排序用什么：答直接插入排序。
• 稳定性判断：希尔在"不稳定的有哪些"这类题里出现，与快排、堆排同列。

易错："一趟"是一个增量，不是一个组。 $d=4$ 时要把 4 个子序列全排完才算一趟。

易错：$d$-有序不保证任何元素就位。 别用"前缀有序"或"最值归位"去套希尔。

易错：反推增量时别只查组 0。 组 0 有序不代表其他组也有序，要么全查、要么查到第一个逆序为止。

教材出处

• 希尔排序的基本思想（从"减少记录个数"和"序列基本有序"两方面改进直接插入排序）、算法步骤与算法描述（算法 8.3）、以 $\{49,38,65,97,76,13,27,49,55,04\}$ 为例、增量取 5、3、1 的逐趟过程（图 8.2）：严蔚敏《数据结构（C 语言版）》（第 2 版），p239–p241
• "希尔排序的时间复杂度是所取'增量'序列的函数，这涉及一些数学上尚未解决的难题"；"当增量序列为 $d_k=2^{t-k+1}-1$ 时，希尔排序的时间复杂度为 $O(n^{3/2})$"；"当 $n$ 在某个特定范围内，希尔排序所需的比较和移动次数约为 $n^{1.3}$"；空间复杂度 $O(1)$：同书 p241
• 算法特点："记录跳跃式地移动导致排序方法是不稳定的"；"只能用于顺序结构，不能用于链式结构"；"增量序列可以有各种取法，但应该使增量序列中的值没有除 1 之外的公因子，并且最后一个增量值必须等于 1"；"适合初始记录无序、$n$ 较大时的情况"：同书 p241
• "折半插入排序、希尔排序、快速排序和堆排序难于在链表上实现"：同书 p269

相关知识

直接插入排序（每一趟就是"步长为 $d$ 的插入排序"）｜ 折半插入排序（另一条改进路线：优化比较 vs 优化移动）｜ 排序的基本概念｜ 快速排序｜堆排序（同样因跨距离交换而不稳定、同样需要随机存取）｜ 由中间状态反推排序算法｜ 排序算法对比

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2025Q112分2023Q102分2018Q102分2015Q112分2014Q102分