Appearance
希尔排序
为什么需要希尔排序
直接插入排序在序列基本有序时效率很高，可以达到 O(n)；但当序列逆序或随机分布时，每次插入都需要大量移动元素，退化为 O(n²)。
希尔排序（Shell Sort）的思路是：先让序列宏观上趋于有序，再对整体做一次插入排序。通过将序列按一定增量分组，对每组分别进行插入排序，随着增量逐步缩小，整个序列越来越接近有序，最终增量为 1 时完成排序。这就是"缩小增量排序"名称的由来。
核心思想
希尔排序的核心特点：
- 缩小增量：选定一个增量序列 d₁ > d₂ > … > dₖ = 1，每趟按当前增量 dᵢ 将序列划分为若干子序列
- 分组插入：对每个子序列执行直接插入排序，使元素能跨越较大距离移动到接近最终位置
- 逐步逼近有序：增量不断缩小，子序列越来越长、序列越来越有序，最后一趟 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]
d=2: 分组 {3,1,8,2} {5,6,7,9} → 各组插入排序
[1, 5, 2, 6, 3, 7, 8, 9]
d=1: 整体插入排序（此时序列已基本有序，移动次数很少）
[1, 2, 3, 5, 6, 7, 8, 9]交互可视化
通过下方的交互动画，你可以逐步观察希尔排序的执行过程：
操作详解
算法思路
- 选择一个增量序列，初始增量 d = n/2（或其他方案）
- 按增量 d 将序列分为 d 组：下标为 {0, d, 2d, …}、{1, 1+d, 1+2d, …} 等
- 对每组执行直接插入排序
- 缩小增量 d = d/2，重复步骤 2-3
- 直到 d = 1，完成最后一趟排序
cpp
void ShellSort(int A[], int n) {
// d 为增量，每次减半
for (int d = n / 2; d >= 1; d /= 2) {
// 从第 d 个元素开始，对每个子序列做插入排序
for (int i = d; i < n; i++) {
int temp = A[i];
int j = i - d;
// 在当前子序列中找到插入位置
while (j >= 0 && A[j] > temp) {
A[j + d] = A[j];
j -= d;
}
A[j + d] = temp;
}
}
}注意：代码中并没有显式地"分组再分别排序"，而是用一个循环交替处理各组元素，效果等价但写法更简洁。
增量序列
增量序列的选择直接影响希尔排序的时间复杂度，408 常见的有以下几种：
| 增量序列 | 公式 | 示例（n=16） | 最坏时间复杂度 |
|---|---|---|---|
| Shell 原始序列 | dᵢ = n/2ⁱ | 8, 4, 2, 1 | O(n²) |
| Hibbard 序列 | dᵢ = 2ⁱ - 1 | 15, 7, 3, 1 | O(n^1.5) |
| Knuth 序列 | dᵢ = (3ⁱ - 1)/2 | 13, 4, 1 | O(n^1.5) |
⭐ 考试默认使用 Shell 原始序列（d = n/2, n/4, …, 1），除非题目另有说明。
⭐ 增量序列必须满足的条件：最后一个增量必须为 1（否则无法保证排序完成）。
排序过程详解
以序列 [49, 38, 65, 97, 76, 13, 27, 49*]（n=8）为例，使用 Shell 原始增量序列。其中 49* 用于标注第二个 49 以观察稳定性。
第一趟 d=4：分为 4 组
组1: A[0]=49, A[4]=76 → 49, 76（无交换）
组2: A[1]=38, A[5]=13 → 13, 38
组3: A[2]=65, A[6]=27 → 27, 65
组4: A[3]=97, A[7]=49* → 49*, 97结果：[49, 13, 27, 49*, 76, 38, 65, 97]
第二趟 d=2：分为 2 组
组1: A[0]=49, A[2]=27, A[4]=76, A[6]=65
→ 插入排序后: 27, 49, 65, 76
组2: A[1]=13, A[3]=49*, A[5]=38, A[7]=97
→ 插入排序后: 13, 38, 49*, 97结果：[27, 13, 49, 38, 65, 49*, 76, 97]
第三趟 d=1：整体插入排序
结果：[13, 27, 38, 49, 49*, 65, 76, 97]
⭐ 观察两个 49 的最终位置：原始序列中 49 在 49* 前面，排序后 49 仍在 49* 前面——看似稳定，但这只是巧合。在 d=4 那趟中，49* 被移动到了 49 前面（下标 3 < 下标 0 的后续位置），后续又被调回。不同增量序列或不同数据下，相同元素的相对顺序可能被打乱。 因此希尔排序是不稳定的排序算法。
复杂度分析
| 指标 | 结果 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(n^1.3) | 经验值，取决于增量序列 |
| 最坏时间复杂度 | O(n²) | 使用 Shell 原始增量序列时 |
| 平均时间复杂度 | 约 O(n^1.3) | 数学上未完全解决，考试记此值 |
| 空间复杂度 | O(1) | 仅需常数级辅助变量 |
| 稳定性 | 不稳定 | 跨子序列移动可能改变相同元素的相对顺序 |
| 适用性 | 仅适用于顺序表 | 需要按下标随机访问，链表无法使用 |
为什么不稳定？ 相同关键字的元素可能被分到不同子序列中，各子序列独立排序时，无法感知其他子序列中相同元素的位置，从而可能打乱它们的相对顺序。
与直接插入排序的对比：
| 对比项 | 直接插入排序 | 希尔排序 |
|---|---|---|
| 时间复杂度 | O(n²) | 约 O(n^1.3) |
| 稳定性 | 稳定 | 不稳定 |
| 适用场景 | 基本有序或 n 较小 | 中等规模数据 |
| 核心区别 | 每次移动一个位置 | 元素可跨越多个位置移动 |
考研高频考点
- ⭐ 给定序列和增量，写出每趟排序的结果（大题/选择题高频）
- ⭐ 希尔排序的稳定性判断及原因说明（选择题/简答题必考）
- ⭐ 增量序列的最后一个值必须为 1（判断题）
- ⭐ 时间复杂度与增量序列的关系：Shell 原始序列最坏 O(n²)，考试中平均记 O(n^1.3)
- ⭐ 希尔排序 vs 直接插入排序的联系与区别（简答题）
- 希尔排序不能用于链表（需要随机访问）
- 空间复杂度 O(1)，属于原地排序