题目

对含 9 个关键字的初始序列进行排序，若序列的变化情况如下表所示，则采用的排序算法是（）。

阶段	序列
初始序列	5, 25, 40, 30, 10, 20, 45, 15, 35
第 1 趟排序后	5, 10, 20, 30, 15, 35, 45, 25, 40
第 2 趟排序后	5, 10, 15, 25, 20, 30, 40, 35, 45

错因

B

基数排序按"位"分桶。题中所有值都是 5 的倍数（个位非 0 即 5），第一趟按个位分桶后必然得到先 0 后 5（或反之）的稳定划分：40,30,10,20 拼接 5,25,45,15,35——和题干第 1 趟差异极大，不可能产生题干形态。

C

归并排序自底向上每趟把相邻两个有序段合并。第 1 趟应得到长度 2 的有序段拼接：[5,25][30,40][10,20][15,45][35] = 5,25,30,40,10,20,15,45,35，与题干第 1 趟 5,10,20,30,15,35,45,25,40 完全不同。题干第 1 趟里 5,10,20,30 跨越了原始多个长度-2 段，不是归并能产生的形态。

D

折半插入排序的"第 趟"会让前 个元素严格有序，其余元素保持原始位置不动。题干第 1 趟里 5、10、20、30 以及 35、45 等多个元素都已移位，远超"前 2 个有序、其余原样"的折半插入产物。

总解析

思路：识别题型时按"每一趟使序列子结构发生了什么样的变化"反推算法。

第 1 趟核对（增量 = 3 的希尔排序）：

把下标 0~8 按 mod 3 = 0/1/2 分成三组，组内做插入排序：

组	下标	原值	组内排序后
0		5, 30, 45	5, 30, 45
1		25, 10, 15	10, 15, 25
2		40, 20, 35	20, 35, 40

按下标回填：

下标	0	1	2	3	4	5	6	7	8
值	5	10	20	30	15	35	45	25	40

= 5, 10, 20, 30, 15, 35, 45, 25, 40 ✓ 与题干第 1 趟完全一致。

第 2 趟核对（增量 = 2 的希尔排序）：

继续在第 1 趟结果上按 mod 2 = 0/1 分组，组内做插入排序：

组	下标	排序前	排序后
0		5, 20, 15, 45, 40	5, 15, 20, 40, 45
1		10, 30, 35, 25	10, 25, 30, 35

回填：5, 10, 15, 25, 20, 30, 40, 35, 45 ✓ 与题干第 2 趟完全一致。

结论：本题为希尔排序，使用增量序列 3, 2, 1（最后一趟未列出，会得到完全有序的升序序列）。

最终答案是 A。