Radix Sort

基本思想

基数排序是一种分配类排序。它不靠两个完整关键字之间的比较来排序，而是把关键字拆成若干个“位”或“组”，再按这些位反复进行分配和收集。

若长度为 $n$ 的线性表中，每个结点 $a_j$ 的关键字可写成一个 $d$ 元组：

$$
(k_j^{d-1}, k_j^{d-2}, \dots, k_j^1, k_j^0)
$$

其中：

$k_j^{d-1}$ 是最高位关键字，也叫最主位关键字。
$k_j^0$ 是最低位关键字，也叫最次位关键字。
每一位关键字的取值范围为 $0 \le k_j^i \le r-1$。
$r$ 称为基数。十进制数按每一位排序时，$r=10$。

基数排序不是基于比较的排序算法

它的主要操作是按当前关键字位把元素放入对应队列，再按队列顺序收集。

## 多关键字排序

一个关键字能拆成多组时，排序本质上就是多关键字排序。

例如三位十进制数 985 可以看成：

$$
(9,8,5)
$$

其中百位权重最高，十位次之，个位最低。若按数值递减排序，应先比较百位；百位相同再比较十位；十位仍相同再比较个位。

1000

LSD：最低位优先

LSD，Least Significant Digit first，最低位优先。

LSD 的处理顺序是：

$$
k^0,\ k^1,\ \dots,\ k^{d-1}
$$

也就是先处理最低位，再处理更高位。以三位十进制数为例，顺序是：

1	个位 -> 十位 -> 百位

LSD 能正确排序的关键是：每一趟分配与收集必须稳定。这样较低位已经形成的顺序，才能在处理较高位时被保留下来。

MSD：最高位优先

MSD，Most Significant Digit first，最高位优先。

MSD 的处理顺序是：

$$
k^{d-1},\ k^{d-2},\ \dots,\ k^0
$$

也就是先处理最高位，再处理更低位。以三位十进制数为例，顺序是：

1	百位 -> 十位 -> 个位

MSD 的直觉更接近普通字典序：先按主关键字分组，再在同一组内继续按次关键字分组。若最高位已经不同，低位不会影响这两个元素的相对顺序。

方法	处理方向	核心理解	常见特点
LSD	从最低位到最高位	先排次关键字，再用稳定排序主关键字保留低位顺序	适合位数固定的整数、编号、日期等
MSD	从最高位到最低位	先按主关键字分组，再在组内继续处理次关键字	更接近字典序和分治思想

从题干读出稳定性要求

多关键字排序题常把稳定性要求藏在一句话里：

对 $k_i$ 排序后，$k_i$ 相同的元素还要满足 $k_{i+1}$ 大的在后面。

隐含以下信息：

$k_i$ 是当前更高优先级关键字。
$k_{i+1}$ 是较低优先级关键字。
当 $k_i$ 相同时，元素之间的相对次序要继续由 $k_{i+1}$ 决定。
因此，若先按 $k_{i+1}$ 排好，再按 $k_i$ 排，后一趟按 $k_i$ 排序必须是稳定排序，否则 $k_{i+1}$ 的顺序会被破坏。

题干要求	应读出的操作
先看 $k_i$，$k_i$ 相同再看 $k_{i+1}$	$k_i$ 是主关键字，$k_{i+1}$ 是次关键字
$k_i$ 相同者，$k_{i+1}$ 大的在后面	在同一 $k_i$ 组内，$k_{i+1}$ 要递增
对每一项关键字排一次而不分组	采用LSD

例如要按二元关键字 $(k_1,k_2)$ 排序，要求：

$k_1$ 小的在前。
$k_1$ 相同者，$k_2$ 大的在后。

则等价于按 $(k_1 \uparrow,\ k_2 \uparrow)$ 排序。使用 LSD 思路时，应先对 $k_2$ 做递增排序，再对 $k_1$ 做递增稳定排序。第二趟稳定，才能保证 $k_1$ 相同的元素仍保持第一趟建立的 $k_2$ 递增顺序。

Tip

只要题目要求“某个高优先级关键字相同者，还要保持某个低优先级关键字的顺序”，就要想到稳定排序。LSD 是从低优先级排到高优先级，每一趟都必须稳定。

## 分配与收集

基数排序通常设置 $r$ 个队列：

$$
Q_0,Q_1,\dots,Q_{r-1}
$$

每一趟处理一个关键字位。

分配：顺序扫描所有元素。若当前元素在当前关键字位上的值为 $x$，就把它插入 $Q_x$ 的队尾。

收集：按目标排序方向，把各队列中的元素依次出队并连接成新的序列。

目标顺序	队列初始化	收集顺序
递增	$Q_0,Q_1,\dots,Q_{r-1}$	从 $Q_0$ 到 $Q_{r-1}$
递减	$Q_{r-1},Q_{r-2},\dots,Q_0$	从 $Q_{r-1}$ 到 $Q_0$

队列的“队尾入队、队头出队”保证了同一队列内部的先后顺序不变。

LSD 递减排序过程

对三位十进制数：

1	520 211 438 888 007 111 985 666 996 233 168

若要求得到递减序列，使用 LSD 时按个位、十位、百位依次处理，每趟收集都按 $Q_9,Q_8,\dots,Q_0$ 的顺序进行。

三趟结果为：

趟数	当前关键字位	本趟结束后的序列
初始	-	`520 211 438 888 007 111 985 666 996 233 168`
第 1 趟	个位	`438 888 168 007 666 996 985 233 211 111 520`
第 2 趟	十位	`996 888 985 168 666 438 233 520 211 111 007`
第 3 趟	百位	`996 985 888 666 520 438 233 211 168 111 007`

每一趟结束后，已经处理过的低位顺序不会丢失：

第 1 趟后，序列按个位递减。
第 2 趟后，序列按十位递减；十位相同者按个位递减。
第 3 趟后，序列按百位递减；百位相同者按十位递减；十位仍相同者按个位递减。

稳定性

基数排序是稳定排序。

稳定性来自两点：

分配时，相同关键字位的元素进入同一个队列，并且插入队尾。
收集时，从队头依次出队，同一队列内部的先后顺序不变。

例如两个元素当前关键字位都为 2，前一个元素先被扫描，就先进入 $Q_2$；收集时它也先出队。它们在当前位相等时不会交换相对位置。

LSD 尤其依赖稳定性。若某一趟不稳定，低位已经建立的顺序就可能在高位处理时被破坏。

效率分析

设：

$n$：元素个数。
$d$：关键字被拆成的位数或组数。
$r$：每一位关键字的取值范围大小，也就是基数。

一趟基数排序包含一次分配和一次收集：

操作	时间
分配	$O(n)$
收集	$O(r)$

总共处理 $d$ 个关键字位，因此时间复杂度为：

$$
O(d(n+r))
$$

若用链式队列表示桶，只需要维护 $r$ 个队列的队头、队尾指针，辅助空间为：

$$
O(r)
$$

若用数组式桶临时存放元素，辅助空间通常会写成 $O(n+r)$。考研教材讨论链式队列实现时，更常见的结论是 $O(r)$。

适用条件

基数排序适合以下情况：

关键字能方便地拆成 $d$ 组。
$d$ 较小。
每组关键字取值范围 $r$ 较小。
元素个数 $n$ 较大。

典型适用对象：

固定位数整数。
学号、编号、身份证号等结构化数字串。
日期类关键字，如年、月、日。

不适合的情况：

元素很少时，为基数排序准备队列不划算。
关键字难以拆分成少数几组。
每组关键字取值范围很大，例如中文姓名中的单字可能有大量取值。
位数很多而 $n$ 不大，例如只给少量身份证号排序。

日期排序例子

若按年龄递减排列学生，年龄越大，出生日期越早。生日可拆成：

$$
(\text{年},\text{月},\text{日})
$$

按生日递增，就能得到年龄递减。

使用 LSD 思路时：

先按“日”递增分配、收集。
再按“月”递增分配、收集。
最后按“年”递增分配、收集。

如果有 $10000$ 名学生，生日只有年、月、日三组关键字，基数排序的代价近似为 $O(3n)$ 量级；相比 $O(n^2)$ 排序或 $O(n\log_2 n)$ 比较排序，优势会很明显。

小结

项目	结论
类型	分配类排序，非比较排序
核心操作	分配、收集
关键参数	$n$ 个元素，$d$ 个关键字位，基数 $r$
LSD	从最低位到最高位，依赖稳定性保留低位顺序
MSD	从最高位到最低位，先按主关键字分组
递增收集	$Q_0,Q_1,\dots,Q_{r-1}$
递减收集	$Q_{r-1},Q_{r-2},\dots,Q_0$
时间复杂度	$O(d(n+r))$
空间复杂度	链式队列实现常记为 $O(r)$
稳定性	稳定
适用场景	$d$ 小、$r$ 小、$n$ 大，关键字易拆分