目录一、直接插入排序1.1 算法思想1.2 代码实现1.3 运行推演1.4 复杂度分析二、折半插入排序2.1 算法思想2.2 代码实现2.3 运行推演2.4 复杂度分析三、希尔排序3.1 算法思想3.2 代码实现3.3 运行推演3.4 复杂度分析前言 插入排序是最古老、最直观的排序思想之一。它的基本逻辑类似于我们整理扑克牌手中的牌保持有序每摸到一张新牌就向手牌中已排序的区域插入正确的位置。本文将以直接插入排序为起点逐步引入折半查找优化和希尔排序的分组预排序思想结合完整可运行的C代码、控制台输出日志与逐行解析彻底讲透插入排序家族。一、直接插入排序1.1 算法思想直接插入排序的核心思维是“有序区 无序区”。初始状态下将数组的第一个元素视为已排序区间剩余部分视为无序区间。每一趟排序从无序区间取出第一个元素在已排序区间中从后向前扫描找到合适的位置并插入。在寻找位置的过程中算法采取“边比较、边后移”的策略当已排序区间中的元素大于待插入元素时将该元素向后移动一位直到遇到第一个小于或等于待插入元素的位置将待插入元素放入该位置的后方。1.2 代码实现voidInsertSort(DataType a[],intn){inti,j;DataType x;for(i1;in;i){//先跟a[i-1]比较比a[i-1]小则继续向前比较if(a[i]a[i-1]){xa[i];//直到找到比x小的数即停止for(ji-1;j0a[j]x;--j){a[j1]a[j];//比其大的数向后挪动一位}a[j1]x;//将x放在合适位置}}}代码解析外层for循环从i 1开始意思是将第 0 个元素看作初始有序区从第 1 个元素开始逐个插入。if (a[i] a[i - 1])是一个重要的短路判断如果当前待插入元素已经比有序区的最后一个元素大说明它本来就处于正确位置直接跳过这能显著优化对近乎有序数组的性能。内层for循环同时完成了“查找”与“挪位”从i-1位置向前扫描只要a[j] x就把a[j]后移一位当循环退出时j指向了第一个不大于x的元素此时将x放入j1位置插入完成。1.3 运行推演初始数据4 6 3 2 8 0 1 10 5 4状态日志每趟排序后的数组4 6 3 2 8 0 1 10 5 4 3 4 6 2 8 0 1 10 5 4 2 3 4 6 8 0 1 10 5 4 2 3 4 6 8 0 1 10 5 4 0 2 3 4 6 8 1 10 5 4 0 1 2 3 4 6 8 10 5 4 0 1 2 3 4 6 8 10 5 4 0 1 2 3 4 5 6 8 10 4 0 1 2 3 4 4 5 6 8 10 0 1 2 3 4 4 5 6 8 10步骤解析 以元素0的插入过程为例。第四趟结束时的数组为2 3 4 6 8 0 ...此时0前面是已经有序的2,3,4,6,8。a[5]0明显小于a[4]8触发插入逻辑。x保存为0内层循环从下标 4 开始向前比较a[4]8 0后移a[3]6后移a[2]4后移a[1]3后移a[0]2后移当j减为 -1 时循环终止。最终将0放入下标 0 的位置。可以看到0一步一步被挪到了数组头部这形象地体现了“边比较边移动”的核心机制。1.4 复杂度分析时间复杂度最好情况数组完全有序内层循环永不执行仅需外层遍历一趟O ( n ) O(n)O(n)。最坏情况数组完全逆序每一趟都需要将有序区的所有元素后移总比较与移动次数约为n ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1)​为O ( n 2 ) O(n^2)O(n2)。平均情况O ( n 2 ) O(n^2)O(n2)。空间复杂度 只使用了常数级辅助变量x、i、jO ( 1 ) O(1)O(1)。稳定性 稳定。当遇到相等的元素时判断条件a[j] x会阻止进一步移动因此相同元素的前后顺序不会改变。二、折半插入排序2.1 算法思想直接插入排序在查找插入位置时采用顺序查找效率较低。折半插入排序引入二分查找法在“已排序区间”内快速定位插入点减少了元素比较次数。然而元素的物理移动仍然无法避免整体移动开销不变。2.2 代码实现voidBInsertSort(DataType a[],intn){intlow,high,mid,i;DataType x;for(i1;in;i){xa[i];low0;highi-1;while(lowhigh){midlow(high-low)/2;//防溢出写法if(a[mid]x){highmid-1;//从左半部分继续找}else{lowmid1;//从右半部分继续找}}for(intji-1;jhigh1;--j){a[j1]a[j];//找到合适位置后该位置后的元素都向后挪动一位}a[high1]x;//插入到合适位置}}代码解析二分查找的经典写法中mid low (high - low) / 2是一种防御性编程技巧可以避免low high可能发生的整型溢出。当while(low high)退出时high指针总是停留在最后一个小于等于x的元素的位置上或 -1。因此插入位置就是high 1。后续的for循环将high1到i-1之间的所有元素统一后移一位然后放入x。将查找与移动两个阶段明确分离。2.3 运行推演状态日志4 6 3 2 8 0 1 10 5 4 3 4 6 2 8 0 1 10 5 4 2 3 4 6 8 0 1 10 5 4 2 3 4 6 8 0 1 10 5 4 0 2 3 4 6 8 1 10 5 4 0 1 2 3 4 6 8 10 5 4 0 1 2 3 4 6 8 10 5 4 0 1 2 3 4 5 6 8 10 4 0 1 2 3 4 4 5 6 8 10 0 1 2 3 4 4 5 6 8 10步骤解析 以插入1为例此时有序区为0,2,3,4,6,8。二分查找过程low0,high5mid2(a[2]3 1high1)mid0(a[0]0 1low1)mid1(a[1]2 1high0)循环结束。最终插入位置high1 1。将a[1..5]的元素整体后移把1放入a[1]。相比直接插入排序比较次数明显减少但移动次数完全相同。2.4 复杂度分析时间复杂度 二分查找将比较次数降为O ( n log ⁡ n ) O(n \log n)O(nlogn)但元素移动仍需O ( n 2 ) O(n^2)O(n2)总体时间复杂度依然是O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( 1 ) O(1)O(1)。稳定性 稳定。二分查找过程中当a[mid] x时low mid 1保证了相等元素不会交换前后顺序。三、希尔排序3.1 算法思想希尔排序是对直接插入排序在效率上的革命性改进。它基于“缩小增量”的思想先将整个待排序列按某个增量gap划分为若干子序列对每个子序列分别进行直接插入排序然后逐步缩小gap重复上述过程直至gap 1时整个序列已基本有序最后一次直接插入排序就能以近乎线性的代价完成。其精妙之处在于当gap较大时元素可以一次跳跃多个位置让较小的元素快速移动到数组前端达到宏观有序的效果随着gap减小数组的局部有序性已经建立插入排序的移动次数大幅降低。3.2 代码实现voidShellSort(DataType a[],intn){// 1. 初始化步长 gap通常初始设为数组长度的一半// 每次循环步长减半直到步长为 1for(intgapn/2;gap0;gap/2){// 2. 从第 gap 个元素开始依次将其插入到其所在的子序列中// 这层循环的作用就相当于直接插入排序中的 for(i1; in; i)for(intigap;in;i){inttempa[i];// 暂存当前准备插入的元素 (不使用哨兵 A[0])intji;// 3. 在当前子序列中从后往前找插入位置// 每次比较的距离不是 1而是 gap// 注意边界条件j gap防止 arr[j - gap] 越界while(jgapa[j-gap]temp){a[j]a[j-gap];// 如果前面的元素更大则将其向后移 gap 个位置j-gap;// 继续往前跳 gap 个位置比较}// 4. 将暂存的元素放入最终找到的位置a[j]temp;}}}代码解析最外层循环for (int gap n / 2; gap 0; gap / 2)采用经典的希尔增量序列每次将步长折半。中层循环for (int i gap; i n; i)含义深远它不是简单的分组后单独处理每个子序列而是使用i交替扫描各个分组相当于把多个插入排序交错执行。这种方式代码简洁且缓存友好。最内层while就是经典的直接插入排序逻辑只不过比较和移动的步长变成了gap边界检查也变成了j gap。这种结构本质上是将直接插入排序中步长为 1 的比较扩展为步长为gap的比较当gap 1时完全退化回原始的插入排序。3.3 运行推演初始数据4 6 3 2 8 0 1 10 5 4状态日志gap是 5: 0 1 3 2 4 4 6 10 5 8 gap是 2: 0 1 3 2 4 4 5 8 6 10 gap是 1: 0 1 2 3 4 4 5 6 8 10步骤解析 当gap5时数组被分为 5 组(4,0), (6,1), (3,10), (2,5), (8,4)。对每组执行插入排序后最小的元素 0 瞬间从索引 5 跃迁到索引 01 也移动到前面首轮便实现了数组的“宏观有序”。当gap2时进一步消除中距离的逆序最后gap1时仅需少量移动即完成最终排序。这诠释了希尔排序“跨大步调整小步精修”的核心哲学。3.4 复杂度分析时间复杂度 强烈依赖于增量序列的选择。使用希尔增量n/2不断折半时复杂度约在O ( n 1.3 ) O(n^{1.3})O(n1.3)到O ( n 1.5 ) O(n^{1.5})O(n1.5)之间最坏情况退化到O ( n 2 ) O(n^2)O(n2)。采用 Hibbard 等更优增量序列可稳定在O ( n 1.3 ) O(n^{1.3})O(n1.3)左右。空间复杂度O ( 1 ) O(1)O(1)。稳定性 不稳定。相同元素可能被分入不同的增量分组在各自排序后原有的相对顺序可能被打乱。下一篇将继续剖析交换排序冒泡排序与快速排序敬请关注。