题目

对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。

错因

A

误以为折半"快"会减少趟数。但插入排序的趟数 = 待插入元素数 = ，与"如何找位置"完全无关——每趟都要把一个新元素插到已排序部分。无论是直接插入（顺序找）还是折半插入（二分找），都得这么走 趟。

B

误以为折半找到位置后能少移动。移动次数取决于位置，不取决于查找方式——找到位置后，把目标位置之后的元素全部右移 1 位是物理必然，与你怎么找到这个位置无关。直接插入和折半插入的元素移动总次数完全相同。

C

误以为折半需要额外的辅助空间。两者都只需要 1 个临时变量缓存当前要插入的元素（temp = a[i]），空间复杂度都是 。折半的"二分查找"逻辑在原数组上做不需要额外空间。

总解析

直接插入 vs 折半插入的差异点：唯一不同的是查找插入位置的方式——

• 直接插入：从已排序段尾部往前线性扫描，找到合适位置（ 当前值的第一个位置）。第 趟最坏比较 次，最好 1 次。
• 折半插入：在已排序段上二分查找插入位置。第 趟比较次数固定 （不论数据初始顺序）。

维度	直接插入	折半插入
总趟数		✓ 相同
元素移动次数	同位置同移动	同位置同移动 ✓ 相同
辅助空间		✓ 相同
比较次数	最坏 、最好	始终 ✗ 不同

为什么只有比较次数不同？

• 比较次数取决于"查找过程怎么走"——直接插入逐个比，折半插入按 收敛
• 移动次数取决于"找到位置后要挤开几个元素"——位置一样移动量一样
• 趟数取决于"要插入的元素数量"——都是
• 辅助空间取决于"暂存当前元素"——一个变量足够

速记：折半插入的优势只有"比较次数少"——但这个优势在大 时并不显著，因为移动开销没变，整体仍是 。教材里折半插入主要是用来对比"二分思想能否提速排序"的反例（答案：单纯改查找无济于事，得改"分治+合并"才行，那就是归并排序了）。

最终答案是 D。