直接插入排序

2026 大纲 七（二）直接插入排序。

摸一张牌，往手里已排好的牌中插

直接插入排序就是打牌时理牌的动作：手里的牌已经排好序，摸到一张新牌，从右往左比过去，找到位置塞进去。

第 $i$ 趟做完之后，序列满足一个不变量：

原序列的前 $i+1$ 个元素已有序，后面的元素一个都没被碰过。

这个不变量里藏着本篇最要紧的一句话：

🔴 前缀有序 $\ne$ 前缀就位。 全局最小值完全可能还躺在后面，前缀随时会被后来的元素插队。这是区分插入类与选择类的唯一判据。

反过来，"后面的元素一个都没被碰过"给了它一个极硬的指纹：

🔴 后缀与初始序列逐位相同——看到某趟结果的尾巴还和原始输入一模一样，就要优先怀疑插入类。

先动手看一眼

加载可视化中...

代码与三处要点

// 不带哨兵（下标从 0 开始）
void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {           // 从第 2 个元素开始，共 n-1 趟
        if (A[i] < A[i - 1]) {          // 前驱不大于它就说明它已在位，整趟只做这 1 次比较
            temp = A[i];                // 暂存待插入元素，A[i] 这个位置随后要被覆盖
            for (j = i - 1; j >= 0 && A[j] > temp; j--)
                A[j + 1] = A[j];        // 后移；是 A[j] > temp，相等时停，稳定性靠这里
            A[j + 1] = temp;            // 退出时 j 指向"不大于 temp 的那个位置"，故插在 j+1
        }
    }
}

// 带哨兵（数据放在 A[1..n]，A[0] 作监视哨）
void InsertSort2(int A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        if (A[i] < A[i - 1]) {          // ① 逆序才需要插入
            A[0] = A[i];                // ② 待插记录存进哨兵单元
            A[i] = A[i - 1];            // ③ 前驱先后移，腾出 A[i]
            for (j = i - 2; A[0] < A[j]; j--)
                A[j + 1] = A[j];        // ④ 继续后移，无需越界判断
            A[j + 1] = A[0];            // ⑤ 落位
        }
    }
}

第一，不带哨兵时 j >= 0 不能删。 若 temp 比已排序区所有元素都小，j 会一路减到 $-1$，没有这个判断就会读 A[-1]，属于越界访问。（n <= 1 时外层循环一次都不进，空表与单元素表都安全。）

第二，哨兵为什么能删掉那个判断。 j 最小减到 0 时，第 ④ 行的条件变成 A[0] < A[0]，必然为假，循环自动停止——哨兵单元里存的正是待插元素本身，它挡住了下标继续往左走。省下的是内层循环里每次迭代都要做的一次下标比较，而内层循环是整个算法执行次数最多的地方（最坏约 $n^2/2$ 次）。

第三，稳定性靠"严格大于"。 能改变相对次序的动作只有后移，触发条件是 A[j] > temp：相等时条件为假、循环停止，temp 落在 A[j] 后面；而被后移的元素都严格大于 temp，它们整体右移一位、彼此次序不变。把 > 写成 >=，相等元素也会被后移——{2a, 2b} 就会输出成 2b, 2a。

开销正比于逆序对数

这是本篇唯一需要记的定量结论，它一句话解释了三个复杂度和全部选型判断：

🔴 后移次数恰等于原序列的逆序对数。

道理是：内层循环每执行一次，就消掉待插元素与前面某个元素构成的一个逆序对。于是

初始序列	逆序对数	比较次数	移动次数
正序	0	$n-1$	0
随机	期望 $n(n-1)/4$	约 $n^2/4$	约 $n^2/4$
逆序	$n(n-1)/2$	$\frac{(n+2)(n-1)}{2}\approx \frac{n^2}{2}$	$\frac{(n+4)(n-1)}{2}\approx \frac{n^2}{2}$

于是时间是最好 $O(n)$、平均与最坏 $O(n^2)$，空间 $O(1)$。

⚠️ 最好情况的移动次数是 0，不是 $O(n)$——已在位的元素连暂存都不做，第 ① 行直接返回。

趟数固定 $n-1$ 趟，与初始序列无关（对比：起泡可提前终止，快排的趟数就是递归深度）。

数比较次数的手法（真题直接考过"哪个序列的比较次数最少"）：对每个待插元素，从它的前驱开始往左数，数到第一个不大于它的元素为止，数了几个就是几次比较；若前驱本来就不大于它，只算 1 次。把 $n-1$ 个元素的次数加起来即可。序列越接近升序，这个和越小。

它比简单选择排序快在哪：只快在比较次数

"大部分元素已有序时，直接插入排序比简单选择排序效率更高"——这句话是对的，但原因只有一条，真题把三个候选理由摆出来让你挑：

理由	成立？	为什么
比较次数更少	✅	直插 $O(n)$（几乎有序时每个元素只比一两次）vs 简单选择恒为 $\frac{n(n-1)}{2}$、与初始顺序无关。这是量级差异，是决定性的
辅助空间更少	❌	两者都是 $O(1)$。直插要一个哨兵/temp，选择要一个交换用的临时变量，一个常数对另一个常数
移动次数更少	❌	简单选择的移动次数与输入无关，恒约 $3(n-1)$，是严格的 $O(n)$。而"大部分已序"$\ne$"完全已序"，错位元素的挪动累计起来完全可能达到同一量级甚至更多

🔴 第三行是这道题的真正考点：简单选择排序的移动次数是所有 $O(n^2)$ 排序里最少的，别想当然地觉得"插入排序哪儿都比选择排序好"。

什么时候该选它

真题问过"什么情况下采用直接插入排序而不采用快速排序"，四条理由全都成立：

1. 大部分元素已有序——逆序对少，内层循环几乎不执行，接近 $O(n)$；而快排在有序输入上反而退化到 $O(n^2)$。
2. 待排序元素数量很少——常数因子极小、无递归开销；快排的分区与递归开销在小规模下不划算。
3. 要求空间复杂度为 $O(1)$——直插确实是 $O(1)$；快排的递归栈平均 $O(\log n)$、最坏 $O(n)$，不是 $O(1)$。
4. 要求排序算法是稳定的——直插稳定，快排不稳定。

正因为前两条，快速排序常在子区间长度降到某个阈值时改调直接插入排序——这是工业实现里的标准做法，也是本算法在大规模场景下唯一的立足点。

反过来，它的弱项也很明确：$n$ 大且无序时明显劣于 $O(n\log n)$ 算法；记录很大时不占优，因为移动与比较同阶，此时该考虑简单选择排序。

逐趟推演与执行流程图（第一次学、或想手动模拟就展开）

排序过程示意（升序，[] 内为已排序区，| 右侧为未排序区）：

初始:  [49] | 38  65  97  76  13  27  49*
第1趟: [38  49] | 65  97  76  13  27  49*
第2趟: [38  49  65] | 97  76  13  27  49*
第3趟: [38  49  65  97] | 76  13  27  49*
第4趟: [38  49  65  76  97] | 13  27  49*
第5趟: [13  38  49  65  76  97] | 27  49*
第6趟: [13  27  38  49  65  76  97] | 49*
第7趟: [13  27  38  49  49* 65  76  97]

按带哨兵的实现逐趟走 [49, 38, 65, 97, 76, 13, 27, 49*]，并数清每趟的比较与移动：

趟 $i$	待插元素	过程	比较次数	移动次数	本趟结果
2	38	38 < 49，49 后移，38 落在位置 1	2	3	38 49 65 97 76 13 27 49*
3	65	65 > 49，前驱不大于它，整趟无动作	1	0	38 49 65 97 76 13 27 49*
4	97	97 > 65，无动作	1	0	38 49 65 97 76 13 27 49*
5	76	76 < 97：97 后移；再比 65，停	2	3	38 49 65 76 97 13 27 49*
6	13	依次越过 97、76、65、49、38 全部后移，撞上哨兵停	6	7	13 38 49 65 76 97 27 49*
7	27	依次越过 97、76、65、49、38，再比 13，停	6	7	13 27 38 49 65 76 97 49*
8	49*	越过 97、76、65；再比 49，相等，停	4	5	13 27 38 49 49* 65 76 97

合计：比较 22 次，移动 25 次。（"移动"含把待插元素存入哨兵、以及最后从哨兵取回，各计 1 次。）

第 8 趟是本例的关键：A[0] = 49* 与 A[j] = 49 比较时条件是 49 < 49，为假，循环立刻停止，49* 被放在 49 的后面——这正是稳定性的现场演示。

比较次数与移动次数的完整推导（想知道那几个精确式怎么来的就展开）

先看单趟开销。第 $i$ 趟要把 $A[i]$ 插进 $A[1..i-1]$：

• 若 $A[i]\ge A[i-1]$（已在位）：只做第 ① 行那 1 次比较，0 次移动。
• 若要越过全部 $i-1$ 个元素（$A[i]$ 是当前最小）：比较次数 $=1+(i-1)=i$；移动次数 $=1$（存哨兵）$+1$（第 ③ 行）$+(i-2)$（第 ④ 行后移）$+1$（落位）$=i+1$。

最好（初始正序）：每趟都在第 ① 行返回。

$${\text{KCN}}_{min}=n-1,{\text{RMN}}_{min}=0$$

最坏（初始逆序）：每趟都要越过前面全部元素。

$${\text{KCN}}_{max}=\sum _{i=2}^{n}i=\frac{(n+2)(n-1)}{2},{\text{RMN}}_{max}=\sum _{i=2}^n(i+1)=\frac{(n+4)(n-1)}{2}$$

平均：假设各种初始排列等概率出现，第 $i$ 趟待插元素落在 $i$ 个可能位置上的概率相等，平均越过约 $i/2$ 个元素：

$${\text{KCN}}_{\text{avg}}\approx \sum _{i=2}^n\frac{i}{2}\approx \frac{n^2}{4},{\text{RMN}}_{\text{avg}}\approx \frac{n^2}{4}$$

链式存储上的插入排序（数据在链表上时展开）

单链表上做插入排序，比顺序表还省：

• 查找插入位置：从头结点开始顺序比较，找到第一个大于待插元素的结点，记下它的前驱。仍是顺序查找，量级与顺序表相同（最坏仍 $O(n^2)$ 次比较），但具体次数不同、甚至恰好相反——顺序表从后向前扫，要越过几个元素就比几次；链表只能从前向后扫，插入位置越靠后比得越多。$n=100$ 时：正序输入顺序表版只比较 99 次而链表版要比较 4 950 次，逆序输入则是顺序表版 5 049 次、链表版 99 次。
• 插入：只需修改两个指针，移动次数为 0——顺序表上那 $O(n^2)$ 次后移全部消失。
• 代价：链表无法"从后向前扫描"，带哨兵那套写法用不上；而且对基本有序的输入，链表版每趟仍要从头扫到插入点，反而不如顺序表版快。

总复杂度仍是 $O(n^2)$（瓶颈从"移动"换成了"比较"），但当记录很大时，省掉全部移动是实打实的收益。

链表适用性是插入排序的一个独有优点：折半插入、希尔、快排、堆排都要求随机存取，无法用在链表上；直接插入、起泡、简单选择、归并、基数则可以。

考点速记

三条结论：

1. 开销正比于逆序对数——一句话解释最好 $O(n)$、平均与最坏 $O(n^2)$、以及"基本有序时最快"。
2. 前缀有序 $\ne$ 前缀就位，且后缀与初始序列逐位相同——这是它的两个指纹。
3. 它可以用于链表（移动降为 0），而折半插入、希尔、快排、堆排都不行。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 哪个序列的比较次数最少：给四个等长序列，问用直插升序排序时谁的比较次数最少。逐个元素往左数到第一个不大于它的位置为止，把 $n-1$ 个数加起来比大小。越接近升序越少。
• 直插比简单选择快的原因：三个候选理由里只有"比较次数更少"成立。辅助空间两者都是 $O(1)$；移动次数选择排序恒约 $3(n-1)$、反而更稳。
• 什么情况下用直插而不用快排：大部分已有序 ✓、元素很少 ✓、要求空间 $O(1)$ ✓、要求稳定 ✓——四条全对。
• 折半插入与直接插入的不同之处：只有比较次数不同。趟数、移动次数、辅助空间三者完全相同（详见折半插入排序）。
• 希尔排序的组内排序用什么：答直接插入排序。
• 选归并而不选插入的理由：只有"运行效率更高"成立；归并的代码更长、占用空间更多（要 $O(n)$ 辅助数组）。
• 由某趟结果反推算法：给出第二趟排序后的序列问只能是哪种算法，判据就是那两个指纹（详见由中间状态反推排序算法）。

易错："移动次数更少"不是直插胜过简单选择的理由。 简单选择的移动次数恒约 $3(n-1)$，是所有 $O(n^2)$ 排序里最少的。

易错：最好情况的移动次数是 0，不是 $n-1$。 已在位的元素连暂存动作都不做。

易错：趟数固定 $n-1$，不能提前终止。 能提前终止的是起泡排序。

教材出处

• 直接插入排序的算法步骤、带监视哨的算法描述（算法 8.1）、以 $\{49,38,65,97,76,13,27,49\}$ 为例的逐趟过程（图 8.1）：严蔚敏《数据结构（C 语言版）》（第 2 版），p237
• 最好情况比较 1 次不移动、最坏情况 $\text{KCN}=\sum _{i=2}^{n}i=(n+2)(n-1)/2$、$\text{RMN}=\sum _{i=2}^n(i+1)=(n+4)(n-1)/2$、平均均约 $n^2/4$，以及空间复杂度 $O(1)$：同书 p238
• 算法特点（稳定排序；也适用于链式存储结构，在单链表上无需移动记录只需修改指针；更适合初始记录基本有序的情况）：同书 p238

相关知识

排序的基本概念｜ 折半插入排序（只优化"查找插入位置"这一半）｜ 希尔排序（让每次插入的待越元素变少）｜ 起泡排序（同为 $O(n^2)$ 且稳定，但一次交换要 3 次赋值）｜ 简单选择排序（记录很大时反而更优）｜ 快速排序（小子表转调对象）｜ 由中间状态反推排序算法｜ 排序算法对比

相关文章

• 排序基本概念
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2026Q92分2022Q112分2020Q112分2017Q102分2015Q112分2012Q112分2009Q102分