8.2.3 希尔排序

希尔排序按递减增量把远距离元素分组做插入，最后增量1。它打破相等记录相对次序，通常不稳定；复杂度依赖增量序列。

手工推演与代码

[9,1,8,2,7,3]增量3时分别排序(9,2),(1,7),(8,3)，得[2,1,3,9,7,8]。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。把分组理解成连续分块；漏掉最终增量1；无条件写固定nlogn。

迁移训练

增量2时下标0,2,4属于一组。对[5,4,3,2,1]列出分组并排序。