| 项目 | 值 |
|---|---|
| 核心思想 | 用折半查找确定插入位置，减少比较次数 |
| 最好时间 | $O(n\log n)$（比较次数） |
| 最坏时间 | $O(n^2)$（移动次数不变） |
| 平均时间 | $O(n^2)$（移动仍是瓶颈） |
| 空间 | $O(1)$ |
| 稳定性 | ✅ 稳定 |
| 改进点 | 减少比较次数，不减少移动次数 |
折半插入排序是直接插入排序的改进版本。它利用已排序子序列的有序性，用折半查找（二分查找）代替逐个比较来确定插入位置。
核心改进：直接插入排序在已排序部分从后往前逐个比较找位置（$O(n)$ 次比较），折半插入排序用二分查找找位置（$O(\log n)$ 次比较）。
void BinaryInsertSort(int A[], int n) {
int i, j, low, high, mid;
for (i = 2; i <= n; i++) {
A[0] = A[i]; // 暂存待插入元素
low = 1; high = i - 1; // 在已排序部分折半查找
while (low <= high) { // 找插入位置
mid = (low + high) / 2;
if (A[mid] > A[0]) high = mid - 1;
else low = mid + 1;
}
for (j = i-1; j >= high+1; j--) // 后移
A[j+1] = A[j];
A[high+1] = A[0]; // 插入
}
}对 49, 38, 65, 97, 76, 13, 27, 49* 排序：
i=2: 待插入38，已排序[49]
折半查找：low=1, high=1, mid=1, A[1]=49>38 → high=0
插入位置：high+1=1，38插入位置1
结果：[38 49] 65 97 76 13 27 49*
i=3: 待插入65，已排序[38, 49]
折半查找：low=1, high=2, mid=1, A[1]=38<65 → low=2
mid=2, A[2]=49<65 → low=3, low>high停止
插入位置：high+1=3（原位置不变）
结果：[38 49 65] 97 76 13 27 49*
i=5: 待插入76，已排序[38, 49, 65, 97]
折半查找：找到插入位置在65和97之间
结果：[38 49 65 76 97] 13 27 49*| 性质 | 说明 |
|---|---|
| 比较次数 | $O(n\log n)$，每轮折半查找 $O(\log i)$ |
| 移动次数 | $O(n^2)$，与直接插入相同 |
| 总时间 | $O(n^2)$，移动是瓶颈 |
| 空间 | $O(1)$ |
| 稳定性 | 稳定 |
| 比较项 | 直接插入 | 折半插入 |
|---|---|---|
| 比较次数 | $O(n^2)$ | $O(n\log n)$ |
| 移动次数 | $O(n^2)$ | $O(n^2)$ |
| 总时间 | $O(n^2)$ | $O(n^2)$ |
| 稳定性 | 稳定 | 稳定 |