文章目录1. 插入排序1.1 基本思想1.2 直接插入排序1.2.1代码实现1.2.2 代码讲解1.2.3 复杂度1.2.4 直接插入排序优化折半插入排序2.2 希尔排序(插入排序的升级版比较难理解)2.2.1 直接插入排序最大的弊端2.3 希尔排序完整代码2.3.1 代码讲解2.3 复杂度与稳定性详细分析2.3.1 时间复杂度2.3.2**空间复杂度**2.4 全文总结1. 插入排序1.1 基本思想直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想1.2 直接插入排序当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移流程下一个数跟前面的一个进行比较如果大于的话前面一个数前移然后继续进行比较直到找到比他小的数然后插入。1.2.1代码实现以下代码以升序排序为例包含完整的排序函数、测试用例和运行结果可直接编译运行#includestdio.h// 直接插入排序升序voidInsertSort(intarr[],intn){// 1. 外层循环控制待插入元素无序区间的起始位置// 数组第一个元素arr[0]默认是有序区间从第二个元素arr[1]开始逐个处理for(inti1;in;i){// 2. 保存待插入元素// 这里必须先存起来后面元素后移时会覆盖arr[i]不保存就会丢失数据intinsertValarr[i];// 3. 定义有序区间的末尾下标intji-1;// 4. 内层循环从有序区间末尾向前遍历寻找插入位置// 循环条件j不越界且有序区间当前元素比待插入元素大需要继续往前找while(j0arr[j]insertVal){// 元素后移把比待插入元素大的元素往后挪一位腾出位置arr[j1]arr[j];j--;// 继续向前比对}// 5. 插入元素循环结束时j1就是待插入元素的正确位置arr[j1]insertVal;}}// 打印数组函数voidPrintArr(intarr[],intn){for(inti0;in;i){printf(%d ,arr[i]);}printf(\n);}// 测试主函数intmain(){// 测试用例包含重复元素、无序数据intarr[]{49,38,65,97,76,13,27,49};intnsizeof(arr)/sizeof(arr[0]);printf(排序前数组);PrintArr(arr,n);InsertSort(arr,n);printf(排序后数组);PrintArr(arr,n);return0;}运行结果排序前数组4938659776132749排序后数组13273849496576971.2.2 代码讲解1. 外层循环为什么从i1开始直接插入排序默认数组的第一个元素arr[0]是有序区间所以我们只需要从第二个元素下标1开始逐个处理无序区间的元素。每一次循环i代表无序区间的起始下标有序区间的范围是[0, i-1]循环结束时i会遍历到数组末尾整个数组都会变成有序区间2. 保存待插入元素为什么要定义insertVal这是代码里最关键的细节之一。当我们执行arr[j 1] arr[j]时会把有序区间的元素向后移动一位而arr[i]本身就是无序区间的第一个元素移动过程中arr[i]的值会被覆盖。如果不提前保存最后插入的时候就会丢失原本的待插入元素导致排序结果错误。3. 内层循环为什么从有序区间末尾向前遍历从后往前遍历的好处是一旦找到比待插入元素小的元素它的下一个位置就是插入位置不需要遍历整个有序区间减少不必要的比较次数循环条件j 0是为了防止数组下标越界避免访问arr[-1]这种非法地址4. 元素后移与插入位置为什么最终插入arr[j1]当内层循环结束时有两种情况情况 1j 0说明找到了比insertVal小的元素此时j指向的元素是有序区间中第一个比insertVal小的元素j1就是待插入的位置情况 2j 0说明待插入元素比有序区间所有元素都小此时j1 0正好是数组的开头位置两种情况都满足arr[j1] insertVal所以这一步可以统一处理。1.2.3 复杂度1. 时间复杂度最好情况数组已有序时间复杂度为O(n)此时内层循环的条件arr[j] insertVal永远不成立不会执行元素后移操作算法只需遍历一次数组即可完成排序最坏情况数组逆序时间复杂度为O(n²)每个元素都需要和前面所有有序区间的元素比较并移动总比较次数为n(n-1)/2移动次数也为n(n-1)/2平均情况时间复杂度为O(n²)2. 空间复杂度直接插入排序是原地排序算法只使用了常数级别的额外空间insertVal、i、j等变量空间复杂度为O(1)。3. 稳定性直接插入排序是稳定排序算法。代码中我们的比较条件是arr[j] insertVal只有当有序区间的元素严格大于待插入元素时才会后移不会移动和待插入元素相等的元素因此重复元素的相对位置不会改变。比如测试用例中的两个49排序后它们的先后顺序和原数组保持一致。1.2.4 直接插入排序优化折半插入排序直接插入排序的核心耗时在「元素比较」和「元素移动」上其中元素移动的次数无法减少但比较次数可以优化。我们可以用 ** 折半查找二分查找** 来替代顺序查找快速找到待插入元素的位置减少比较次数这就是折半插入排序。voidBinaryInsertSort(intarr[],intn){for(inti1;in;i){intinsertValarr[i];intlow0,highi-1;// 折半查找插入位置while(lowhigh){intmid(lowhigh)/2;if(arr[mid]insertVal){highmid-1;}else{lowmid1;}}// 元素后移从low到i-1的元素都需要后移一位for(intji-1;jlow;j--){arr[j1]arr[j];}// 插入元素arr[low]insertVal;}}折半插入排序的时间复杂度仍然是O(n²)但减少了比较次数对于数据量较大的有序数组效率会有明显提升。2.2 希尔排序(插入排序的升级版比较难理解)前面我们已经完整学完了直接插入排序它逻辑简单、代码好写、稳定性强但有一个致命短板当数组无序程度很高、逆序元素多的时候每一个元素都要往前逐个比较、一步步后移元素移动次数极多效率非常低。那能不能想个办法让大的元素快速挪到后面、小的元素快速挪到前面不用一步一步慢慢挪基于这个思路希尔排序诞生了。希尔排序本质就是对直接插入排序的极致优化也叫缩小增量排序。2.2.1 直接插入排序最大的弊端直接插入排序是相邻元素逐个移动步长只能是 1比如一个很小的数在数组最后面它要一步一步往前挪和前面每一个元素比较、逐个后移移动次数太多、效率极低。它只适合两种场景数据量很小数组本身已经接近有序一旦数据乱序、逆序严重直接插入排序就会变得非常慢。引入间隔 Gap 的核心目的我们设置一个间隔增量 Gap把相隔 Gap 距离的元素分为一组元素不再一步一步挪而是跨越式移动小元素可以直接跳到前面大元素直接甩到后面不用逐个相邻比较一次性把远距离的逆序先调整好一句话设置间隔就是为了让元素实现「跳跃式移动」提前把数组调成基本有序避免后期大量逐个挪动。为什么间隔要从大到小最后缩小到 1一.初始 Gap 很大分组少、每组元素少能快速把远距离的乱序元素调整到位宏观上把数组捋顺。二.逐步缩小 Gap间隔变小分组变多每组元素变多在前面宏观有序的基础上做精细化微调。三.最后 Gap 必须等于 1当 Gap1 时就是标准的直接插入排序。但此时数组经过前面多轮跳跃调整已经接近有序而直接插入排序在数组接近有序时效率是最高的。这就是希尔排序的精髓先粗调、后细调大间隔宏观整理小间隔精细收尾。2.3 希尔排序完整代码#includestdio.h// 希尔排序voidShellSort(intarr[],intn){// 1. 初始增量设为数组长度一半intgapn/2;// 增量不断缩小直到间隔为0停止while(gap0){// 从下标gap开始对每个分组做直接插入排序for(intigap;in;i){// 保存当前待插入元素防止后移被覆盖inttemparr[i];// 同组内前一个元素的下标intji-gap;// 组内向前比较比temp大的元素向后跨越式移动while(j0arr[j]temp){arr[jgap]arr[j];jj-gap;}// 把元素放到正确位置arr[jgap]temp;}// 增量减半缩小间隔gapgap/2;}}// 打印数组voidPrintArray(intarr[],intn){for(inti0;in;i){printf(%d ,arr[i]);}printf(\n);}intmain(){intarr[]{9,5,1,8,2,7,3,6,4};intlensizeof(arr)/sizeof(arr[0]);printf(排序前);PrintArray(arr,len);ShellSort(arr,len);printf(排序后);PrintArray(arr,len);return0;}2.3.1 代码讲解增量循环:while(gap0)只要间隔还大于 0就继续分组排序直到间隔变为 1 做完最后一轮再缩到 0 结束。遍历每个分组元素for(intigap;in;i)和直接插入排序 i1 很像直插从第 2 个元素开始步长 1希尔排序从下标 gap 开始步长仍是 1但比较和移动的跨度是 gap暂存待插入元素inttemparr[i];和直接插入排序完全一样必须先保存元素否则后面跨越式后移会把原值覆盖丢失。同组前驱下标:intji-gap;直接插入排序是 j i - 1希尔排序是 j i - gap。唯一区别往前找的步长从 1 变成了间隔 gap。组内元素后移:while(j0arr[j]temp){arr[jgap]arr[j];jj-gap;}直插arr[j1] arr[j]; j–希尔arr[jgap] arr[j]; j - gap逻辑一模一样只是移动跨度从相邻 1 格变成跳跃 Gap 格。希尔排序没有改变直接插入排序的核心逻辑只是加了分组 跳跃间隔解决了直插在乱序数据下移动次数过多的痛点。2.3 复杂度与稳定性详细分析2.3.1 时间复杂度采用 gap gap/2 增量规则平均时间复杂度 O (n¹・³)最坏时间复杂度依然是 O (n²)但实际运行效率远高于直接插入排序数组越接近有序希尔排序效率越高2.3.2空间复杂度仅使用 gap、i、j、temp 临时变量没有开辟额外数组空间复杂度 O (1)属于原地排序算法。2.4 全文总结希尔排序是直接插入排序的优化升级版专门解决直插乱序数据效率低的问题引入间隔 Gap 的目的实现元素跳跃移动提前宏观整理数组间隔从大到小先粗调、后细调最后 gap1 回归直接插入排序收尾代码和直插高度相似仅把步长 1 改成步长 gap学习成本极低原地排序、效率更高但丧失了稳定性适合不要求保序的中等规模数据排序。