有一次我在给一位刚学 C 语言的朋友讲排序。他皱着眉头问我冒泡排序我勉强能看懂插入排序到底在干嘛为什么要把元素一个一个往前挪我当时没有急着翻课本而是从桌上拿了一副扑克牌抽了六张像发牌那样摆成一排反问他你平时打牌理牌是怎么理的他愣了一下说起了牌之后顺手插到该放的位置啊。我说对这就是插入排序。插入排序是所有排序算法里最接近人类直觉的一个。它不搞什么花哨策略就是重复一个动作拿起一个元素插进前面已经排好序的序列里让它待在正确的位置。这个动作重复 n-1 次整组数据就排好了。如果你准备零基础学排序我真正建议你先把插入排序彻底搞懂而不是急着去啃快速排序或者归并排序。原因不复杂插入排序的价值不在“快”而在把“排序”这个抽象问题还原成了“整理”这个具体动作。它是最好的第一块跳板。1. 为什么说插入排序是最接近人类直觉的排序算法1.1 打牌理牌你其实一直在手动执行插入排序想象一下你正在玩扑克。摸完一轮牌你手里已经有几张牌比如是 5、3、7。这时候你又摸到一张 4。正常人不会把整手牌重新排一遍而是很自然地看一圈发现 4 应该放在 3 和 5 之间于是把 5 和 7 往旁边挪一挪腾出位置把 4 放进去。这个动作分解到计算机里恰好就是插入排序的三个子步骤取牌把当前要整理的元素拿出来。腾位从右往左依次比较把比它大的牌往后挪。落位把牌放进腾出来的空位。同样的动作重复若干次整手牌就整整齐齐了。很多人觉得算法是课本里才有的东西但插入排序恰恰是少数几种“你早就用过只是不知道它叫这个名字”的算法。我经常用这个类比去说服初学者如果你的程序需要维护一个“始终保持有序”的数组比如排行榜、成绩表、库存列表每次新来一个数据都要插到合适位置那么你其实是在重复使用插入排序的思想。1.2 先建立一个正确的心理模型它不是在“整体重排”初学者最容易搞混的一点是觉得插入排序像冒泡排序那样从第一轮开始就在全局反复交换。不是的。插入排序每一轮只做一件事把当前元素插到它前面那个“已经有序的序列”里。所以在任意一轮进行中数组都分成两段左边一段已经排好序。右边一段还没处理顺序保持原样。随着轮次推进左边这段不断变长右边这段不断变短。最终右边消失整个数组有序。理解这个“半边有序、半边待处理”的心理模型比记住代码本身更重要。因为后面你学二分插入排序、希尔排序甚至归并排序都离不开“局部有序”的概念。插入排序把这个概念展示得最直白。2. 动画背后一次完整的插入排序过程拆解2.1 拿六个数字把整个过程走一遍动画看的时候总是很快容易一晃而过。我建议你拿笔在纸上跟着下面这个例子手动推演一遍。用数组{5, 2, 4, 6, 1, 3}来演示。先约定我们把第一个元素 5 看作“已经排好序的部分”。从第二个元素开始每一轮取出一个元素往前插。轮次取出的 key插入前已排序部分操作摘要插入后的数组初始-[5]把第一个元素视为已排序5, 2, 4, 6, 1, 312[5]5 后移2 放到开头2, 5, 4, 6, 1, 324[2, 5]5 后移2 前停止4 插入中间2, 4, 5, 6, 1, 336[2, 4, 5]5 6不需要移动2, 4, 5, 6, 1, 341[2, 4, 5, 6]6、5、4、2 依次后移1 放到开头1, 2, 4, 5, 6, 353[1, 2, 4, 5, 6]6、5、4 后移遇到 2 停止3 插入1, 2, 3, 4, 5, 6这六轮结束数组变成有序。注意第 3 轮key 是 6它比前面已排序部分的最后一个元素 5 还大所以一个都不用挪直接原地不动。这是插入排序在“数据已经比较有序”时效率高的原因之一。2.2 每一轮内部其实只有三步很多人看动画被带偏以为插入排序是在“交换元素”。实际上它更准确地说是在“移动元素”并且只在最后做一次真正的插入。每一轮循环内发生的事情是把arr[i]的值存到变量key里此时原位置相当于被“掏空”了。用一个下标j从i-1开始向左移动凡是比key大的元素都往右复制一位。直到遇到一个不大于key的元素或者已经遍历到数组最左边循环停止。此时把key放进arr[j1]。注意第二步里“复制”这个词。插入排序内部大量操作是把arr[j]赋值给arr[j1]这本质上是元素的后移而不是交换。这一点在阅读代码时非常关键很多初学者会疑惑为什么我没写swap数组却在变化因为后移本身就是一种移动。2.3 动画里真正值得盯住的三个细节看插入排序动画的时候我建议你刻意去盯三件事key 那个被抽出来的元素它在每一轮开始时是“悬空”的动画里通常会高亮。比较方向永远是“从右往左”也就是从已排序部分的末尾往开头走。这个方向决定了你写 while 循环时j--的原因。元素不是交换过去的而是一个一个“挤”过去的视觉上像多米诺骨牌往右倒。把这三个细节在脑子里和后面的代码对应起来你就能做到“看动画能想到代码看代码能想到动画”。注意插入排序每一轮只处理一个元素千万不要一次性想把整个数组都排好。算法最忌讳“贪多”一轮只解决一个元素的归属是插入排序最朴素的智慧。3. C 语言代码实现先跑通再讲优化3.1 一个能直接运行的最小版本先不用考虑各种花哨写法下面这段是插入排序最经典、最容易理解的 C 语言实现#include stdio.h void insertion_sort(int arr[], int n) { int i, j, key; for (i 1; i n; i) { key arr[i]; // 取出当前要插入的元素 j i - 1; // 从它前面一个位置开始向前找 // 只要前一个元素比 key 大就把它往后挪 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; // 空出来的位置放入 key } } int main() { int arr[] {5, 2, 4, 6, 1, 3}; int n sizeof(arr) / sizeof(arr[0]); insertion_sort(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }这段代码在常见编译器环境下可以直接编译运行输出结果是1 2 3 4 5 6。3.2 逐行拆解核心循环很多初学者拿到代码就背背完就忘。我建议你换一种方式一行一行地问自己“这一行在干什么为什么在这里”。第一行核心代码是for (i 1; i n; i)为什么不从 0 开始因为第 0 个元素单独看就已经是“长度为 1 的有序序列”了不需要插入。我们从第 1 个元素开始把它插到前面长度为 1 的序列里下一轮处理第 2 个元素把它插到前面长度为 2 的序列里。i 的含义是“当前要处理的下标”。第二句key arr[i];这句的意义是把当前元素备份出来。为什么要备份因为后面的 while 循环会把前面的元素往右复制有可能覆盖掉arr[i]的位置。如果不提前存到 key 里等你想放回去的时候原值已经丢了。第三句j i - 1;j 代表“当前正在和 key 比较的那个位置”从已排序部分的最后一个位置开始。第四句是整个算法的灵魂while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; }这里有两个条件缺一不可j 0防止访问数组下标变成负数。arr[j] key只要前面的元素比 key 大就需要往后挪。循环内部做的事情就是把arr[j]复制到它右边一位。注意这里每一轮都会覆盖掉arr[j1]原来的值但那个值要么已经在上一轮被备份走了要么就是被掏空的位置所以不会丢失数据。循环结束后j 指向的是“最后一个不大于 key 的元素”的位置。因为循环退出前 j 又执行了一次j--所以 key 的正确落点是j 1。最后一句arr[j 1] key;就是完成插入。3.3 给排序加上过程输出自己验证一遍只看代码还是不够直观。我强烈建议你在排序函数里加几行打印亲眼看看每一轮数组怎么变化#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) { int i, j, key; for (i 1; i n; i) { key arr[i]; j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } 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); 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这个输出和第 2 节的手工推演完全一致。能对上说明你对算法的理解没有偏差。3.4 教科书版本用 for 循环压缩写法很多教材和源码会把 while 改写成 for 循环看起来更紧凑void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j; for (j i - 1; j 0 arr[j] key; j--) { arr[j 1] arr[j]; } arr[j 1] key; } }这个版本和 while 版本逻辑完全一样只是把“初始化 j、判断条件、j--”合并到了 for 语句里。我建议你两个版本都写一遍理解它们是等价的。考试和面试时遇到哪种写法都能马上反应过来。4. 复杂度、稳定性与适用边界4.1 时间复杂度要看三种情况初学者容易把插入排序直接定性成“O(n²) 的慢排序”这个说法太粗糙了。它的时间复杂度应该分三种情况看情况条件比较/移动次数时间复杂度最好数据已经从小到大有序每轮只比较 1 次不移动O(n)平均数据随机排列每轮大约移动一半已排序元素O(n²)最坏数据完全逆序每轮都要把前面所有元素往后挪O(n²)最好情况很好理解如果数组本来就是有序的arr[j] key第一次比较就失败while 循环直接不进去每一轮只做一次比较和一次赋值。所以插入排序在“处理基本有序的数据”时效率其实很高能达到线性级别。最坏情况是逆序数组{6,5,4,3,2,1}每一轮的 key 都小于前面所有元素所有已排序元素都要后移。比较次数和移动次数加起来大约是n(n-1)/2也就是 O(n²)。空间复杂度则是 O(1)。它只用了 i、j、key 这几个额外变量在原地完成排序不申请额外的数组。这一点在嵌入式环境或者内存受限的场景里是很大的优势。4.2 稳定性一个细节决定排序的“品格”稳定性的定义是如果数组里有两个相等的元素排序之后它们的相对顺序不能变。插入排序的稳定性取决于 while 循环里比较条件用的是还是。写成arr[j] key遇到相等的元素时while 循环停止key 被插到相等元素后面。相等元素的原始顺序不变算法是稳定的。写成arr[j] key遇到相等的元素时仍然会把它往后挪key 被插到相等元素前面。相等元素的顺序被反转算法变得不稳定。在只做单字段排序时这个差别看不出来结果都是有序的。但真实业务里经常有多字段排序比如学生成绩表先按总分排总分相同再按学号排。如果你在第二次排序时用了不稳定的算法前一次按学号排好的顺序可能被破坏。所以稳定性不是理论洁癖而是真实工程需求。4.3 什么时候该用它什么时候别用它适合插入排序的场景我总结为四个数据量小比如几十个到几百个元素。数据已经基本有序只有少数元素位置不对。数据是动态到来的比如实时流式数据每来一条就插入到已排序列表里。内存紧张不能申请额外的大数组。不适合的场景也很明确数据量大且无序比如几万、几十万个随机数这时候快速排序、归并排序明显更合适。对排序耗时极敏感的服务端场景插入排序的 O(n²) 会成为瓶颈。数据本身已经是稳定有序的结构但你需要频繁大量调整顺序时应该考虑更高效的数据结构比如平衡树。注意插入排序是“小数据友好型”算法。把它用在大规模随机数据上等于拿着一把水果刀去砍树不是刀不行是场景选错了。5. 新手最容易栽的坑以及一套排查顺序5.1 三个高频 bug我自己见过初学者写插入排序最容易出现三个问题。第一个while 条件漏写j 0。直接写成while (arr[j] key)当 j 减到 -1 时会去访问arr[-1]。这在 C 语言里是未定义行为运气好读到垃圾值运气不好直接段错误崩溃。第二个把arr[j] key写成arr[j] key。排序结果依然有序所以很难发现但算法从稳定变成了不稳定。如果后面你拿它做多字段排序就会埋下隐患。第三个循环结束后插入位置写错。很多人想当然写成arr[j] key却忘了 while 循环退出前 j 已经多减了一次。应该是arr[j 1] key。这个 bug 的典型症状是数组里某个元素丢失或者某两个位置出现重复值。还有一个不是循环本身的坑而是数组大小的坑。在main里用sizeof(arr) / sizeof(arr[0])计算数组长度是对的但一旦数组作为参数传进函数它就退化成指针sizeof(arr)不再是整个数组的大小而是指针的大小。所以不要在函数内部重新用 sizeof 算长度应该在调用前算好传进去。5.2 一套从现象到根因的排查顺序如果你写完代码发现结果不对不要慌按下面这个顺序排查先看现象是什么是完全没排序还是只有局部有序还是最后一位不合法还是直接崩溃把数组缩小到 3 到 5 个元素用手推一遍中间结果确定算法逻辑本身对不对。在 while 循环里加打印输出每一轮的 i、key、j以及当前数组状态看看卡在哪一步。检查边界输入空数组、单元素、重复元素、已经有序、完全逆序、含负数。检查 n 的传递是不是在函数里误用了sizeof。检查比较方向还是升序还是降序j--还是j。这个排查顺序的核心是先确认“算法逻辑”对不对再确认“代码实现”对不对最后才考虑“边界情况”对不对。很多初学者一上来就在网上问为什么崩溃其实只要加两行打印自己就能发现是j 0漏了。5.3 正确性验证不要只看一次输出只跑一个样例得到正确结果不代表代码没问题。我建议你准备一组测试数据至少覆盖这些情况// 逆序数组最坏情况 int arr1[] {6, 5, 4, 3, 2, 1}; // 正序数组最好情况 int arr2[] {1, 2, 3, 4, 5, 6}; // 重复元素验证稳定性隐患 int arr3[] {3, 1, 3, 2, 3}; // 含负数 int arr4[] {0, -2, 7, -1, 5}; // 单元素 int arr5[] {1};每次跑完都写一个小的检查函数确认数组确实是从小到大排列而不是肉眼看一眼就完事。养成这个习惯之后你以后学任何排序算法都会更快。6. 从插入排序出发建立算法学习的可复用框架6.1 学任何一个排序算法的四个步骤插入排序不只是教你一个算法它还能帮你建立一套学习排序算法的方法论。以后你学冒泡排序、选择排序、快速排序、归并排序都可以走同一个流程第一步找一个生活场景。插入排序对应打牌理牌冒泡排序对应气泡上浮选择排序对应每轮挑最小的放最前面。没有生活场景你对算法的记忆就是死记硬背。第二步手工推演。拿一个 6 个元素左右的小数组把每一轮的中间状态写出来至少走 3 个例子。第三步写最小可运行代码加调试输出。先保证正确再考虑优化或压缩写法。过程性打印是你最好的老师。第四步分析三个维度时间复杂度的三种情况、空间复杂度、稳定性。最后明确它适合什么场景、不适合什么场景。这套流程走完你对一个算法的理解就不是“会用”而是“懂它”。6.2 两个顺势就能理解的进阶方向理解了插入排序之后有两个方向是你立刻就能往前走的。第一个是二分插入排序。因为插入排序每一轮要插入的前半段已经有序所以完全可以用二分查找快速定位插入位置。这样比较次数可以从 O(n²) 降到 O(n log n)但元素移动的次数仍然是 O(n²)。它的意义在于让你看到“比较”和“移动”是两个可以分别优化的环节。第二个是希尔排序。希尔排序的本质就是“多次插入排序”先把数组按一定间隔分成若干组对每组做插入排序然后缩小间隔直到间隔为 1。它的核心思想是让元素先进行大步移动减少小步移动的总次数。如果你插入了插入排序的原理希尔排序的代码你基本能看懂一半。另外还有一个不那么直观但很重要的事情很多现代混合排序算法在处理小规模数组片段时会退化到插入排序。比如 TimSort 在处理长度小于某个阈值的子数组时就会调用插入排序因为在小规模数据上插入排序的常数开销相对更低。所以插入排序不是“被淘汰的算法”它仍然藏在很多高性能排序的实现细节里。6.3 回到一个更底层的经验折腾完这一整条链路我最想留给你的一句话是学算法先别急着追求最短的代码、最快的性能先把“这个算法到底在重复做什么动作”想清楚。插入排序重复的动作是“拿起一张牌插进正确的位置”。你理解了这一点代码怎么写都只是表达方式的问题。而当你理解了“为什么每轮要找右往左找、为什么挪完要插回 j1、为什么相等元素不要越过”你其实已经在用工程师的思维看算法了。下一步你可以试着把这份代码改成降序排序或者改成二分插入排序或者加上一个“如果本轮没有移动元素就直接结束”的提前退出。改着改着你会发现自己不知不觉已经能独立折腾算法了。先从这一份代码开始把它跑通把它打印出来把它丢掉再重新默写一遍。搞定插入排序30 分钟够用了。