希尔排序 → 缩步插缝法 超详细讲解

前置基础：插入排序 → 插缝排队法

希尔排序是插入排序的优化版，所有核心逻辑都建立在插入排序之上。先搞懂插入排序，希尔排序就能一眼看懂。

核心思想

插入排序的逻辑和我们打扑克牌理牌完全一致：把数组分成「已排序区」和「未排序区」，每次从未排序区拿出第一个元素，向前插到已排序区的正确位置，直到所有元素都插入完成。

因为核心动作是「找缝隙插入」，所以也叫「插缝排队法」。

执行步骤（逐轮演示）

以数组[8, 3, 5, 1, 2]为例：

1. 初始状态：已排序区只有第一个元素[8]，未排序区[3, 5, 1, 2]
2. 取出未排序第一个元素 3：和已排序区的 8 比较，3<8，8 后移，3 插到最前面 已排序区变为[3, 8]
3. 取出未排序第一个元素 5：和 8 比较，5<8，8 后移；再和 3 比较，5>3，插到 3 后面 已排序区变为[3, 5, 8]
4. 取出未排序第一个元素 1：依次和 8、5、3 比较，全部后移，1 插到最前面 已排序区变为[1, 3, 5, 8]
5. 取出最后一个元素 2：向前比较找到位置，插入完成 最终有序数组：[1, 2, 3, 5, 8]

C++ 完整代码

cpp

运行

void insertionSort(vector<int>& nums) { int n = nums.size(); // 从第二个元素开始，逐个插入到前面的有序区 for (int i = 1; i < n; i++) { int temp = nums[i]; // 保存当前待插入的元素 int j; // 向前遍历有序区，比temp大的元素全部后移，腾出位置 for (j = i; j > 0 && nums[j - 1] > temp; j--) { nums[j] = nums[j - 1]; } nums[j] = temp; // 元素插入到正确缝隙 } }

核心特点（理解希尔排序的关键）

1. 优点：当数组基本有序时，效率极高，接近 O (n)。因为每个元素只需要移动很少几步就能找到位置，内层循环很快结束。
2. 缺点：当数组完全乱序、且小元素都在数组末尾时，效率极低 O (n²)。比如最小的元素在最后一位，它需要一步步往前挪 n-1 次，才能到最前面。
3. 空间复杂度 O (1)，是稳定排序（相等元素不会交换相对顺序）。

希尔排序的优化思路，正是精准命中了插入排序的缺点：先用大步长让末尾的小元素 “跳” 到前面，让数组快速变得基本有序，最后再用步长为 1 的普通插入排序收尾。

---

一、希尔排序核心思想

理解了插入排序，希尔排序就非常好懂 —— 它就是插入排序的「大步长预排序 + 最终精细排序」优化版，也就是「缩步插缝法」。

核心逻辑：

1. 先按较大的步长把数组分成多组，每组内做插入排序，让数组先 “大概有序”
2. 不断缩小步长重复分组排序，让数组越来越有序
3. 直到步长缩为 1，此时数组已经高度有序，最后做一次普通插入排序即可完成

为什么这样会更快？

• 大步长阶段：末尾的小元素一次就能 “跳” 很远，快速挪到靠前的位置，避免了一步步前移的低效操作
• 步长 = 1 阶段：数组已经基本有序，插入排序的优点被完全发挥，收尾极快

---

二、完整执行步骤（附逐轮演示）

通用执行流程

1. 设定初始步长：通常取数组长度的一半gap = n / 2
2. 分组插入排序：所有下标相差gap的元素归为一组，每组内分别执行插入排序
3. 缩小步长：一般按gap = gap / 2减半，重复第 2 步
4. 终止条件：当gap = 1时，整个数组为一组，执行最后一次插入排序，排序完成

逐轮实例演示

以数组[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]为例，数组长度 n=10。

第 1 轮：初始步长 gap = 5

按下标间隔 5 分组，共分成 5 组：

• 组 1：下标 0、5 → 元素8, 3
• 组 2：下标 1、6 → 元素9, 5
• 组 3：下标 2、7 → 元素1, 4
• 组 4：下标 3、8 → 元素7, 6
• 组 5：下标 4、9 → 元素2, 0

每组内做插入排序（升序）：

• 组 1 排序后：3, 8
• 组 2 排序后：5, 9
• 组 3 排序后：1, 4（已有序）
• 组 4 排序后：6, 7
• 组 5 排序后：0, 2

第 1 轮结束后数组变为：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

观察：原本在末尾的 0、2 这些小数，一次就跳到了数组前半段，这就是大步长的价值。

第 2 轮：步长缩小 gap = 2

按下标间隔 2 分组，共分成 2 组：

• 偶数组：下标 0、2、4、6、8 → 元素3, 1, 0, 9, 7
• 奇数组：下标 1、3、5、7、9 → 元素5, 6, 8, 4, 2

每组内做插入排序：

• 偶数组排序后：0, 1, 3, 7, 9
• 奇数组排序后：2, 4, 5, 6, 8

第 2 轮结束后数组变为：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]此时数组已经基本有序，只有少量元素位置不对。

第 3 轮：步长缩为 gap = 1

步长为 1 时，整个数组就是一组，执行普通插入排序。因为数组已经接近有序，每个元素只需要移动 1-2 步就能归位，极快完成： 最终排序结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

---

三、C++ 完整代码实现

cpp

运行

#include <vector> #include <iostream> using namespace std; // 希尔排序（缩步插缝法） void shellSort(vector<int>& nums) { int n = nums.size(); // 外层循环：不断缩小步长 gap for (int gap = n / 2; gap > 0; gap /= 2) { // 中层+内层：分组执行插入排序 // 和普通插入排序代码几乎完全一样，只是把步长 1 换成了 gap for (int i = gap; i < n; i++) { int temp = nums[i]; // 保存当前待插入的元素 int j; // 组内向前找插入位置，每次向前跳 gap 步 for (j = i; j >= gap && nums[j - gap] > temp; j -= gap) { nums[j] = nums[j - gap]; // 元素后移，腾出插入位置 } nums[j] = temp; // 元素插入到合适位置 } } } // 测试用例 int main() { vector<int> nums = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; shellSort(nums); for (int num : nums) { cout << num << " "; } // 输出：0 1 2 3 4 5 6 7 8 9 return 0; }

代码对照：把上面代码里的gap全部换成1，它就变成了标准的插入排序。两者的核心逻辑完全一致，希尔排序只是多了一层步长循环。

---

四、复杂度与核心特性

1. 时间复杂度

• 平均情况：约O(n^1.3)，远优于普通插入排序的 O (n²)
• 最坏情况：O(n²)（步长选择极差时，比如步长序列不合理）
• 实际效率和步长序列强相关：原始希尔步长（n/2 减半）最简单但不是最优；Knuth 步长序列（gap = 3*gap + 1反向递减）综合性能更好。

2. 空间复杂度

O(1)，纯原地排序，只需要几个临时变量，无额外空间开销。

3. 稳定性

不稳定排序。 原因：分组跨距交换时，值相等的元素可能被分到不同组，排序后相对顺序可能被打乱。

4. 适用场景

• 中等规模数据排序，实现简单，空间开销极低
• 数据量不是极大时，综合表现优秀，常作为嵌入式、单片机场景的排序方案
• 是对插入排序的 “低成本优化”，代码只需要在插入排序外套一层步长循环即可

---

五、关键细节理解

1. 为什么不直接用插入排序？普通插入排序每次只能移动 1 位，乱序数组下末尾的小元素要一步步往前挪很多次；希尔排序通过大步长让元素一次 “跳” 很远，快速把元素挪到大致正确的位置，最后微调成本极低。

2. 步长必须是减半吗？不是。减半只是最经典、最简单的写法，步长序列可以自定义，只要最终收敛到 1 即可。更优的步长序列能进一步降低最坏时间复杂度。

3. 和其他排序的对比

• 比插入排序快，代码复杂度相近
• 比快速排序、归并排序实现简单，空间开销更小，但平均效率略低
• 适合作为 “轻量级排序方案” 使用

谢谢