基数排序（Radix Sort）是一种非比较排序算法，通过逐位排序来实现整体排序。它将整数按位拆分，从某一位开始，对该位做一次稳定排序（通常是计数排序），重复多次后整体有序。
基数排序有两种方式：
LSD 从个位开始，每一轮对当前位做一次稳定的计数排序。经过 d 轮（d 为最大位数）后，整体有序。
为什么必须是稳定排序？ 因为低位排序的结果要在高位排序中保持。如果高位相同，低位的顺序必须保留。
1#include <bits/stdc++.h>
2using namespace std;
3
4// 获取数字 x 在第 exp 位上的值（exp = 1, 10, 100, ...）
5int getDigit(int x, int exp) {
6 return (x / exp) % 10;
7}
8
9// 对数组按第 exp 位进行计数排序（稳定排序）
10void countingSortByDigit(int a[], int n, int exp) {
11 int output[100005];
12 int count[10] = {0};
13
14 // 统计每个数字出现的次数
15 for (int i = 0; i < n; i++)
16 count[getDigit(a[i], exp)]++;
17
18 // 计算前缀和，确定每个数字的最终位置
19 for (int i = 1; i < 10; i++)
20 count[i] += count[i - 1];
21
22 // 从后往前遍历，保证稳定性
23 for (int i = n - 1; i >= 0; i--) {
24 int d = getDigit(a[i], exp);
25 output[count[d] - 1] = a[i];
26 count[d]--;
27 }
28
29 // 复制回原数组
30 for (int i = 0; i < n; i++)
31 a[i] = output[i];
32}
33
34void radixSort(int a[], int n) {
35 // 找到最大值，确定最大位数
36 int maxVal = *max_element(a, a + n);
37
38 // 从个位到最高位，逐位排序
39 for (int exp = 1; maxVal / exp > 0; exp *= 10) {
40 countingSortByDigit(a, n, exp);
41 }
42}
43
44int main() {
45 int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
46 int n = 8;
47
48 radixSort(a, n);
49
50 for (int i = 0; i < n; i++)
51 printf("%d ", a[i]);
52 // 输出: 2 24 45 66 75 90 170 802
53 return 0;
54}以 [170, 45, 75, 90, 802, 24, 2, 66] 为例：
第一轮：按个位排序
| 元素 | 个位 |
|---|---|
| 170 | 0 |
| 90 | 0 |
| 802 | 2 |
| 2 | 2 |
| 24 | 4 |
| 45 | 5 |
| 75 | 5 |
| 66 | 6 |
排序后：[170, 90, 802, 2, 24, 45, 75, 66]
第二轮：按十位排序
| 元素 | 十位 |
|---|---|
| 802 | 0 |
| 2 | 0 |
| 24 | 2 |
| 45 | 4 |
| 66 | 6 |
| 170 | 7 |
| 75 | 7 |
| 90 | 9 |
排序后：[802, 2, 24, 45, 66, 170, 75, 90]
第三轮：按百位排序
| 元素 | 百位 |
|---|---|
| 2 | 0 |
| 24 | 0 |
| 45 | 0 |
| 66 | 0 |
| 75 | 0 |
| 90 | 0 |
| 170 | 1 |
| 802 | 8 |
排序后：[2, 24, 45, 66, 75, 90, 170, 802] -- 排序完成！
MSD 从最高位开始排序，然后递归地对每个桶内的元素按下一位排序。
1#include <bits/stdc++.h>
2using namespace std;
3
4// 获取 x 的第 pos 位（从高位数起，pos=0 为最高位）
5int getDigitMSD(int x, int pos, int maxDigits) {
6 int exp = 1;
7 for (int i = 0; i < maxDigits - 1 - pos; i++) exp *= 10;
8 return (x / exp) % 10;
9}
10
11void msdRadixSort(vector<int>& a, int pos, int maxDigits) {
12 if (a.size() <= 1 || pos >= maxDigits) return;
13
14 // 按当前位分桶
15 vector<vector<int>> buckets(10);
16 for (int x : a) {
17 int d = getDigitMSD(x, pos, maxDigits);
18 buckets[d].push_back(x);
19 }
20
21 // 递归排序每个桶
22 for (auto& bucket : buckets) {
23 msdRadixSort(bucket, pos + 1, maxDigits);
24 }
25
26 // 收集结果
27 int idx = 0;
28 for (auto& bucket : buckets) {
29 for (int x : bucket) {
30 a[idx++] = x;
31 }
32 }
33}
34
35int main() {
36 vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
37
38 int maxVal = *max_element(a.begin(), a.end());
39 int maxDigits = 0;
40 while (maxVal > 0) { maxDigits++; maxVal /= 10; }
41
42 msdRadixSort(a, 0, maxDigits);
43
44 for (int x : a) printf("%d ", x);
45 // 输出: 2 24 45 66 75 90 170 802
46 return 0;
47}| 特性 | LSD | MSD |
|---|---|---|
| 方向 | 低位 → 高位 | 高位 → 低位 |
| 实现方式 | 迭代，更简单 | 递归 |
| 需要稳定排序 | 是（关键） | 桶内递归即可 |
| 适合场景 | 整数排序 | 字符串排序、变长数据 |
| 空间复杂度 | O(n + k) | O(n + k)，递归栈额外开销 |
| 竞赛中常用 | 更常用 | 较少使用 |
使用基数排序的决策流程：
竞赛中的优化技巧：使用 2^k 进制（如 256 进制），这样取位操作可以用位运算代替除法：
1void radixSort256(int a[], int n) {
2 int output[100005];
3 for (int shift = 0; shift < 32; shift += 8) {
4 int count[256] = {0};
5 for (int i = 0; i < n; i++)
6 count[(a[i] >> shift) & 0xFF]++;
7 for (int i = 1; i < 256; i++)
8 count[i] += count[i - 1];
9 for (int i = n - 1; i >= 0; i--) {
10 int d = (a[i] >> shift) & 0xFF;
11 output[--count[d]] = a[i];
12 }
13 for (int i = 0; i < n; i++) a[i] = output[i];
14 }
15}| 特性 | 基数排序 |
|---|---|
| 时间复杂度 | O(d * (n + k))，d 为位数，k 为进制 |
| 空间复杂度 | O(n + k) |
| 稳定性 | 稳定（LSD 版本） |
| 适用条件 | 整数或等长字符串，位数不太大 |
何时选择基数排序：
基数排序在竞赛中不如 sort 常用，但在特定场景（如后缀数组、大规模整数排序）下是重要的优化手段。