docs/basic/radix-sort.md
???+ warning "提醒" 本页面要介绍的不是 计数排序．
本页面将简要介绍基数排序．
基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题．基数排序将待排序的元素拆分为 $k$ 个关键字，逐一对各个关键字排序后完成对所有元素的排序．
如果是从第 $1$ 关键字到第 $k$ 关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；
如果是从第 $k$ 关键字到第 $1$ 关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序．
下面用 $a_i$ 表示元素 $a$ 的第 $i$ 关键字．
假如元素有 $k$ 个关键字，对于两个元素 $a$ 和 $b$，默认的比较方法是：
例子：
std::pair 与 std::tuple 的默认比较方法与上述的相同．基于 k - 关键字元素的比较方法，可以想到：先比较所有元素的第 $1$ 关键字，就可以确定出各元素大致的大小关系；然后对 具有相同第 $1$ 关键字的元素，再比较它们的第 $2$ 关键字……以此类推．
由于是从第 $1$ 关键字到第 $k$ 关键字顺序进行比较，由上述思想导出的排序算法称为 MSD（Most Significant Digit first）基数排序．
将待排序的元素拆分为 $k$ 个关键字，先对第 $1$ 关键字进行稳定排序，然后对于每组 具有相同关键字的元素 再对第 $2$ 关键字进行稳定排序（递归执行）……最后对于每组 具有相同关键字的元素 再对第 $k$ 关键字进行稳定排序．
一般而言，我们默认基数排序是稳定的，所以在 MSD 基数排序中，我们也仅仅考虑借助 稳定算法（通常使用计数排序）完成内层对关键字的排序．
正确性参考上文 k - 关键字元素的比较．
下面是使用迭代式 MSD 基数排序对 unsigned int 范围内元素进行排序的 C++ 参考代码，可调整 $W$ 和 $\log_2 W$ 的值（建议将 $\log_2 W$ 设为 $2^k$ 以便位运算优化）．
??? example "参考代码"
cpp --8<-- "docs/basic/code/radix-sort/radix-sort_1.cpp:core"
下面是使用迭代式 MSD 基数排序对 空终止字节字符串 基于字典序进行排序的 C++ 参考代码：
??? example "参考代码"
cpp --8<-- "docs/basic/code/radix-sort/radix-sort_2.cpp:core"
由于两个字符串的比较很容易冲上 $O(n)$ 的线性复杂度，因此在字符串排序这件事情上，MSD 基数排序比大多数基于比较的排序算法在时间复杂度和实际用时上都更加优秀．
前置知识：桶排序
桶排序需要其它的排序算法来完成对每个桶内部元素的排序．但实际上，完全可以对每个桶继续执行桶排序，直至某一步桶的元素数量 $\le 1$．
因此 MSD 基数排序的另一种理解方式是：使用桶排序实现的桶排序．
也因此，可以提出 MSD 基数排序在时间常数上的一种优化方法：假如到某一步桶的元素数量 $\le B$（$B$ 是自己选的常数），则直接执行插入排序然后返回，降低递归次数．
MSD 基数排序从第 $1$ 关键字到第 $k$ 关键字顺序进行比较，为此需要借助递归或迭代来实现，时间常数还是较大，而且在比较自然数上还是略显不便．
而将递归的操作反过来：从第 $k$ 关键字到第 $1$ 关键字顺序进行比较，就可以得到 LSD（Least Significant Digit first）基数排序，不使用递归就可以完成的排序算法．
将待排序的元素拆分为 $k$ 个关键字，然后先对 所有元素 的第 $k$ 关键字进行稳定排序，再对 所有元素 的第 $k-1$ 关键字进行稳定排序，再对 所有元素 的第 $k-2$ 关键字进行稳定排序……最后对 所有元素 的第 $1$ 关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序．
LSD 基数排序也需要借助一种 稳定算法 完成内层对关键字的排序．同样的，通常使用计数排序来完成．
LSD 基数排序的正确性可以参考 《算法导论（第三版）》第 8.3-3 题的解法 或参考下面的解释：
回顾一下 k - 关键字元素的比较方法，
现在，将顺序反过来：
在这个过程中，对每个关键字边比较边重排元素的顺序，就得到了 LSD 基数排序．
$$ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements, where each element has }k\text{ keys.}\ 2 & \textbf{Output. } \text{Array }A\text{ will be sorted in nondecreasing order stably.} \ 3 & \textbf{Method. } \ 4 & \textbf{for }i\gets k\textbf{ down to }1\ 5 & \qquad\text{sort }A\text{ into nondecreasing order by the }i\text{-th key stably} \end{array} $$
下面是使用 LSD 基数排序实现的对 k - 关键字元素的排序．
??? example "参考代码"
cpp --8<-- "docs/basic/code/radix-sort/radix-sort_lsd.cpp:core"
实际上并非必须从后往前枚举才是稳定排序，只需对 cnt 数组进行等价于 std::exclusive_scan 的操作即可．
???+ note "例题 洛谷 P1177【模板】快速排序" 给出 $n$ 个正整数，从小到大输出．
```cpp
#include <algorithm>
#include <iostream>
#include <utility>
void radix_sort(int n, int a[]) {
int *b = new int[n]; // 临时空间
int *cnt = new int[1 << 8];
int mask = (1 << 8) - 1;
int *x = a, *y = b;
for (int i = 0; i < 32; i += 8) {
for (int j = 0; j != (1 << 8); ++j) cnt[j] = 0;
for (int j = 0; j != n; ++j) ++cnt[x[j] >> i & mask];
for (int sum = 0, j = 0; j != (1 << 8); ++j) {
// 等价于 std::exclusive_scan(cnt, cnt + (1 << 8), cnt, 0);
sum += cnt[j], cnt[j] = sum - cnt[j];
}
for (int j = 0; j != n; ++j) y[cnt[x[j] >> i & mask]++] = x[j];
std::swap(x, y);
}
delete[] cnt;
delete[] b;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
int *a = new int[n];
for (int i = 0; i < n; ++i) std::cin >> a[i];
radix_sort(n, a);
for (int i = 0; i < n; ++i) std::cout << a[i] << ' ';
delete[] a;
return 0;
}
```
如果对内层关键字的排序是稳定的，则 MSD 基数排序和 LSD 基数排序都是稳定的排序算法．
通常而言，基数排序比基于比较的排序算法（比如快速排序）要快．但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择．1
一般来说，如果每个关键字的值域都不大，就可以使用 计数排序 作为内层排序，此时的复杂度为 $O(kn+\sum\limits_{i=1}^k w_i)$，其中 $w_i$ 为第 $i$ 关键字的值域大小．如果关键字值域很大，就可以直接使用基于比较的 $O(nk\log n)$ 排序而无需使用基数排序了．
MSD 基数排序和 LSD 基数排序的空间复杂度都为 $O(k+n)$．
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms(3rd ed.). MIT Press and McGraw-Hill, 2009. ISBN 978-0-262-03384-8. "8.3 Radix sort", pp. 199. ↩