很多人学 C 语言走到排序这一章第一反应就是背代码。尤其是冒泡排序名气太大几乎每本教材都要讲一遍导致不少初学者误以为“排序算法 冒泡排序”。等真正面试或者做算法题的时候发现冒泡排序在数据量稍大时慢得离谱这才回头重新研究其他排序。如果你也有类似困惑我的建议是C 语言入门阶段先彻底吃透插入排序而不是急着背冒泡排序。为什么因为插入排序的思想和生活经验最贴近代码量极小而且非常容易验证正确性。你只需要理解“整理扑克牌”的过程就能写出这个算法。更重要的是插入排序是理解更高级排序算法希尔排序、桶排序思想等的基础学好它后面会顺很多。这篇文章会从零开始用手工模拟、动画拆解、完整代码、时间复杂度和常见 bug 的方式帮你把直接插入排序彻底搞清楚。目标很明确30 分钟内你能独立写出没有 bug 的插入排序代码并且能解释清楚每一行代码为什么这么写。1. 插入排序到底解决什么问题先明确一个基本问题排序算法到底在干什么给你一个无序数组比如int arr[8] {5, 2, 9, 1, 5, 6, 3, 8};排序的目标很简单让数组从小到大排列变成{1, 2, 3, 5, 5, 6, 8, 9}这看起来太简单了简单到很多人觉得“这不就是调一个函数的事吗”。但在 C 语言学习阶段排序的意义不在于“把数组排好”而在于训练你三个核心能力循环边界控制数组下标从 0 开始循环条件什么时候是i n什么时候是i n - 1写错一个边界就是数组越界。元素移动思想插入排序的过程本质是“平移元素”这种思想在很多算法里都会用到。算法复杂度意识同样解决一个问题不同算法的效率差别巨大插入排序是最容易分析复杂度的算法之一。所以插入排序是 C 语言学习里一个性价比极高的知识点。它不只是让你会排一个数组而是让你第一次真正体会到“算法”这个词的含义。2. 插入排序的核心思想整理扑克牌先抛开代码想一个生活场景。你打扑克牌抓牌的时候会把牌一张张插到手里已经排好序的牌中。比如手里已经有3 5 8这时抓了一张6你会怎么放你会把8往后挪一位把6插到5和8之间变成3 5 6 8这个过程就是插入排序的本质。现在把场景翻译成数组操作数组的前一部分是“已经排好序的牌”。数组的后一部分是“还没抓上来的牌”。每一轮操作从“没排序的部分”取第一张牌往“已经排好序的部分”里插。插入的过程就是把比它大的元素往后挪空出位置再放进去。这就是“直接插入排序”Straight Insertion Sort。这个思想听起来简单但有一个细节很容易忽略在数组里“插入”一个元素不是直接塞进去而是要先把后面的元素往后挪。数组的内存是连续的没有“缝隙”可以让元素直接插进去。所以插入排序的全部操作本质上就是两件事从后往前比较找到插入位置。把插入位置之后的元素全部往后移一格。理解了这一点代码就不难写了。2.1 插入排序的三种叫法你可能见过“直接插入排序”“插入排序”“简单插入排序”这些名词。它们说的是同一个东西名称说明插入排序统称指这一类通过插入来排序的算法直接插入排序最基础的插入排序逐个向前比较并插入简单插入排序和直接插入排序是同一个意思强调它实现简单先掌握直接插入排序后面如果学到希尔排序你就能理解希尔排序是在直接插入排序基础上做了“分组优化”本质上还是插入思想。3. 动画级拆解一步一步看插入排序的过程这一节非常重要。很多人写不出插入排序的代码不是因为不会写 C 语言而是脑子里没有“排序过程”的动态画面。我们用一组数据把每一轮的比较和移动都列出来。假设数组是int arr[6] {4, 3, 2, 10, 5, 1};目标是排成升序从小到大。下面是完整过程注意看每一轮发生了什么。初始状态索引: 0 1 2 3 4 5 数值: 4 3 2 10 5 1我们规定索引 0 的元素即第一个元素 4已经是“手里排好序的牌”因为单独一个元素天然是有序的。所以从索引 1 开始逐个把后面的元素插入到前面有序区。第 1 轮插入元素 arr[1] 3当前状态有序区[4] 待插入3把 3 和有序区从后往前比较4 3所以 4 往后移一位。位置 0 空出来了把 3 放进去。结果索引: 0 1 2 3 4 5 数值: 3 4 2 10 5 1此时前两个元素3, 4有序。第 2 轮插入元素 arr[2] 2当前状态有序区[3, 4] 待插入2从后往前比较4 24 往后移一位。3 23 往后移一位。位置 0 空出把 2 放进去。结果索引: 0 1 2 3 4 5 数值: 2 3 4 10 5 1此时前三个元素2, 3, 4有序。第 3 轮插入元素 arr[3] 10当前状态有序区[2, 3, 4] 待插入10从后往前比较4 10不用移动。直接把 10 放在原位置。结果索引: 0 1 2 3 4 5 数值: 2 3 4 10 5 1这一轮其实什么都没变。原因很简单10 比有序区所有元素都大它已经在正确位置了。很多初学者会在这里犯嘀咕那这轮还算不算“插入”算。只是移动次数为 0。这也提醒我们插入排序对基本有序的数据移动次数很少。第 4 轮插入元素 arr[4] 5当前状态有序区[2, 3, 4, 10] 待插入5从后往前比较10 510 往后移一位。4 5停止移动。把 5 放到原来 10 的位置索引 3。结果索引: 0 1 2 3 4 5 数值: 2 3 4 5 10 1第 5 轮插入元素 arr[5] 1当前状态有序区[2, 3, 4, 5, 10] 待插入1从后往前比较10 110 往后移一位。5 15 往后移一位。4 14 往后移一位。3 13 往后移一位。2 12 往后移一位。位置 0 空出把 1 放进去。最终结果索引: 0 1 2 3 4 5 数值: 1 2 3 4 5 10排序完成。3.1 过程规律总结把上面五轮操作抽象出来规律非常清晰外层循环从索引i 1开始到i n - 1结束表示“当前要处理的元素”。把arr[i]暂存到一个变量里因为后面移动元素会覆盖它。内层循环从j i - 1开始从后往前扫描有序区。如果arr[j] 暂存值就把arr[j]移到arr[j 1]继续往前比较。如果arr[j] 暂存值说明找到插入位置停止移动把暂存值放到arr[j 1]。还有一种情况如果一直比到j 0说明暂存值比有序区所有元素都小应该放在数组开头也就是位置 0。这段规律直接翻译成 C 语言代码就是完整的插入排序。4. 完整代码基础版直接插入排序先看最标准的写法。这个版本不含哨兵逻辑最直观适合刚开始学习的阶段。// 文件路径insert_sort.c #include stdio.h // 直接插入排序升序 void insertSort(int arr[], int n) { int i, j, temp; for (i 1; i n; i) { temp arr[i]; // 暂存待插入元素 j i - 1; // 从有序区的最后一个元素开始比较 // 从后往前找插入位置比 temp 大的元素都往后移动 while (j 0 arr[j] temp) { arr[j 1] arr[j]; // 后移元素 j--; } arr[j 1] temp; // 把 temp 放到正确位置 } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {4, 3, 2, 10, 5, 1}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); insertSort(arr, n); printf(排序后); printArray(arr, n); return 0; }编译并运行gcc insert_sort.c -o insert_sort ./insert_sort预期输出排序前4 3 2 10 5 1 排序后1 2 3 4 5 10这段代码就是插入排序的标准形态请确保你能闭着眼睛写出来。4.1 核心代码逐行解释我们来解释一下最关键的四行逻辑temp arr[i];arr[i]就是这一轮要插入的元素。必须先存到临时变量里因为在后面的 while 循环中arr[j 1] arr[j]会从右往左覆盖元素如果不提前保存arr[i]的值会被覆盖掉数据就丢了。j i - 1;i - 1是有序区最后一个元素的下标。比如第 4 轮处理索引 4值是 5时有序区是[2, 3, 4, 10]最后一个元素是arr[3]也就是 10。所以j从 3 开始往前比较非常自然。while (j 0 arr[j] temp)这是整个算法的核心判断条件。它做了两件事j 0防止数组下标越界。如果一直往前比较到数组开头还没找到位置说明temp是当前最小的元素应该放在位置 0。arr[j] temp表示“前一个元素比待插入元素大”。这种情况下前一个元素必须往后挪给temp腾地方。特别注意条件里的顺序不能反。j 0必须写在前面。因为 C 语言的是短路运算一旦j 0成立后面的arr[j]根本不会执行这样就不会访问arr[-1]。arr[j 1] temp;循环结束后j指向的是最后一个不比temp大的元素所以temp应该放到j 1的位置。如果你直接把temp放到arr[j]就会漏掉一个位置或者把不该覆盖的元素覆盖掉。这个细节值得单独说一遍插入位置是 j 1不是 j。5. 亲自验证在循环中打印每一轮的排序结果光看最终输出很多人还是不太放心“排序过程中到底发生了什么”。这里提供一个加强版的代码它会在每一轮结束后打印当前数组状态方便你手动对照上文的动画级拆解。// 文件路径insert_sort_debug.c #include stdio.h void insertSortWithProcess(int arr[], int n) { int i, j, temp; for (i 1; i n; i) { temp arr[i]; j i - 1; while (j 0 arr[j] temp) { arr[j 1] arr[j]; j--; } arr[j 1] temp; // 打印当前第 i 轮结束后的数组状态 printf(第 %d 轮后, i); for (int k 0; k n; k) { printf(%d , arr[k]); } printf(\n); } } int main() { int arr[] {4, 3, 2, 10, 5, 1}; int n sizeof(arr) / sizeof(arr[0]); printf(初始数组); for (int k 0; k n; k) { printf(%d , arr[k]); } printf(\n); insertSortWithProcess(arr, n); printf(最终结果); for (int k 0; k n; k) { printf(%d , arr[k]); } printf(\n); return 0; }运行输出初始数组4 3 2 10 5 1 第 1 轮后3 4 2 10 5 1 第 2 轮后2 3 4 10 5 1 第 3 轮后2 3 4 10 5 1 第 4 轮后2 3 4 5 10 1 第 5 轮后1 2 3 4 5 10 最终结果1 2 3 4 5 10建议你运行这段代码对照上一节的手工模拟过程逐行比对。这一步能帮你把“抽象的循环”和“数组下标的变化”对应起来理解会立刻深入一层。6. 时间复杂度与稳定性分析排序算法不能只看“能不能排对”还要看“快不快”。插入排序的性能分析是重点也是面试中频繁考察的知识点。6.1 时间复杂度插入排序的核心操作有两个比较和移动。最坏情况数组完全逆序比如{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}。每一轮当前元素都要和前面所有元素比较一遍并且全部要往后移动。比较次数和移动次数都接近n^2 / 2所以时间复杂度是O(n²)。最好情况数组已经完全有序比如{1, 2, 3, 4, 5}。每一轮当前元素只需要比较一次因为前一个元素比它小不需要移动所以比较次数是n - 1移动次数是 0。时间复杂度是O(n)。平均情况时间复杂度是O(n²)。这里的结论非常有意思插入排序对“基本有序”的数据表现极好。如果数据本身已经接近有序插入排序会比很多 O(n²) 级别的排序算法快得多甚至接近 O(n)。正是这个特性让插入排序成为许多复杂排序算法的“最后一步收尾工具”比如快速排序在处理小规模子数组时有些实现会切换成插入排序。6.2 空间复杂度插入排序是原地排序只需要一个临时变量temp空间复杂度是O(1)。6.3 稳定性插入排序是稳定排序。什么叫稳定如果数组里有两个相等的元素比如{3, 5a, 5b, 1}其中5a和5b值相同但来自不同的原始位置稳定排序能保证排完序后5a仍然在5b前面。插入排序为什么稳定因为代码里的判断条件是arr[j] temp注意是“大于”不是“大于等于”。当遇到相等的元素时循环会停止temp被放到相等元素的后方不会跨过相等元素所以相同元素的相对顺序不会改变。6.4 三种情况小结情况比较次数移动次数时间复杂度最好已有序n - 10O(n)最坏逆序n²/2n²/2O(n²)平均随机约 n²/4约 n²/4O(n²)7. 插入排序的优化哨兵版本很多教材在讲插入排序时会提到一个优化版本使用“哨兵”来减少边界判断。先看原来的内层循环条件while (j 0 arr[j] temp)这里有j 0这个判断。每次循环都要检查一次虽然开销不大但理论上可以减少。优化思路是把temp暂存到arr[0]然后用arr[0]作为哨兵。这样即使temp比所有有序区元素都小循环到j 0时因为arr[0] temparr[j] temp不成立while 自然停止不需要额外判断j 0。不过要注意这种写法把数组下标为 0 的位置当作“缓存区”所以实际排序的数据要从下标 1 开始存放。如果你在竞赛或者教材中看到这种写法不要觉得奇怪。// 文件路径insert_sort_sentinel.c #include stdio.h // 带哨兵的插入排序arr[0] 作为哨兵实际数据从 arr[1] 开始 void insertSortWithSentinel(int arr[], int n) { // n 是待排序元素个数有效下标从 1 到 n int i, j; for (i 2; i n; i) { arr[0] arr[i]; // 哨兵暂存待插入元素 j i - 1; while (arr[j] arr[0]) { arr[j 1] arr[j]; j--; } arr[j 1] arr[0]; } } int main() { // 注意下标 0 是哨兵位不参与排序实际排序元素从下标 1 开始 int arr[7] {0, 4, 3, 2, 10, 5, 1}; int n 6; // 实际排序 6 个元素下标 1~6 printf(排序前); for (int i 1; i n; i) { printf(%d , arr[i]); } printf(\n); insertSortWithSentinel(arr, n); printf(排序后); for (int i 1; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }这个版本的优点在于内层 while 少了j 0的边界检查代码更精简理论上运行更快。缺点是理解难度稍高因为下标从 1 开始如果你刚接触指针和数组可能容易混淆。我的建议是先掌握最基础版本哨兵版本作为进阶理解。在实际工程项目中编译器对边界判断的优化已经很好了哨兵带来的性能提升并不明显更多是算法教材里用来训练思维。8. 插入排序 vs 冒泡排序 vs 选择排序C 语言入门时这三个算法经常被放在一起比较。用一个表格看懂它们的关键差异维度插入排序冒泡排序选择排序核心思想往有序区插入元素相邻元素交换大的沉底每轮选择最小的放前面最好时间复杂度O(n)O(n²)基础版O(n²)最坏时间复杂度O(n²)O(n²)O(n²)平均时间复杂度O(n²)O(n²)O(n²)空间复杂度O(1)O(1)O(1)稳定性稳定稳定不稳定对“近似有序”数据表现极好慢慢代码难度中等最简单简单冒泡排序胜在好理解选择排序胜在“交换次数少”但插入排序在综合表现上通常更好。特别是数据规模很小或者数据已经接近有序时插入排序几乎是无敌的。表格里没有提到快速排序因为它和插入排序不在一个学习阶段。快速排序是分治思想适合大数据量插入排序是基础排序适合小数据量和教学场景。两者不是替代关系而是互补关系。9. 常见错误与排查方法写插入排序的过程中初学者最常见的错误集中在几个地方。这里把高频 bug 列成表格方便你遇到问题时快速对照。问题现象可能原因排查方式解决方案排序结果第一个元素是乱的while 中j 0忘记判断导致访问arr[-1]在 while 循环前打印 j 的初值查看是否出现 -1补上j 0条件注意短路顺序排序后元素丢失出现重复值没有使用temp暂存移动元素时覆盖了待插入值在进入 while 前打印arr[i]和后续输出对比先temp arr[i]再开始移动排序结果不对但没报错第一个元素总是被覆盖哨兵版本中把arr[0]当成普通数据参与了排序检查数组定义下标 0 是否留给了哨兵数据从下标 1 开始存或者不用哨兵版数组越界程序崩溃外层循环i n错写成i n检查循环条件改成i n因为下标最大是 n-1while 写成了死循环j--写在循环体内但被条件挡住没执行到单步调试看 j 是否有变化确认j--在循环体内一定会被执行排序结果完全没变化数组传参方式错误或者是传入的是值拷贝在函数内打印数组地址确认和调用方一致C 语言数组传参本质是传指针检查函数签名输入有重复元素排序后出现乱序且不对内层判断写成了arr[j] temp破坏了稳定性用含重复数据的数组测试改成arr[j] temp这里额外强调一个最重要的排查手段打印和单步调试。如果排序结果不对不要猜直接在关键位置加printf打印每一轮的数组状态和 3.1 节的手工模拟结果对照很快就能找到问题。10. 插入排序的工程实践建议与适用场景学了插入排序什么时候真的会用到它这里给几个实际的判断。10.1 适合插入排序的场景数据量很小当数组长度小于几十时插入排序的实现简单、常数小不一定比快排慢。数据基本有序比如日志按时间写入偶尔有少数乱序记录用插入排序效率很高。作为复杂排序的收尾C 标准库里的qsort虽然用快速排序但很多快速排序实现在递归到子数组足够小的时候会改用插入排序。这是插入排序在真实工程中最常见的用途之一。链表排序对链表来说插入排序非常自然因为链表不需要大量移动元素只需要修改指针。10.2 不适合插入排序的场景超大规模数据几十万甚至上百万条数据时O(n²) 的时间复杂度会让程序卡到无法接受此时应使用归并排序、快速排序、堆排序等 O(n log n) 级别的算法。数据完全随机且规模很大插入排序会退化成大量比较和移动性能很差。10.3 代码风格建议排序函数不要依赖全局变量通过参数传入数组指和长度保持函数通用性。数组长度尽量用sizeof(arr) / sizeof(arr[0])计算不要写死。在函数内不要修改数组长度变量n在排序过程中保持不变。建议把函数名写成insertSort而不是sort避免命名过于泛化也方便和其他排序算法区分。11. 一个综合练习插入排序 从文件读取数据如果你觉得单纯排一个固定数组不够过瘾可以试试这个综合练习从文本文件中读取一组整数用插入排序排好序再把结果输出到另一个文件。这个练习覆盖了 C 语言文件操作和排序算法在很多时候你上网搜“C语言文件读写操作代码”实际遇到的就是类似需求。// 文件路径insert_sort_file.c #include stdio.h void insertSort(int arr[], int n) { int i, j, temp; for (i 1; i n; i) { temp arr[i]; j i - 1; while (j 0 arr[j] temp) { arr[j 1] arr[j]; j--; } arr[j 1] temp; } } int main() { FILE *fin, *fout; int arr[100]; int n 0; fin fopen(input.txt, r); if (fin NULL) { printf(无法打开 input.txt\n); return 1; } // 从文件读取整数直到文件末尾 while (fscanf(fin, %d, arr[n]) 1 n 100) { n; } fclose(fin); printf(读取到 %d 个整数。\n, n); printf(排序前); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); insertSort(arr, n); printf(排序后); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); fout fopen(output.txt, w); if (fout NULL) { printf(无法创建 output.txt\n); return 1; } for (int i 0; i n; i) { fprintf(fout, %d , arr[i]); } fclose(fout); printf(结果已写入 output.txt\n); return 0; }在同一目录下创建input.txt内容如下42 7 19 3 88 1 5 23编译运行gcc insert_sort_file.c -o insert_sort_file ./insert_sort_file预期输出读取到 8 个整数。 排序前42 7 19 3 88 1 5 23 排序后1 3 5 7 19 23 42 88 结果已写入 output.txt同时output.txt里会写入排序后的结果。这个练习还有一个价值让你理解fscanf的返回值。fscanf成功读取一个整数时返回 1读到文件末尾返回 EOF所以fscanf(fin, %d, arr[n]) 1才能作为循环条件。这种写法在“从文件读取未知数量数据”的场景里非常实用值得单独记忆。12. 给初学者的学习路径建议如果你正在自学 C 语言不清楚算法这块应该按什么顺序学这里给一条经过验证的路径先理解数组和循环插入排序的代码几乎全是数组和循环的组合如果for、while还不熟练先补基础。动手模拟一轮排序拿纸和笔手动把一个 5 元素的数组按插入排序的过程走一遍。这一步不能省它能帮你建立算法执行的画面感。默写基础版代码不看参考资料凭记忆写出insertSort函数。写不出来也没关系对照本文 4.1 节的解释找出卡住的地方。用调试代码验证过程运行 5.1 节的增强版程序把输出和你的手写模拟对照。尝试做变体练习比如改成降序排列把arr[j] temp改成arr[j] temp或者统计排序过程中的比较次数和移动次数。了解哨兵优化和复杂度分析这一层属于进阶能理解最好暂时看不懂也不影响使用。按照这个顺序插入排序这个知识点基本就吃透了。之后再去学快速排序、归并排序你会发现它们虽然更复杂但很多分析思路和插入排序是相通的。插入排序不是最快的排序算法但它小巧、稳定、贴近生活是 C 语言学习者进入算法世界的第一道门。把这一道门走通后面的路会顺畅很多。希望这篇文章能帮你把插入排序彻底弄懂而不是停留在“看别人代码觉得自己会了”的阶段。建议收藏起来写代码卡住的时候随时回看。
