题目

设数组 S[] = {93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892}, 采用最低位优先(LSD)基数排序将 S 排列成升序序列。第 1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是 ( )。

错因

A

桶倒序收集。把"升序基数排序"误执行为"按个位 9, 8, …, 0 降序收集"，得到 …, 43（桶 3 的末尾）, 372（桶 2）, 892（桶 2）, …。372 之后 892 是对的（同桶且 372 先入桶），但前面应是同桶之外、桶序更小的桶——升序对应桶 1 的末尾 301，不是降序对应桶 3 的末尾 43。LSD 升序时桶号必须按 0, 1, …, 9 递增收集。

B

误用了 MSD（最高位优先）而不是 LSD。按最高位（百位）分配：372 落入百位 3 的桶里，与 301、327 同桶；按原序桶内 372 是第一个，所以前一位是百位 2 桶的末尾 236，后一位是百位 3 桶里 372 之后的 301。题目明确写"最低位优先"，LSD 第 1 趟看的是个位，不是百位。

D

前后邻居都错位。可能同时犯了两种错误：① 把 372 误认作个位 5 的桶（看成 372 个位 = 5），落到 485 之后变成 485 在 372 前；② 又把 301 当成 372 的后邻。本质问题是没动手把每个元素的个位真正算一遍——LSD 第 1 趟前先列出每个元素的个位，分配时就不会错。

总解析

思路：LSD（Least Significant Digit）基数排序第 1 趟看个位：先按个位把元素分配到 0–9 共 10 个桶（桶内保持原序），再按桶号 0, 1, …, 9 顺序收集。

第一步：取每个元素的个位。

元素	93	946	372	9	146	151	301	485	236	327	43	892
个位	3	6	2	9	6	1	1	5	6	7	3	2

第二步：分配到 10 个桶（按原序入桶）。

桶	内容（按入桶先后）
0	（空）
1	151, 301
2	372, 892
3	93, 43
4	（空）
5	485
6	946, 146, 236
7	327
8	（空）
9	9

第三步：按桶号 0→9 顺序收集。

第 1 趟结果序列：

151, 301, 372, 892, 93, 43, 485, 946, 146, 236, 327, 9

第四步：定位 372 的前后邻居。

• 前：桶 2 内 372 是第 1 个元素，所以前邻居是上一个非空桶（桶 1）的末尾元素 → 301
• 后：桶 2 内 372 之后紧跟 → 892

最终答案是 C（301, 892）。

小结：LSD 第 1 趟做完后还没有真正排好序——只是按个位分组。后续还要按十位、百位继续分配收集，三趟下来才得到整体升序。本题只问第 1 趟结束的中间状态。