折半插入排序

2026 大纲 七（三）折半插入排序（插入排序的基本框架见《直接插入排序》，折半查找本身见《折半查找》）。

只优化了一半的算法

直接插入排序的每一趟做两件事：查找插入位置，然后移动元素给它腾地方。

折半插入排序只动了前一半——把顺序查找换成折半查找，后移那个循环一行都没改。

于是比较次数从 $\mathrm{\Theta }(n^2)$ 降到了 $\mathrm{\Theta }(n{\log }_{2}n)$。但总复杂度呢？

🔴 仍然是 $O(n^2)$。因为复杂度由没被优化的那一半决定。 移动次数一次都没省，$\mathrm{\Theta }(n^2)$ 的移动压倒了 $\mathrm{\Theta }(n{\log }_{2}n)$ 的比较。

这是本篇最值得迁移出去的一句话：优化一个由两部分组成的过程时，只压低其中一部分，总量级不会变——瓶颈会自动转移到另一部分身上。

它还带来一个反直觉的后果：

🔴 最好情况是 $\mathrm{\Theta }(n{\log }_{2}n)$，不是 $O(n)$。 直接插入排序有一句 if (A[i] < A[i-1]) 可以整趟跳过，折半插入没有——每个元素都必须走一遍折半查找。所以序列基本有序时，它反而比直接插入排序慢。

先动手看一眼

加载可视化中...

代码与四处要点

void BinaryInsertionSort(int a[], int n) {
    int i, j, low, high, mid, temp;
    for (i = 1; i < n; i++) {        // 共 n-1 趟，趟数与初始序列无关
        temp = a[i];                 // 暂存待插入元素：a[i] 随后会被覆盖
        low = 0;
        high = i - 1;                // 在有序区 a[0..i-1] 中折半查找
        while (low <= high) {        // 区间为空时退出，此时 low 就是插入位置
            mid = (low + high) / 2;
            if (a[mid] > temp)
                high = mid - 1;      // 待插元素更小，去左半区
            else
                low = mid + 1;       // a[mid] <= temp，去右半区
                                     // 相等时也走这一支 —— 稳定性的关键
        }
        for (j = i - 1; j >= low; j--)
            a[j + 1] = a[j];         // 统一把 a[low..i-1] 整体后移一位
        a[low] = temp;               // 落位
    }
}

第一，循环结束时 low 恰好停在"第一个大于待插元素的位置"，而 high = low - 1 停在"最后一个不大于待插元素的位置"。所以插入点取 low（等价地取 high + 1）。

第二，稳定性就在那个 else 分支。 a[mid] == temp 时归入 else（往右半区继续找），最终 low 会停在所有与 temp 相等的元素之后。若写成 if (a[mid] >= temp) high = mid - 1;，相等元素会被划进"待越过"的一侧，插入位置落到它们前面——{2a, 2b} 正确版插入位置为 1、输出 2a, 2b，错误版为 0、输出 2b, 2a。

第三，三个边界都自洽。 i = 1 时区间只有一个元素，1 次比较后必然退出；待插元素比所有元素都小时 high 一路减到 $-1$、low 保持 0，全部右移后 a[0] = temp；待插元素比所有元素都大时 low 一路加到 $i$，后移循环初值 j = i-1 < low，一次都不执行——这正是"正序输入 0 次后移"的来源。n <= 1 时外层循环不执行，安全。

第四，它没有那句快速跳过。 直接插入排序开头的 if (A[i] < A[i-1]) 在这里不存在，这就是"最好情况仍是 $\mathrm{\Theta }(n{\log }_{2}n)$"的直接原因。

一个算法里，两个指标的敏感性正好相反

这是折半插入排序最有教学价值的地方，也是"比较次数和移动次数必须分开数"的最好例证。

比较次数几乎与初始序列无关。 折半查找的执行路径由区间长度驱动：长度为 $m$ 的区间取中点后排除中点自身，剩下左半或右半。不论关键字取什么值，区间长度都按对半的速度收缩到 0，因此第 $i$ 趟的比较次数上界是 $\lfloor {\log }_2(i-1)\rfloor +1$，总计

$$\text{KCN}=\sum _{i=2}^n(\lfloor {\log }_2(i-1)\rfloor +1)=\mathrm{\Theta }(n{\log }_{2}n)$$

移动次数完全依赖初始序列。 后移循环执行 $i-low$ 次，而这恰是"待插元素前面有多少个比它大的元素"，也就是它贡献的逆序对数——与直接插入排序完全相同：

$${\text{RMN}}_{min}=0(\text{正序}),{\text{RMN}}_{\text{avg}}\approx \frac{n^2}{4},{\text{RMN}}_{max}\approx \frac{n^2}{2}(\text{逆序})$$

对照一下就很清楚：$n=8$ 时折半插入的比较次数总在 13～17 之间浮动，而直接插入排序正序只要 7 次、逆序要 35 次——差整整一个数量级。

⚠️ 一处要说准的细节：待查区间长度为偶数时，左右两半差一个元素，走左边和走右边的后续比较次数可能差 1 次。所以严格说总比较次数会在一个小范围内浮动，不是恒定值。最小的例子：$n=3$ 时 [2, 3, 1] 比较 2 次，[2, 3, 4] 比较 3 次。但这不影响结论——量级与主项只由 $n$ 决定。

汇总成表：

指标	最好	平均	最坏
时间	$O(n{\log }_{2}n)$	$O(n^2)$	$O(n^2)$
比较次数	$\mathrm{\Theta }(n{\log }_{2}n)$	$\mathrm{\Theta }(n{\log }_{2}n)$	$\mathrm{\Theta }(n{\log }_{2}n)$
移动次数	0	约 $n^2/4$	约 $n^2/2$
空间	$O(1)$	$O(1)$	$O(1)$

与直接插入排序的四项对照

真题正面考过"对同一待排序序列分别做折半插入和直接插入，两者可能的不同之处是什么"，四个候选里只有一个成立：

对照项	是否不同	为什么
排序的总趟数	❌ 相同	两者都固定 $n-1$ 趟，与初始序列无关
元素的移动次数	❌ 相同	后移循环一行没改，都等于逆序对数
辅助空间的数量	❌ 相同	都只需一个暂存单元，$O(1)$
元素之间的比较次数	✅ 不同	$\mathrm{\Theta }(n{\log }_{2}n)$ vs $n-1\sim \mathrm{\Theta }(n^2)$

折半插入唯一改变的就是比较次数，这也正是它存在的全部意义。

只能用顺序表

折半查找每一步都要取出区间中点 a[mid]。顺序表上这是 $O(1)$ 的下标运算；链表上要从头结点走 mid 步，单次取中点就要 $O(n)$——"折半"省下的比较次数，会被"找中点"的遍历吃干净，还不如直接顺序扫。

所以直接插入排序可以用于链表（甚至因为不用后移而更划算），折半插入不行。需要随机存取的还有希尔排序、快速排序、堆排序。

适用场景：$n$ 不太大、初始无序、且比较代价明显高于移动代价（比如关键字是长字符串，比一次要逐字符扫）。⚠️ 初始基本有序时不适合（不如直接插入），$n$ 很大时也救不了（瓶颈在移动）。

逐趟推演与两种查找方式的流程对照（第一次学、或想手动模拟就展开）

把 9 插进已排好的 [3, 5, 8, 12, 15]：

已排序区: [3, 5, 8, 12, 15]    待插入: 9

折半查找过程（区间用下标 [low, high] 表示）:
  low=0, high=4, mid=2 → a[2]=8  ≤ 9  → low = mid+1 = 3
  low=3, high=4, mid=3 → a[3]=12 > 9  → high = mid-1 = 2
  low=3 > high=2 → 循环结束，插入位置 = low = 3

后移元素: 把 a[3..4] 即 12, 15 各右移一位
插入:     [3, 5, 8, 9, 12, 15]

以 [49, 38, 65, 97, 76, 13, 27, 49*] 为例（49* 是第二个 49）：

趟 $i$	待插	有序区	折半查找过程	插入位置	后移个数	本趟结果
1	38	[49]	mid=0：49 > 38 → high=−1	0	1	38 49 65 97 76 13 27 49*
2	65	[38,49]	mid=0：38 ≤ 65 → low=1；mid=1：49 ≤ 65 → low=2	2	0	38 49 65 97 76 13 27 49*
3	97	[38,49,65]	mid=1：49 ≤ 97 → low=2；mid=2：65 ≤ 97 → low=3	3	0	38 49 65 97 76 13 27 49*
4	76	[38,49,65,97]	mid=1：49 ≤ 76 → low=2；mid=2：65 ≤ 76 → low=3；mid=3：97 > 76 → high=2	3	1	38 49 65 76 97 13 27 49*
5	13	[38,49,65,76,97]	mid=2：65 > 13 → high=1；mid=0：38 > 13 → high=−1	0	5	13 38 49 65 76 97 27 49*
6	27	[13,38,49,65,76,97]	mid=2：49 > 27 → high=1；mid=0：13 ≤ 27 → low=1；mid=1：38 > 27 → high=0	1	5	13 27 38 49 65 76 97 49*
7	49*	[13,27,38,49,65,76,97]	mid=3：49 ≤ 49* → low=4；mid=5：76 > 49* → high=4；mid=4：65 > 49* → high=3	4	3	13 27 38 49 49* 65 76 97

第 7 趟是稳定性的现场：a[mid] = 49 与 temp = 49* 相等，条件 a[mid] > temp 为假，走 low = mid + 1 这一支，插入位置落在 49 的右边。

考点速记

三条结论：

1. 只优化了一半，复杂度由没被优化的另一半决定——移动次数仍是 $\mathrm{\Theta }(n^2)$。
2. 比较次数几乎与初始序列无关、移动次数完全依赖初始序列，两者在同一个算法里并存。
3. 最好情况是 $\mathrm{\Theta }(n{\log }_{2}n)$ 不是 $O(n)$，所以基本有序时它反而慢于直接插入排序。

这一节在 408 真题里不单独成题——下方「真题练习」是空的，这不是漏挂。它出现的位置只有一个，而且挂在直接插入排序那一篇下：

• 折半插入与直接插入"可能的不同之处"是什么：四个候选是排序总趟数、元素移动次数、辅助空间数量、元素间比较次数。只有比较次数不同，另外三项完全相同。做这类题的关键是记住"它只换掉了查找那一半"。

另外它还会在两处作为对照项出现：《排序算法对比》里的稳定性与复杂度总表；以及"哪些算法只能用于顺序存储"这类判断（折半插入、希尔、快排、堆排都要随机存取）。

复习优先级：把上面那张四项对照表和"最好是 $n{\log }_{2}n$"这两条记住即可，不必花时间练手工模拟。

易错：它的最好情况不是 $O(n)$。 没有快速跳过那一句，每个元素都得走完折半查找。

易错：移动次数与直接插入完全相同。 折半只省比较，一次移动都没省。

易错：它不能用于链表。 链上取中点是 $O(n)$，省下的比较全被吃掉。

教材出处

• 折半插入排序的算法步骤与算法描述（算法 8.2）：严蔚敏《数据结构（C 语言版）》（第 2 版），p238–p239
• "折半插入排序所需要的关键字比较次数与待排序序列的初始排列无关，仅依赖于记录的个数"、"折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列"、"在平均情况下，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变，因此时间复杂度仍为 $O(n^2)$"、空间复杂度 $O(1)$：同书 p239
• 算法特点（稳定排序；因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构；适合初始记录无序、$n$ 较大时的情况）：同书 p239
• 各种内部排序方法比较表中折半插入排序"最好 $O(n{\log }_{2}n)$、最坏与平均 $O(n^2)$、空间 $O(1)$、稳定"：同书 p267

相关知识

直接插入排序（本篇的基础版本，移动次数逐记录相同）｜ 折半查找（查找阶段所用方法的完整分析）｜ 希尔排序（另一条改进路线：减少移动而非减少比较）｜ 排序的基本概念｜ 排序算法对比｜ 由中间状态反推排序算法（与直接插入的中间状态完全一致，无法区分）

相关文章

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

交互体验

前往完整可视化页面 →

真题练习