8.2 插入排序、希尔排序·选择题讲评

插入题看移动而非交换；希尔题先按下标同余分组。近乎有序是插入排序优势。

手工推演与代码

长度n逆序时插入比较/移动为平方量级；完全有序只需n-1次关键比较。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。把哨兵位置算数据；希尔相邻元素分组；声称希尔稳定。

迁移训练

哪个适合小规模近乎有序表？答案直接插入排序。