基数排序

2026 大纲 七（十）基数排序。

不比较关键字，按它的取值分桶

前面九种排序全部建立在比较关键字之上，因而受 $\mathrm{\Omega }(n{\log }_{2}n)$ 下界约束。基数排序换了信息来源：它不比较关键字，而是根据关键字各位的值，通过若干趟"分配"与"收集"完成排序。信息来源从"两两比较的结果"换成了"关键字自身的取值"，下界自然管不着。

每一趟做两件事：

• 分配：扫描序列，按当前位的值 $v$ 把元素追加到第 $v$ 号队列的队尾；
• 收集：按队列编号 $0\to r-1$、队列内部先进先出，依次取出串接。

其中 $d$ = 关键字位数（也是趟数），$r$ = 基数（每位的取值个数，也是队列个数）。"基数"这个名字指的就是 $r$。

🔴 两个"顺序"缺一不可：队列之间按编号从小到大 → 提供本趟的排序效果；队列内部先进先出 → 提供稳定性。下一节会看到，后者是它能正确工作的前提，不是附赠品。

默认口径：没有特别说明时，基数排序指 LSD（最低位优先）。

先动手看一眼

加载可视化中...

稳定性是正确性前提，不是附赠品

这是本篇最核心的一句话。

归纳证明：设第 $k$ 趟开始前，序列已按低 $k-1$ 位有序（$k=1$ 时平凡成立）。第 $k$ 趟按第 $k$ 位分配：

• 第 $k$ 位不同的元素被分进不同队列，收集时按队列编号排序 $\Rightarrow$ 第 $k$ 位的大小关系正确；
• 第 $k$ 位相同的元素进同一个队列。它们的大小关系应当由低 $k-1$ 位决定，而它们进入队列的次序正是"按低 $k-1$ 位有序"的次序。只要队列先进先出（稳定），这个次序就被原样保留 $\Rightarrow$ 低 $k-1$ 位的大小关系也正确。

两条合起来：第 $k$ 趟后序列按低 $k$ 位有序。归纳完成，$d$ 趟后按全部 $d$ 位有序。∎

不稳定会怎样——对 {11, 21, 12} 做两趟 LSD：

趟	分配	收集
1（个位）	桶1：11, 21；桶2：12	11, 21, 12
2（十位）稳定	桶1：11, 12（进桶次序保持）；桶2：21	11, 12, 21 ✓
2（十位）不稳定	桶1：12, 11（次序被打乱）；桶2：21	12, 11, 21 ✗

第 2 趟只看十位，11 与 12 的十位相同，谁在前完全由"进桶时的次序"决定；一旦这个次序被打乱，第 1 趟按个位排好的成果就白费了。

🔴 其他算法是"稳定性是一个附带的好性质"，基数排序是"稳定性是它能正确工作的前提"。 这两者的分量完全不同。

中间状态：只在"末 $k$ 位"上有序

由不变量直接得到识别它的唯一线索：

第 $k$ 趟后，序列按关键字的低 $k$ 位整体有序。

⚠️ 完整关键字的大小关系可能仍然很乱——第 1 趟后 930 可能排在最前面（个位是 0）。只有"捂住高位、只看末 $k$ 位"才看得出有序。

一趟到位 0 个：每趟所有元素都会被重新分配一次，没有哪个元素能提前锁定最终位置。

做题的两种问法都靠这条：

问法一：给出关键字序列，问第 $k$ 趟分配收集后的结果。 老实按位分桶，注意桶内保持进入次序。以 110, 119, 007, 911, 114, 120, 122 为例，问第 2 趟（十位）后的结果：

第 1 趟（个位）后：110, 120, 911, 122, 114, 007, 119 （个位 0 的：110、120；个位 1 的：911；个位 2 的：122；个位 4 的：114；个位 7 的：007；个位 9 的：119。）

第 2 趟按十位分桶：

桶	0	1	2
元素	007	110, 911, 114, 119	120, 122

收集得 007, 110, 911, 114, 119, 120, 122。注意 1 号桶里四个元素的次序完全沿用第 1 趟的结果——这就是稳定性在起作用。

问法二：问某个元素的前后邻居。 只需算出该趟所依据的那一位，找出同桶且相邻的元素即可，不必把整个序列排完。

一个新的用法：多关键字排序

真题出过一道很实在的应用题：$n$ 名学生各有课程 1 成绩 $C_1$ 与课程 2 成绩 $C_2$，要求先按 $C_1$ 升序，$C_1$ 相同则按总分 $C_1+C_2$ 升序，问最适合的算法。

答案是基数排序，而做法就是 LSD 思想的直接搬用：

1. 第一趟：以"总分"为关键字，对所有记录做稳定排序；
2. 第二趟：以"$C_1$"为关键字，对上一趟结果再做稳定排序。

为什么对：第二趟按 $C_1$ 排，稳定性保证 $C_1$ 相同时原有相对顺序不变——而原有顺序正是第一趟排好的总分升序。两遍稳定排序合起来恰好满足需求。

⚠️ 次序不能反：先排次关键字，再排主关键字。反过来做，第二趟会把第一趟按主关键字排好的结果打乱。

另外三个候选（快速、希尔、选择）都不稳定，也都不是为多关键字设计的。虽然改写比较函数也能完成任务，但题目问的是"最适合"，答基数排序。

"线性时间"是有前提的

时间 $O(d(n+r))$：每趟分配要扫描 $n$ 个记录（$O(n)$），收集要遍历 $r$ 个队列（包括空队列，也得看一眼才知道是空的，$O(r)$），共 $d$ 趟。

趟数由 $d$ 固定，每趟的分配收集与元素取值无关，所以：

🔴 三种情况完全一样，与初始序列完全无关。 而且移动次数也与初始排列次序无关——这一条被真题单独问过：四个候选（直接插入、冒泡、基数、快速）里只有基数排序的元素移动次数不受初始次序影响。

⚠️ 注意与简单选择排序区分：后者是比较次数与初始序列无关，移动次数仍随输入变；基数排序是两者都无关。

什么时候真的划算？ 当 $d$ 与 $r$ 都可视为常数时 $O(d(n+r))$ 退化成 $O(n)$，线性优于任何比较排序。但有两个隐含代价：

• $d$ 大时不划算：关键字若是 32 位整数按十进制拆，$d=10$，等于把序列完整扫 10 遍；而 $n=1000$ 时 ${\log }_{2}n\approx 10$，快排一遍也差不多。
• $r$ 大时不划算：每趟都要遍历全部 $r$ 个队列，$r$ 远大于 $n$ 时（比如按 32 位整数一次分配，$r=2^{32}$），$O(r)$ 这一项会压倒一切。

所以它最适合 $n$ 很大而关键字位数较少的序列。

使用条件也很严，教材专门强调："需要知道各级关键字的主次关系和各级关键字的取值范围。"展开来说：关键字必须能拆成有限位、每位取值范围有限且已知；各位之间的主次关系必须明确；关键字取值范围为无穷集合时无法使用（例如任意精度实数）。这三条把它的适用面限制得很窄，也解释了它虽是线性时间却不是通用排序算法。

空间有两种口径，答题时看清问的是哪一种：

口径	结果	内容
只算队列	$O(r)$	$r$ 个队列的头尾指针（共 $2r$ 个）
链式基数排序的完整开销	$O(n+r)$	上面的 $2r$ 个指针，加上每条记录多带的一个 next 指针域

教材给的是后者。没说明时按 $O(r)$。

存储结构：顺序、链式均可，链式更自然——分配收集只改指针、不移动记录，记录再大也无所谓。

从扑克牌看多关键字排序：MSD 与 LSD 的分野（第一次学就展开）

扑克牌的次序关系为

$$\mathrm{♣}2<\mathrm{♣}3<\cdots <\mathrm{♣}A<\mathrm{♢}2<\cdots <\mathrm{♢}A<\mathrm{♡}2<\cdots <\mathrm{♡}A<\mathrm{♠}2<\cdots <\mathrm{♠}A$$

每张牌有两个"关键字"：花色（$\mathrm{♣}<\mathrm{♢}<\mathrm{♡}<\mathrm{♠}$）和面值（$2<3<\cdots <A$），且花色的地位高于面值。把牌整理成这个次序有两种办法：

方法	做法	特点
最高位优先 MSD	先按花色分成有次序的 4 堆，再分别对每一堆按面值整理	要递归地处理每一堆，堆内还要再分堆，实现复杂
最低位优先 LSD	先按面值分成 13 堆，按面值次序叠起来收集；再重新按花色分成 4 堆，按花色次序收集	分配与收集交替进行，全程只对整个序列操作，不用递归，实现简单

LSD 的神奇之处：第二趟只按花色分堆、完全不看面值，为什么最后面值也是有序的？因为第一趟收集后序列已按面值有序；第二趟把它们按花色分进 4 个队列（先进先出），同一花色的牌保持了进入队列的先后次序，也就是面值次序。

把单关键字拆成多关键字：$0\sim 999$ 的整数可看成 $(K^0,K^1,K^2)$ 三个关键字（百、十、个位），每位取值 $0\sim 9$；5 个字母组成的单词可看成 5 个关键字，每位取值 'A' ~ 'Z'。

MSD 为什么麻烦：它先按最高位分堆，堆与堆之间的次序已经定死，接下来只能在每个堆内部独立地继续排下一位——这是一个递归过程，需要维护递归栈和大量子区间边界。它的好处是可以提前剪枝（某堆只剩一个元素就不用再分），所以"大多数记录的最高位关键字互不相同"时反而更快。教材的实用建议是：关键字很大时，可以先按最高位关键字把序列分成若干小的子序列，再对每个子序列用直接插入排序。

三趟分配与收集的完整推演（想手动模拟就展开）

以 {278, 109, 063, 930, 589, 184, 505, 269, 008, 083} 为例（$n=10$，$d=3$，$r=10$，LSD 方式）。

第 1 趟——按个位分配与收集：

桶	0	1	2	3	4	5	6	7	8	9
元素	930			063, 083	184	505			278, 008	109, 589, 269

收集结果：930, 063, 083, 184, 505, 278, 008, 109, 589, 269

第 2 趟——按十位分配与收集：

桶	0	1	2	3	4	5	6	7	8	9
元素	505, 008, 109			930			063, 269	278	083, 184, 589

收集结果：505, 008, 109, 930, 063, 269, 278, 083, 184, 589

此时序列已按后两位（十位 + 个位）有序：$05<08<09<30<63<69<78<83<84<89$ ✓

第 3 趟——按百位分配与收集：

桶	0	1	2	3	4	5	6	7	8	9
元素	008, 063, 083	109, 184	269, 278			505, 589				930

收集结果：008, 063, 083, 109, 184, 269, 278, 505, 589, 930 —— 排序完成。

关键观察：第 3 趟的 0 号桶里是 008, 063, 083——它们百位都是 0，能排对完全是因为它们进桶时就已经按后两位有序了，而队列的先进先出把这个次序原样保留了下来。

考点速记

三条结论：

1. 稳定性是它的正确性前提，不是附赠的好性质。
2. 第 $k$ 趟后只在"低 $k$ 位"上有序，完整关键字可能仍很乱；一趟到位 0 个。
3. 比较次数与移动次数都与初始序列无关；时间 $O(d(n+r))$，只有 $d$、$r$ 小而 $n$ 大时才真的线性。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 求第 $k$ 趟分配收集后的序列：老实按位分桶，桶内保持进入次序。四个选项的差别往往就在某两个同桶元素的先后上。
• 求某元素在某趟后的前后邻居：只算该趟依据的那一位，找同桶相邻元素，不必把整个序列排完。
• 移动次数与初始排列次序无关的是哪个：四个候选（直接插入、冒泡、基数、快速）里只有基数排序。⚠️ 别选简单选择排序——它是比较次数无关、移动次数仍随输入变。
• 多关键字排序选哪个算法：要求"先按 $C_1$ 升序、$C_1$ 相同再按总分升序"时答基数排序。做法是先按次关键字（总分）稳定排、再按主关键字（$C_1$）稳定排，次序不能反。

易错：中间状态只在末 $k$ 位有序。 拿完整关键字去核对会觉得"这明明没排好"，从而否掉正确选项。

易错：多关键字排序要先排次关键字。 反过来做，第二趟会把第一趟的结果打乱。

易错：移动次数无关的是基数排序，不是简单选择排序。 后者只有比较次数与输入无关。

教材出处

• 多关键字排序与扑克牌的例子、最高位优先法与最低位优先法（"这是一种'分配'与'收集'交替进行的方法"）：严蔚敏《数据结构（C 语言版）》（第 2 版），p256
• 链式基数排序的思想、$K$ 由 $d$ 个关键字复合而成、"基"指的是 $r_d$ 的取值范围（数字为 10、字母为 26）、三趟分配与收集的完整过程（图 8.15）：同书 p257
• 算法描述（算法 8.12 的 Distribute / Collect / RadixSort，采用静态链表）：同书 p259
• 时间复杂度："每一趟分配的时间复杂度为 $O(n)$，每一趟收集的时间复杂度为 $O(r_d)$，整个排序需进行 $d$ 趟分配和收集，所以时间复杂度为 $O(d(n+r_d))$"；空间复杂度："所需辅助空间为 $2r_d$ 个队列指针，另外由于需用链表做存储结构，则……还增加了 $n$ 个指针域的空间，所以空间复杂度为 $O(n+r_d)$"：同书 p259
• 算法特点："是稳定排序"；"可用于链式结构，也可用于顺序结构"；"时间复杂度可以突破基于关键字比较一类方法的下界 $O(n{\log }_{2}n)$，达到 $O(n)$"；"基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围"：同书 p260
• "基数排序最适用于 $n$ 值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的'最高位关键字'均不同，则亦可先按'最高位关键字'不同将序列分成若干'小'的子序列，而后进行直接插入排序"；"当关键字的取值范围为无穷集合时，则无法使用基数排序"：同书 p268

相关知识

排序的基本概念（稳定性的定义与下界的适用边界）｜ 计数排序（单趟分配-收集的顺序存储实现，不在大纲内）｜ 排序算法对比｜ 队列（"桶"的本体就是队列，先进先出正是稳定性的来源）｜ 直接插入排序（MSD 分堆后各子序列常改用它收尾）｜ 由中间状态反推排序算法

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（4题）

2026Q102分2021Q102分2015Q92分2013Q112分