Appearance
折半插入排序
为什么需要折半插入排序
直接插入排序在查找插入位置时，采用顺序比较的方式，每趟最坏需要比较 i 次。而已排序的子序列本身是有序的，完全可以利用折半查找来加速定位插入位置，从而减少比较次数。
折半插入排序就是这样一种优化：用折半查找替换顺序查找来确定插入位置。408 考研中，折半插入排序是直接插入排序的重要改进版本，也是理解"查找"与"排序"结合的经典案例。
核心思想
折半插入排序的核心特点：
- 查找阶段优化：在已排序子序列中使用折半查找定位插入位置，比较次数降为 O(log i)
- 移动阶段不变：找到插入位置后，仍需逐个后移元素，移动次数与直接插入排序相同
- 稳定性保持：当待插入元素与中间元素相等时，继续在右半区间查找，保证相同元素的相对顺序不变
算法流程示意：
已排序部分: [3, 5, 8, 12, 15] 待插入: 9
折半查找过程:
low=0, high=4, mid=2 → a[2]=8 < 9 → low=3
low=3, high=4, mid=3 → a[3]=12 > 9 → high=2
low=3 > high=2 → 插入位置 = low = 3
后移元素: 12, 15 各右移一位
插入: [3, 5, 8, 9, 12, 15]交互可视化
通过下方的交互动画，你可以逐步观察折半插入排序的执行过程：
操作详解
算法思路
关键步骤：
- 从第 2 个元素开始，将其作为待插入元素暂存到
temp - 在已排序子序列
a[0..i-1]中，用折半查找确定插入位置 - 将插入位置及之后的元素依次后移一位
- 将
temp放入插入位置 - 重复上述过程直到所有元素有序
cpp
void BinaryInsertionSort(int a[], int n) {
int i, j, low, high, mid, temp;
for (i = 1; i < n; i++) {
temp = a[i]; // 暂存待插入元素
low = 0;
high = i - 1;
// 折半查找插入位置
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] > temp)
high = mid - 1; // 查找左半区间
else
low = mid + 1; // 查找右半区间（相等时也进入右半，保证稳定性）
}
// 统一后移 [low, i-1] 的元素
for (j = i - 1; j >= low; j--)
a[j + 1] = a[j];
a[low] = temp; // 插入
}
}注意：当
a[mid] == temp时，令low = mid + 1（继续在右半区间查找），这是保证排序稳定性的关键。
与直接插入排序的区别
| 对比维度 | 直接插入排序 | 折半插入排序 |
|---|---|---|
| 查找插入位置 | 顺序查找（从后往前逐个比较） | 折半查找（二分定位） |
| 比较次数 | 最坏 O(n²)，最好 O(n) | 总比较次数 O(nlog₂n) |
| 移动次数 | O(n²) | O(n²)（与直接插入相同） |
| 总时间复杂度 | O(n²) | O(n²) |
| 对初始序列的敏感性 | 序列越有序，效率越高 | 比较次数与初始序列无关，移动次数仍依赖初始序列 |
| 稳定性 | 稳定 | 稳定 |
| 适用场景 | 小规模或基本有序的数据 | 数据量不大且希望减少比较次数时 |
总结：折半插入排序仅优化了"比较"操作，"移动"操作没有改进。因此当数据量较大时，整体性能提升有限，瓶颈在于元素的移动。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(nlog₂n) | 序列有序时无需移动，仅需比较 |
| 最坏时间复杂度 | O(n²) | 序列逆序时移动次数最多 |
| 平均时间复杂度 | O(n²) | 移动操作主导整体开销 |
| 空间复杂度 | O(1) | 仅需常数级辅助变量 |
空间复杂度：O(1)，仅使用 temp、low、high、mid 等常数个辅助变量。
考研高频考点
- ⭐ 折半插入排序的比较次数与初始序列无关，仅取决于元素个数 n（选择题高频）
- ⭐ 折半插入排序的移动次数与直接插入排序相同，时间复杂度仍为 O(n²)（判断题/选择题）
- ⭐ 折半插入排序是稳定的排序算法（排序稳定性对比题必考）
- 折半插入排序与直接插入排序的区别与联系（简答题/综合题）
- 排序算法的比较次数、移动次数分别受什么因素影响（概念辨析题）