13 希尔排序
增量分组、间隔插入与稳定性反例
第 01 题 问题 1
gap=4 时，索引 1 与哪些索引属于同组？
参考答案
1、5、9、13……。
解析
同组索引对 gap 取模的余数相同；不是连续的四项分块。
第 02 题 问题 2
数组 gap=2 有序，是否必然整体升序？
参考答案
不必然。
解析
例如 [1,4,2,5] 的偶数组 [1,2] 与奇数组 [4,5] 都有序，但 4>2。
第 03 题 问题 3
原书 [55,74,3,45,13,87,46,30] 经 gap=4 排序后的结果？
参考答案
[13,74,3,30,55,87,46,45]。
解析
分别排序索引 (0,4)、(1,5)、(2,6)、(3,7)，其他组彼此还未比较。
第 04 题 问题 4
完成 gap=2 后，再做 gap=1 有什么意义？
参考答案
最后一次是对整个列表做插入排序，保证全局有序。
解析
前面的大 gap 只做预处理；不能省去最终覆盖全局的 gap=1。
第 05 题 问题 5
长度 8 的折半增量是什么？
参考答案
[4,2,1]。
解析
8//2=4，逐次整数除以 2，直到 0。
第 06 题 问题 6
本教材 knuth_gaps(50) 返回什么？
参考答案
[40,13,4,1]。
解析
按 3h+1 生成小于 50 的项，再逆序使用。
第 07 题 问题 7
本教材的 Knuth 起点与原书 n/9 附近起点相同吗？
参考答案
不完全相同。
解析
本教材采用小于 n 的最大项；原文起点是经验性实现选择，不能把它当作唯一正确条件。
第 08 题 问题 8
为什么 4、2 的分组不会混合奇偶位置？
参考答案
两个 gap 都是偶数，沿 gap 移动不改变索引奇偶性。
解析
只有最终 gap=1 才让这些组充分混合；增量关系影响性能。
第 09 题 问题 9
最后 gap=1 使用稳定插入，整个希尔排序因此稳定吗？
参考答案
不稳定。
解析
大 gap 可能已经改变相等键的原顺序，最后一轮无法恢复历史信息。
第 10 题 问题 10
对 [2A,2B,1X,3Y] 用 gap=2、1，最终相等键次序是什么？
参考答案
2B 在 2A 之前。
解析
gap=2 把 1X 前移，2A 移到索引 2；gap=1 会保留当时 2B、2A 的次序。
第 11 题 问题 11
所有希尔排序都能直接写成 O(n^1.5) 吗？
参考答案
不能。
解析
复杂度依增量序列与实现；经典折半增量的最坏情况可以为 O(n²)。
第 12 题 问题 12
若 gap 序列仅为 [4,2]，有哪些正确性风险？
参考答案
可能只做到各间隔组有序，整体仍有逆序。
解析
序列最终应包含 1；而且 gap 必须为正整数。