插入排序算法详解：原理、代码实现与稳定性分析

1. 插入排序到底在解决什么问题

1.1 你打牌时其实已经会了插入排序

“排序算法”是数据结构里绕不开的一座山。不管你是准备“数据结构408”考研、应付“数据结构期末复习”，还是刚学“C语言排序算法”，第一道坎往往就是那几个经典的O(n²)排序。而“插入排序”又是其中最特别的一个——因为它很容易理解，却很容易写错。

先做一个联想。你打扑克牌，起手抓到一手牌，是不是会一边抓一边把新牌塞进手里已有的有序牌中？比如手里已经有“2、5、9、J”，这时来了张“7”，你会找到5和9之间的位置，把7插进去，手里仍然是“2、5、7、9、J”。这个动作，就是插入排序。

计算机里的插入排序干的是同一件事：把一个新元素“插入”到前面已经排好序的子序列中。它维护一个“局部有序区间”，每次都让这个区间往外扩一个元素。一开始这个有序区间只有第0个元素，因为单个元素天然有序；然后处理第1个元素，把它放到前面合适的位置；再处理第2个元素……等最后一个元素落位，整个数组就有序了。

这个思路简单到什么程度？就是你不需要背任何花哨的框架，只要记住一句话：每次把当前元素往“前面那一段有序区”里塞。这也是为什么很多老师都爱把它作为第一个排序来讲，因为它用到了最直白的“有序区扩张”思想，而不是“交换消除逆序”“分治递归”这种需要额外心智负担的东西。

1.2 插入、冒泡、选择：三种基础排序的思维差异

初学的时候，插入排序、冒泡排序、简单选择排序这仨容易混。我的建议是抓住它们各自的核心动作：

• 冒泡排序的核心动作是“交换”，每一轮把当前范围里的最大值“冒”到末尾。它的思路是让较大的元素像气泡一样不断向右移动。
• 简单选择排序的核心动作是“选出”，每一轮在剩余元素中找出最小值，把它放到当前范围的头部。它尽量减少交换次数，但比较次数固定。
• 插入排序的核心动作是“挪位+插入”，把当前元素腾出来，把前面比它大的元素都往后挪一格，留出空位再放进去。

用表格对比一下会更清楚：

三者都是O(n²)级别的基础排序，但插入排序有一个隐藏优势：当数据“基本有序”时，它会退化成O(n)。这一点下面细说。现在先记住结论：插入排序不是所有情况都慢，它最擅长的就是“大部分元素已经待在自己的位置上”这种场景。

2. 逐帧回放插入排序全过程

2.1 用一组真实数据手动推演

标题既然叫“动图展示”，我先把丑话说在前面：文章里没法直接嵌入那种闪来闪去的GIF，所以我把动图的每一帧截成表格和字符图。你如果能照着这些“帧”自己在草稿纸上画一遍，比看任何动图都管用。

取一个经典数组：

49 38 65 97 76 13 27

我建议初学时用竖线“|”表示“这个位置左边已经有序”的分界线，这个习惯能让你少犯很多边界错误。

初始状态，只看第0个元素49，它天然有序：

49 | 38 65 97 76 13 27

第一轮，处理下标1的38：

1. 把38存到临时变量key里，这个操作很关键，因为一会儿它原来的位置要被覆盖。
2. 让指针j从下标0开始往前找。j=0时，a[0]=49 > 38，所以把49往后挪一格，数组变成： 49 49 | 65 97 76 13 27
3. 此时j变成-1，说明前面没有比38更小的元素了，把key填到下标0。

结果：

38 49 | 65 97 76 13 27

第二轮，处理下标2的65。key=65，j从1开始往前扫。比较a[1]=49，49 > 65不成立，所以直接停止，65原地不动。注意，即使65恰好在自己该在的位置，它也要完成一次“比较”才停下来。这个“原地停在正确位置”的情况，是插入排序在有序数据下表现极好的原因之一：只比较，不移动。

结果：

38 49 65 | 97 76 13 27

第三轮，处理下标3的97。key=97，往前扫，38、49、65都不比97大，所以本轮只比较三次，不移动。结果：

38 49 65 97 | 76 13 27

第四轮，处理下标4的76，这是比较有意思的一轮。key=76，j从3往前扫：

• a[3]=97 > 76，97后移：38 49 65 97 97 13 27
• a[2]=65，65 > 76不成立，停止。

把key=76填到下标3的位置。结果：

38 49 65 76 97 | 13 27

第五轮，处理下标5的13。这个元素比前面所有元素都小，所以前面的38、49、65、76、97都要依次后移，最后13放到下标0。整个过程，很像隧道掘进机把一整排人往后推了一格，然后自己在最前面落了脚。

结果：

13 38 49 65 76 97 | 27

第六轮，处理最后一个元素27。它比13大、比38小，所以从后往前数，97、76、65、49、38依次后移，空出下标1的位置，27插入。

最终结果：

13 27 38 49 65 76 97

把完整的“帧序列”整理成一张表，你复习的时候可以对照着看：

仔细观察这张表，你会发现一个规律：每一轮插入之后，竖线“|”左边确实都是有序的，而且一轮只扩大一个元素。这就是插入排序最朴素的正确性证明——每一轮保持“前i个元素有序”，n轮之后整个数组有序。

2.2 单趟插入的“微观慢动作”

初学阶段，最容易卡住的地方是“为什么元素要后移而不是直接交换”。我见过很多同学写成类似交换的逻辑：发现a[j]比key大，就交换a[j]和a[j+1]，这样也能排对，但“交换”和“后移插入”是两个不同的动作。

为了看清楚差异，把刚才第四轮单独放大。这一轮处理key=76，目标是把76放进0~3这个有序区里。

开始时：

下标： 0 1 2 3 4 5 6 数组： 38 49 65 97 76 13 27 key = 76，j = 3

第一步，比较a[3]=97和key。97大于76，按规则，这个97不应该再待在76的前面，所以把它往后挪一格，覆盖掉a[4]：

38 49 65 _ 97 13 27

这里a[4]原本是key=76所在的位置，但我们已经把76备份到key里了，所以a[4]可以被覆盖——这就是为什么要先“保存key”的原因。

第二步，j减到2。比较a[2]=65，65并不大于76，于是停止后移。那么空位就在下标3：

38 49 65 _ 97 13 27

第三步，把key=76放进下标3：

38 49 65 76 97 13 27

如果走“交换”的路线，算法变成：97和76交换，得到38 49 65 76 97 13 27，结果一样。但交换需要三次赋值（temp=a, a=b, b=temp），而“后移+插入”在长距离移动时只把每个元素移动一次，赋值次数少一半以上。更重要的是，插入排序的“后移”逻辑才是它以后演变成希尔排序的理论基础。所以从一开始就要习惯“备份key，找位置，后移，最后落位”这条链路。

动手演示的时候，我建议你拿一张纸，写下下标0到6，再用硬币或小纸片标出每个元素。移动一个元素，就把纸片往后推一格，直到摸清那个“空位从哪儿产生，又从哪儿落下”的过程。这个方法听起来土，但理解指针越界问题特别有效。

3. 落到代码：C/C++ 实现与踩坑点

3.1 最朴素的数组版实现

理解了过程，代码其实就是一个双重循环。外层循环负责“从前往后取元素”，内层循环负责“往前扫描并后移”。我先把最标准的C风格写法放出来，后面再解释每一行为什么这么写。

void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; // 把当前要插入的元素备份出来 int j = i - 1; // 从有序区的最右边开始往前找 while (j >= 0 && a[j] > key) { // 只要前面的元素比key大 a[j + 1] = a[j]; // 就把那个元素往后挪一格 j--; // 继续往前看 } a[j + 1] = key; // 把key放到空出来的位置上 } }

代码只有六行有效逻辑，但有一个细节很多人第一次写会忽略：while循环里必须是j >= 0 && a[j] > key，顺序不能反。因为&&是短路运算，如果j已经变成-1，再执行a[j]就是在访问非法内存。你先判断j>=0，再访问a[j]，就能安全退出循环。

再看外层循环为什么从i=1开始，而不是i=0。因为第0个元素自己就是有序区，单元素不需要“插入”。换句话说，下标0是初始化好的有序区，i从1开始才轮到第一个“新来的元素”。如果从i=0开始，会把a[0]和自己比一遍，逻辑上既多余又容易造成边界问题。

还有一个常见的变体是把比较符号写成a[j] >= key。这个后面讲稳定性的时候会重点说，先记住：标准写法应该用严格大于>，相等时不移动，才能保证排序稳定性。

3.2 三个“看起来没问题但其实就是错”的写法

我在带初学者的时候，发现有三类错误出现频率极高。这里直接给你列出来，省得你踩。

第一类：内层循环条件顺序写反。

while (a[j] > key && j >= 0) // 错误！

当j跑到-1时，会先访问a[-1]，未定义行为。在C/C++里可能不崩溃但不代表安全，换一组数据可能就直接段错误。考试时手写代码，这样写也很容易被扣分。

第二类：没有备份key，直接拿原数组元素做比较。

for (int i = 1; i < n; i++) { int j = i - 1; while (j >= 0 && a[j] > a[i]) { // 错误！ a[j + 1] = a[j]; j--; } a[j + 1] = a[i]; // 这里的a[i]已经被覆盖了 }

在这个错误版本里，一旦a[j] > a[i]并执行了a[j+1] = a[j]，如果j+1恰好等于i，那么a[i]就被覆盖了。此后再用a[i]作为比较基准，整个逻辑就乱了。你手动跑一遍上面的例子，第一轮就会翻车：38被49覆盖后，key本来是38，却变成了49。

第三类：把内层循环从“后移”写成“交换”。

while (j >= 0 && a[j] > a[j + 1]) { swap(a[j], a[j + 1]); j--; }

这个写法在结果上没问题，也在LeetCode等平台上能通过。它的问题是性能差：插入排序的优点就是“每个元素最多移动一次”，交换则让每个元素可能被多次赋值。更麻烦的是，这种写法失去了插入排序的灵魂，后面讲希尔排序、折半插入优化时你会发现自己根本没理解核心机制。所以练习时请坚持“后移+插入”的写法。

3.3 考研风格的“哨兵”版本

数据结构教材里还有一种经典写法，叫“哨兵”版。它把a[0]空出来，专门放当前要插入的元素，这样内层循环可以省掉j >= 0这个判断，速度上有一点常数级提升，考试里也常被问到。

// 数组元素存放在a[1]~a[n]，a[0]作为哨兵 void insertionSortWithSentry(int a[], int n) { for (int i = 2; i <= n; i++) { a[0] = a[i]; // 把当前元素放进哨兵位置 int j = i - 1; while (a[j] > a[0]) { // 不需要判断j>=0 a[j + 1] = a[j]; j--; } a[j + 1] = a[0]; // 把哨兵位置的值填入正确位置 } }

这个版本的妙处在于：当j一直走到0时，a[0]一定等于key，与key比较的结果是相等，循环自然停止。它用一个额外空间换一次每次循环里的边界判断，在数据量大时确实能省一点时间。但你要注意，这里元素从下标1开始存放，和普通数组从下标0开始的习惯不同。如果你在考试里写这个版本，一定要先说明数组存储方式。

我在教学里一般建议先背朴素的j >= 0版本，因为它符合大多数人的直觉，也和你刷LeetCode时的接口习惯一致。哨兵版本是加分项，理解了之后自然能写，没理解的时候强行背，反而容易搞混下标边界。

4. 复杂度、稳定性与优化空间

4.1 为什么最坏是O(n²)，最好却是O(n)

插入排序的时间复杂度高度依赖数据原本的排列情况。这是它和其他基础排序最大的区别：同样一遍代码，数据不同，运行时间天差地别。

最好的情况，即数组已经完全有序。这时候每轮只要比较一次，也就是拿key和前面紧挨着的元素比一下，发现a[i-1] <= key，立刻停止。整个排序一共比较n-1次，移动0次（严格说key的备份和填回要做两次赋值，但在算法分析里通常不计为“移动元素”）。所以时间复杂度是O(n)。

最坏的情况，即数组是严格逆序的：大到小。第i轮插入时，key要跟前面所有的i个元素都比较一遍，而且每个元素都要往后挪一格。比较次数和移动次数都是累加的：

比较总数 = 1 + 2 + ... + (n-1) = n(n-1)/2 移动总数 = 1 + 2 + ... + (n-1) = n(n-1)/2

两个加起来，数量级还是O(n²)。

平均情况，数据随机时，平均每轮大概要比较一半的有序区元素，整体复杂度依然是O(n²)。所以教材上标准的结论是：最好O(n)，最坏O(n²)，平均O(n²)，空间复杂度O(1)。

这里有个易错点：有些人会把“平均O(n²)”记成“平均O(n log n)”。原因大概是快排和归并的O(n log n)印象太深。插入排序再怎么优化，平均情况下每个元素都要越过大约一半的前面元素，这个“大约一半”决定了它逃不出O(n²)的掌心。理解了这个微观原因，你就不会记错。

4.2 稳定性：为什么必须用“>”而不是“>=”

稳定性是什么？简单说，如果数组里有相等的两个元素，比如“49a”和“49b”，排序之后，原本靠前的“49a”仍然在“49b”前面，就说这个排序算法是稳定的；如果可能发生互换相对位置，就是不稳定的。

插入排序天然是稳定的。原因在于内层循环只对“严格大于key”的元素进行后移，遇到a[j] <= key就停下来。也就是说，相等的元素不会被移到key的后面，而是保持key在它后面，相对顺序不变。

可以把稳定性理解成“排序时不会乱插队”。你维护有序区时，遇到和自己值相同的人，会自觉站在人家后面，不敢把人挤到后面去。插入排序天然自带这种“礼貌”。

但如果你把>误写成>=，稳定性立刻被破坏：遇到相等元素时，你会让相等的元素后移，key插到它前面，等于“插队”。很多同学写出来的代码能通过普通测试，但考完试对答案才发现稳定性判断错了，就是栽在这个符号上。

所以考408或期末面试时，如果被问到“插入排序稳定吗？”，你要答两点：算法本身稳定；前提是内层循环使用严格大于>，写成>=就会变不稳定。

4.3 折半插入优化：省查找，但省不了挪位

既然插入排序的主要开销是“查找插入位置”和“后移元素”，那能不能用折半查找来加速找位置？答案是可以，这就是“折半插入排序”。

做法很简单：内层循环不用线性扫描，而是对前面那段有序区做折半查找，找到应该插入的位置。比如有序区是[13, 38, 49, 65, 76, 97]，要插入27，直接二分找到插入点在下标1。查找的复杂度从O(i)降到O(log i)。

但问题在于：找到位置之后，插入位置后面的元素仍然要整体后移，这一步的移动次数并没有减少。所以折半插入排序的总复杂度还是O(n²)，只是把“比较”这个部分的常数系数降低了。对数据量小的时候有一点微弱的性能提升，对数据量大时影响可以忽略不计。

这个优化真正的价值在“思路启发”上：你可以在插入排序的基础上，把“找位置”和“挪位置”两个操作拆开，分别优化。后来很多高级排序都延续了这种“分解问题再优化”的思想。学到这里，你可以顺手记住结论：折半插入排序，平均时间复杂度仍是O(n²)，但它比较次数减少，稳定性保持，空间复杂度O(1)。期末选择题里如果问“哪个排序在插入排序基础上减少了比较次数”，答案就是它。

5. 它在七大排序里到底是什么位置

5.1 七大排序横向对比

很多课程把基础排序总结为“七大排序”：直接插入、希尔、冒泡、快速排序、简单选择、堆排序、归并排序。把插入排序放进这个全家桶里看，它的定位非常清楚：常量和实现复杂度最低、对有序数据最友好、但大规模随机数据上整体打不过进阶排序。

光看这张表，插入排序似乎没什么亮点：平均和最坏都是O(n²)，比快排、堆排、归并慢。但这张表没体现“最好情况O(n)”这一点。在数据几乎有序的场景里，插入排序是全场唯一能跑到O(n)的简单排序，这也是它至今没被淘汰的原因。

5.2 实际工程里，插入排序常当“配角”

你可能觉得，既然有O(n log n)的排序，为什么还要学一个O(n²)的插入排序？原因在于，工程优化里插入排序经常作为高级排序的“最后一段”。

最有名的例子是快速排序的小区间优化。快排递归到子数组规模很小的时候（比如小于16个元素），递归开销开始变得不划算，很多标准库实现会停止递归，转而在小区间上调用插入排序。因为小规模数据上，插入排序不仅代码简单，而且开销很小，实测经常比继续递归快。类似的做法在归并排序的底层优化里也能看到。

还有一种场景是“几乎有序的数据流”。比如你维护一个排行榜，大部分时候只有几个新元素插入，数组整体已经有序，这时你用插入排序处理新元素，能在O(n)时间内搞定。你如果用快排全量重排，反而又慢又浪费。

另外，对于链表结构，插入排序也很好用。链表插入不需要移动元素，只需要改变指针指向。虽然比较次数没变，但“移动”的开销变成了O(1)的指针操作，写起来也直观。所以“插入排序只适合数组”这句话并不准确。

5.3 希尔排序就是“分组后的插入排序”

最后必须提一下希尔排序，因为不懂插入排序，就很难理解希尔排序。

希尔排序的思路很直接：先让数组“大体有序”，然后不断缩小间隔，最后做一次完整的插入排序。它把数组按照某个间隔gap分成若干组，每组内部做插入排序；然后gap逐步缩小，直到gap=1，也就是普通的插入排序。

为什么这么做？因为插入排序在“几乎有序”时效率最高。希尔排序就是反复制造“几乎有序”的状态，最后一轮插入排序时，数据已经乱不到哪儿去了，整个排序速度就上来了。所以希尔排序常被描述成“插入排序的升级版”，它的正确性和性能都建立在插入排序之上。

如果你能在脑子里把“插入排序”和“希尔排序”串成一条线，很多数据结构试卷里的填空题就会变得很好答：希尔排序的时间复杂度和增量序列有关，本质上是对直接插入排序的改进。

6. 常见问题排查与408考点清单

6.1 典型Bug排查表

我在自己写和辅导别人写插入排序时，遇到过不少典型问题。整理成表，方便你对照排查：

这些Bug里，最隐蔽的是“使用a[i]而没有备份key”。它偶尔能通过小规模测试，因为某些数据在覆盖前正好已经移出循环，但换一组数据就崩。所以我建议你在本地用几类特殊数据自测：完全升序、完全降序、有大量重复值、只有一个元素。这几组数据能覆盖绝大多数边界问题。

6.2 408和期末复习最爱考的细节

如果你在准备数据结构408或期末考，以下几个点几乎是必考级别，单独列出来：

第一，手动模拟能力。给一个数组，让你写出每轮插入排序后的结果。这种题不难，但容易在“这轮没移动”上掉以轻心。切记：没移动不等于没比较，每一轮至少要比较一次。

第二，比较次数和移动次数计算。最好情况下比较n-1次，移动0次；最坏情况下两者都是n(n-1)/2。考试里如果数据是确定的，要求手算具体数字，你最好按轮次老老实实列个表，防止算错。

第三，哨兵问题了。有些408风格的选择题会问：插入排序中设置哨兵的目的是什么？答案就是“避免每轮内层循环都要判断下标是否越界”，从而减少一次比较。答题时可以说“简化边界判断，提高效率”。

第四，与选择排序的区别。选择题里常有一个干扰项：“插入排序每一轮选最小值放到前面”，这是选择排序的说法。插入排序是“把当前元素插入前面有序区”，描述的是另一回事。

第五，稳定性判定。刚才已经强调过：直接插入排序是稳定的，前提是用严格大于。希尔排序则不稳定。这两者常常成对出现，问你“在插入排序基础上改进的排序算法中，哪个稳定性变了”。

如果让我给一个复习策略，我会建议你把这篇文章里的示例数组自己在纸上跑三遍：第一遍不看书，第二遍对照代码检查，第三遍不看任何参考，同时写出每一轮的比较次数和移动次数。这个过程比看十遍动图都有用，因为纸面推演会逼你把“谁往后移、空位在哪、key最终落到哪”这三个问题逐个想清楚。

插一句我的个人体会：很多同学学排序，最后脑子里留下的只有“时间复杂度表”，但稍微换个问法就不会了。真正把这个算法吃透的标准，不是能默写代码，而是能对着一个心算数组，说出每一轮的比较次数和移动次数，讲清为什么在几乎有序的数据上它表现得特别好。能达到这个程度，408里的排序选择题基本就难不住你了。

排序算法这块，插入排序是所有排序的“第一块积木”。它简单，但它连接着复杂排序里最核心的两个问题：如何减少比较，如何减少移动。希尔排序、折半插入、甚至快排的局部优化，都能从这六行代码里找到出发点。把这块积木搭稳，后面的路会顺很多。