8.2 插入排序、希尔排序·综合题讲评

折半插入用二分找到位置，但元素移动仍为O(n)，所以总时间仍O(n²)。

手工推演与代码

[1,3,5,7]插4，折半定位下标2，再右移5、7并写4。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。只因查找logn就把整体写nlogn；相等键插入位置选择破坏稳定。

迁移训练

解释折半插入比较次数下降但移动次数不变。