C语言插入排序是很多初学者学会冒泡排序之后第二个应该掌握的排序算法也可能是最容易“看着简单、一写就错”的一道坎。插入排序的基本思路可以用一句话讲完把新元素往已经有序的前半部分里插入从后往前比较比它大的元素逐个后移最后把它放到该待的位置。这句话听着简单真落到C语言代码里问题就来了为什么循环要从第二个元素开始为什么要用临时变量先把值存起来为什么内层循环越走越靠前这些点不弄清楚代码只能是背下来的。下面的内容不会堆动画截图而是把排序过程拆成可以照着写的步骤先建立脑内动画再逐行讲C语言实现最后补上验证方式、常见错误和练习路径。适合刚学完数组和循环的C语言新手也适合准备期末、专升本或入门竞赛时想快速把排序基础打扎实的人。最值得先说明白的一点是插入排序虽然平均时间复杂度不算优秀但它在数据基本有序的场景里表现非常好而且很多高级排序算法内部会把插入排序当作收尾策略搞懂它绝对不亏。1. 插入排序到底在干什么先建立脑内动画1.1 一句话理解核心逻辑插入排序的做法本质上就是把一个数组想象成两部分左边是“已经排好序的部分”右边是“等待处理的部分”。每次从右边取第一个元素出来把它往左边已经有序的序列里插。插入的时候不能直接换位置而是从后往前找只要左边的元素比它大就把那个元素往右挪一格给新元素腾位置。找到某个位置前面的元素不再比它大就停把新元素放进去。关键就在“从后往前”这四个字。如果从前往后找你想把元素放到中间某个位置就得先把后面所有元素都移开移动次数会更多而且容易覆盖掉还没处理的元素。从后往前找移动和后移可以在同一个循环里完成代码上更顺手这也是为什么几乎所有教材都这么写。1.2 用扑克牌模拟一遍完整过程把数组想成手里的一副扑克牌。你从左到右看牌默认第一张已经理好了摸到第二张的时候如果它比第一张小就把第一张牌往右边挪一个位置然后把第二张放到空出来的位置。摸到第三张再看第三张应该插到前面哪两张之间。每次只处理一张新牌处理完以后手牌左边这部分始终是有序的。以数组{5, 2, 4, 6, 1, 3}为例完整过程如下趟数正在处理的元素处理前数组移动过程处理后数组第1趟25 2 4 6 1 3525后移2 5 4 6 1 3第2趟42 5 4 6 1 3545后移24不成立2 4 5 6 1 3第3趟62 4 5 6 1 356不成立原地不动2 4 5 6 1 3第4趟12 4 5 6 1 36、5、4、2依次后移1 2 4 5 6 3第5趟31 2 4 5 6 36、5、4依次后移23不成立1 2 3 4 5 6表格里“处理后数组”可以看成每处理完一张牌之后手里已经有序的牌。第1趟处理完左边两个元素有序第2趟处理完左边三个元素有序以此类推。1.3 “插入”的本质腾位置而不是换位置很多人第一次写插入排序时会把“插入”理解成“交换”。比如发现第 i 个元素比前面的小就不断 swap 相邻元素让这个元素往前冒泡。这种写法也能得到结果但它不是标准的直接插入排序而且代码性能更差、移动次数更多。标准的插入排序内部只做两件事把需要插入的值先存下来。从后往前把比它大的元素依次往右移动一格。移动不是交换。交换需要三次赋值移动只需要一次赋值。数据量小的时候看不出差别数据量上万后移动方式比交换方式明显轻快。这个区别也关系到你对“原地算法”的理解插入排序不用开第二块数组只借助一个 key 变量就能在原数组内完成排序。注意写插入排序时先别急着调优化。先把“取一个值、往前比较、后移空位、放入正确位置”这一套流程跑通再谈性能改进。2. C语言直接插入排序标准写法代码逐行拆开讲2.1 写代码前先把环境准备好C语言不需要多复杂的开发环境。如果你用的是 Windows装一个好用的编译器就好比如 Dev-C、Code::Blocks、Visual Studio Community或者配置好 MinGW 的命令行环境。如果你用的是 Linux基本都会自带 gcc直接写文件编译就行。macOS 上也可以用 clang命令跟 gcc 差不多。我一般建议新手用最简单的流程先建一个insert_sort.c文件把代码贴进去然后打开终端执行编译命令。gcc insert_sort.c -o insert_sort ./insert_sortLinux 和 macOS 一般用./insert_sort来运行。Windows 命令行下编译后生成的是insert_sort.exe运行方式就是insert_sort.exe如果你平时喜欢用图形界面 IDE也可以直接在 IDE 里新建 C 项目把代码放进去编译运行。这里最不需要纠结的就是工具任何能编译 C 的软件都可以算法思路不受开发环境影响。2.2 完整代码包含输出观察版下面是完整的直接插入排序 C 语言代码。为了方便观察每一趟排序发生了什么我加了一个打印函数。#include stdio.h void print_array(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; // 先保存当前要插入的元素 int j i - 1; // 从已排序部分的最后一个元素开始往前比 // 从后往前找只要前面的元素比 key 大就后移 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } // 循环结束后j1 就是 key 应该放入的位置 arr[j 1] key; // 打印每一趟的结果方便观察算法过程 printf(第 %d 趟: , i); print_array(arr, n); } } int main() { int arr[] {5, 2, 4, 6, 1, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); print_array(arr, n); insertion_sort(arr, n); printf(排序后: ); print_array(arr, n); return 0; }运行输出如下排序前: 5 2 4 6 1 3 第 1 趟: 2 5 4 6 1 3 第 2 趟: 2 4 5 6 1 3 第 3 趟: 2 4 5 6 1 3 第 4 趟: 1 2 4 5 6 3 第 5 趟: 1 2 3 4 5 6 排序后: 1 2 3 4 5 6注意第3趟原来的 6 已经比前面所有的都大循环条件一次都不成立key 又放回原位置所以数组看起来“没变化”。排序算法里这种“没变化”也是正常结果不是 bug。2.3 每个关键代码点为什么这么写为什么外层从 i 1 开始因为第 0 个元素自己就是有序的不需要插入自己。从第二个元素开始每次把当前元素插入到它前面那一段已经有序的序列中。如果从 i 0 开始key 等于 arr[0]j 从 -1 开始程序也能跑但没有任何意义还多了一次无用的循环。为什么一定要用 key 把 arr[i] 保存下来这是新手最常忽略的一步。看这段代码while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; }arr[j 1] arr[j] 会把当前位置的值覆盖。比如第 4 趟处理元素 1 时arr[5] 先被覆盖成 6然后 arr[4] 覆盖成 5arr[3] 覆盖成 4arr[2] 覆盖成 2arr[1] 也会被覆盖成 2。如果不提前把 arr[i] 也就是 1 存到 key 里等真要把 1 放回 arr[0] 时这个 1 早就已经丢了。key 变量存在的意义就是防止待插入的值被覆盖。为什么内层循环条件要写 j 0 arr[j] key两个条件都不能少。arr[j] key 负责判断“前面这个元素要不要后移”j 0 负责防止数组越界。当 j 一路减到 -1说明 key 比当前已排序部分的所有元素都小它应该被放到数组最前面。如果少了 j 0arr[-1] 会被非法访问程序可能崩溃也可能悄悄读到一个随机值导致结果莫名其妙。为什么最后插入位置是 arr[j 1]while 循环退出有两种情况j 停在某个位置arr[j] key说明 key 应该放在 j 的后面也就是 j 1。j 减到了 -1说明 key 应该放在数组开头也就是 0正好等于 -1 1。所以退出后统一执行 arr[j 1] key 就对了不需要额外去判断 j 到底是哪种情况。这是这段代码设计得很巧妙的地方同时也是新手最容易抄错的地方有人在 while 后面写 arr[j] key结果每次都会把一个位置写错。为什么要用函数而不是把逻辑全堆在 main 里把插入排序封装成insertion_sort函数main 里只需要调用。这样后面你想换不同测试数据只需要改 main 里的数组你想在别的程序里复用排序逻辑也只需要把这个函数复制过去。排序函数只关心 arr 和 n 两个参数不关心数据是怎么来的这是 C 语言里很基本的模块化思路。3. 代码写完之后怎么验证它真的对3.1 先跑最小样例不要一上来就测一万个数我见过不少初学者第一次写完插入排序直接拿一个长度 10000 的随机数组测试。结果跑出来不对又看不懂哪里错了最后只能一行一行地猜。排错的第一步是缩小问题范围。先跑固定的小数组比如{5, 2, 4, 6, 1, 3}因为你能在纸上把六步过程手算出来然后跟程序输出一行一行对照。只要每一趟的输出和手算结果一致主要逻辑就基本没问题了。然后再慢慢加大数据比如 10 个、100 个最后再试 10000 个。这就像学开车先在停车场练明白转弯和换挡再上大路。数据量越大出错后越难定位。3.2 必须测的边界情况排序题目里最容易让人翻车的不是正常数据而是边界数据。建议把下面几类数组都测一遍测试类型示例输入期望输出说明空数组{}无输出不崩溃数组长度为 0没有任何元素单元素{7}7长度为 1天然有序已有序{1, 2, 3, 4}1 2 3 4内层循环应该基本不移动逆序{5, 4, 3, 2, 1}1 2 3 4 5每趟都要移动很多次有重复{3, 1, 3, 2}1 2 3 3验证稳定性重复元素不动空数组是很特殊的情况。调用函数时 n 是 0外层 for 循环i n一开始就不成立所以不会有任何操作。看起来很简单但如果你在 main 里不管 n 直接执行sizeof(arr) / sizeof(arr[0])空数组不一定能正常拿到 0所以建议测试空数组时手动把 n 传成 0别依赖数组定义。3.3 用随机数据做大规模验证手算能覆盖小数据但真要确定排序结果正确还需要用更大规模的随机数据来测试。思路是这样的生成一个随机数组。先复制一个副本。用插入排序排副本同时用标准库的 qsort 或者你确认正确的其它排序排原数组。最后逐位比较两个结果是否完全一致。C 语言里可以用rand()生成随机数用qsort作为对照排序。下面是一个简单的验证框架#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } int main() { int n 1000; int arr[1000]; int expected[1000]; for (int i 0; i n; i) { arr[i] rand() % 10000; expected[i] arr[i]; } insertion_sort(arr, n); qsort(expected, n, sizeof(int), cmp); for (int i 0; i n; i) { if (arr[i] ! expected[i]) { printf(第 %d 位不一致\n, i); return 1; } } printf(和 qsort 结果完全一致\n); return 0; }如果每一轮随机测试都能通过基本可以确定你的插入排序实现没有逻辑问题。这个方法比靠眼睛看输出靠谱得多。这里补充一句上面的cmp用减法实现比较因为测试数据范围在 0 到 9999 之间不会出现整数溢出问题。如果以后要比较更大范围的整数建议改成更安全的写法比如先判断大小再返回 -1、0、1避免减法溢出。注意rand() % 10000只会生成有限范围内的数据所以这种测试主要是验证排序逻辑的正确性不是验证算法在真实负载下的性能。真要测性能需要单独计时并尝试不同分布的数据。4. 插入排序的性能和适用场景不要盲目崇拜 O(n²)4.1 时间复杂度最好、最坏、平均到底差多少插入排序的时间复杂度取决于初始数据的顺序最好情况数据本来就是升序。每一趟只要比较一次发现前面的元素不大于 key直接结束。总比较次数接近 n 次时间复杂度 O(n)。最坏情况数据完全逆序。第 i 趟平均要移动 i 次总移动次数约为