题目

用希尔排序方法对一个数据序列进行排序时，若第 1 趟排序结果为 9,1,4,13,7,8,20,23,15，则该趟排序采用的增量(间隔)可能是()

错因

A

没真正按 d=2 分组验证。按 d=2 分两组：

• 组 1（下标 0,2,4,6,8）：9, 4, 7, 20, 15 —— 9>4 不递增 ✗
• 组 2（下标 1,3,5,7）：1, 13, 8, 23 —— 13>8 不递增 ✗

两组都没排好，d=2 不可能。

C

按 d=4 分四组：

• 组 1（下标 0,4,8）：9, 7, 15 —— 9>7 不递增 ✗
• 其他组也无需再看

d=4 不成立。

D

按 d=5 分五组：

• 组 1（下标 0,5）：9, 8 —— 9>8 不递增 ✗

d=5 不成立。

选这些选项的人通常没逐组分写，只凭"序列整体看起来差不多有序"就猜。希尔排序判增量必须严格按下标 mod d 分组逐一验证。

总解析

希尔排序的核心性质：

第 k 趟用增量 时，把数组按下标 分成 组，每组内部进行直接插入排序。一趟做完后，每个组内必须有序（升序），但组间可能交错。

反推增量的方法：拿"该趟结果"，分别尝试每个候选 d，按下标 mod d 分组，所有组都内部有序的 d 才是可能的。

已知：第 1 趟结果（下标 0..8）= 9, 1, 4, 13, 7, 8, 20, 23, 15

逐增量验证：

d = 3（候选答案）：

组	下标	元素	是否升序
0	0, 3, 6	9, 13, 20	✓
1	1, 4, 7	1, 7, 23	✓
2	2, 5, 8	4, 8, 15	✓

全部组内部递增 → d = 3 可行。

d = 2：

组	下标	元素	是否升序
0	0, 2, 4, 6, 8	9, 4, 7, 20, 15	✗（9>4）

直接否决。

d = 4：

组	下标	元素	是否升序
0	0, 4, 8	9, 7, 15	✗（9>7）

直接否决。

d = 5：

组	下标	元素	是否升序
0	0, 5	9, 8	✗（9>8）

直接否决。

解题速记：希尔排序"反推增量"题的标准做法——

1. 把候选 d 一一拿出来
2. 按下标 mod d 分组（最快的方法是从下标 0 开始每隔 d 取一个数）
3. 任何一组内部出现"大数后跟小数"立即否决
4. 全部组都升序的 d 就是可能的增量

最终答案是 B（3）。