前置基础插入排序 → 插缝排队法希尔排序是插入排序的优化版所有核心逻辑都建立在插入排序之上。先搞懂插入排序希尔排序就能一眼看懂。核心思想插入排序的逻辑和我们打扑克牌理牌完全一致把数组分成「已排序区」和「未排序区」每次从未排序区拿出第一个元素向前插到已排序区的正确位置直到所有元素都插入完成。因为核心动作是「找缝隙插入」所以也叫「插缝排队法」。执行步骤逐轮演示以数组[8, 3, 5, 1, 2]为例初始状态已排序区只有第一个元素[8]未排序区[3, 5, 1, 2]取出未排序第一个元素 3和已排序区的 8 比较388 后移3 插到最前面 已排序区变为[3, 8]取出未排序第一个元素 5和 8 比较588 后移再和 3 比较53插到 3 后面 已排序区变为[3, 5, 8]取出未排序第一个元素 1依次和 8、5、3 比较全部后移1 插到最前面 已排序区变为[1, 3, 5, 8]取出最后一个元素 2向前比较找到位置插入完成 最终有序数组[1, 2, 3, 5, 8]C 完整代码cpp运行void insertionSort(vectorint 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; // 元素插入到正确缝隙 } }核心特点理解希尔排序的关键优点当数组基本有序时效率极高接近 O (n)。因为每个元素只需要移动很少几步就能找到位置内层循环很快结束。缺点当数组完全乱序、且小元素都在数组末尾时效率极低 O (n²)。比如最小的元素在最后一位它需要一步步往前挪 n-1 次才能到最前面。空间复杂度 O (1)是稳定排序相等元素不会交换相对顺序。希尔排序的优化思路正是精准命中了插入排序的缺点先用大步长让末尾的小元素 “跳” 到前面让数组快速变得基本有序最后再用步长为 1 的普通插入排序收尾。一、希尔排序核心思想理解了插入排序希尔排序就非常好懂 —— 它就是插入排序的「大步长预排序 最终精细排序」优化版也就是「缩步插缝法」。核心逻辑先按较大的步长把数组分成多组每组内做插入排序让数组先 “大概有序”不断缩小步长重复分组排序让数组越来越有序直到步长缩为 1此时数组已经高度有序最后做一次普通插入排序即可完成为什么这样会更快大步长阶段末尾的小元素一次就能 “跳” 很远快速挪到靠前的位置避免了一步步前移的低效操作步长 1 阶段数组已经基本有序插入排序的优点被完全发挥收尾极快二、完整执行步骤附逐轮演示通用执行流程设定初始步长通常取数组长度的一半gap n / 2分组插入排序所有下标相差gap的元素归为一组每组内分别执行插入排序缩小步长一般按gap gap / 2减半重复第 2 步终止条件当gap 1时整个数组为一组执行最后一次插入排序排序完成逐轮实例演示以数组[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]为例数组长度 n10。第 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(vectorint 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() { vectorint 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 即可。更优的步长序列能进一步降低最坏时间复杂度。和其他排序的对比比插入排序快代码复杂度相近比快速排序、归并排序实现简单空间开销更小但平均效率略低适合作为 “轻量级排序方案” 使用谢谢