基数排序是一种非比较排序。它把整数拆成若干位，从低位到高位依次进行稳定排序，最终得到整个数组的有序排列。

学习基数排序，需要掌握三件事：一轮怎样按当前位排好、为什么必须保持稳定、为什么多轮之后整个数值就有序。实现中，这些问题集中体现在下面这句：

output[--count[digit]] = x;

本文面向算法竞赛学习：先手推过程，再理解计数排序的分配方法，随后证明正确性，最后给出支持标准输入输出的完整模板，并整理复杂度、适用条件和易错点。

本文实现按从小到大排序，仅适用于非负 int 整数。负数不能直接使用这个版本，因为取出的数字可能成为负下标。

0. 基数排序与计数排序的关系

普通计数排序直接统计每个数值。如果数值范围是 0~U，就需要大小约为 U + 1 的计数数组，时间和额外空间都与这个值域有关。

十进制基数排序每轮只统计一位，该位的取值只有 0~9，所以只需十个计数位置。一个很大的整数会被拆成多轮处理，无需按它的完整数值开计数数组。

本文使用 LSD（Least Significant Digit，最低位优先）方法。每轮的子过程就是一次稳定的计数排序。另有最高位优先的 MSD 方法，组织方式不同，本文只讨论 LSD。

1. 先排个位，再排十位

这里使用 LSD 基数排序，也就是从最低位开始，逐步处理更高位。

例如有这样一组数：

初始：170  45  75  90  802  24  2  66

每轮只观察一个位置上的数字，并保持当前位相同的元素的原有顺序：

按个位：170  90  802  2  24  45  75  66
按十位：802  2   24  45  66  170 75  90
按百位：2    24  45  66  75  90  170 802

位数不足时，对应的高位按 0 处理。例如 2 的十位和百位都视为 0。

注意，第一轮只保证个位有序，并不保证整个数值有序。只有处理完最高位，整个数组才完成排序。

2. 如何取出当前位？

我们用 exp 表示当前处理的位置：

exp = 1     个位
exp = 10    十位
exp = 100   百位

取位公式是：

int digit = (x / exp) % 10;

以 172 为例：

(172 / 1) % 10    // 2，个位
(172 / 10) % 10   // 7，十位
(172 / 100) % 10  // 1，百位

整数除法先去掉右边不需要的位，% 10 再取出最后一位。

3. count：从出现次数到位置边界

每轮先统计当前位上 0~9 各出现了几次。

std::size_t count[10] = {};

for (int x : a) {
    int digit = (x / exp) % 10;
    ++count[digit];
}

count[5] == 2 表示当前位为 5 的元素有两个。这里使用 std::size_t，它也是 vector 的大小和下标使用的类型。

继续使用前面的数组，按个位统计，结果如下：

只有次数，还不能直接确定每个元素放在哪里。接下来求前缀和：

for (int i = 1; i < 10; ++i) {
    count[i] += count[i - 1];
}

转换后变成：

此时，count[d] 的含义变为：当前位小于或等于 d 的元素总共有多少个。

例如 count[5] == 7，说明个位不大于 5 的元素共七个。排好后它们占据下标 0~6，所以个位为 5 的分组结束于下标 6。

每个分组因此有了自己的连续区间：

更一般地，在填入元素之前，数字 d 的分组区间是 [count[d - 1], count[d])；当 d == 0 时，左边界是 0。这里右边界不包含在区间内。

这就是当前位有序的原因：小数字的分组在前，大数字的分组在后，区间互不重叠。

4. output 为什么只需要一维？

output 保存的是本轮排序后的完整数组，每个位置存一个完整的整数：

std::vector<int> output(a.size());

假如 a 有八个元素，这行代码就创建八个 int 位置，初始值都是 0。它们与原数组 a 的存储空间独立。

个位为 5 的两个元素，可以连续放在：

output[5] = 45;
output[6] = 75;

同一组占据多个相邻位置，因此不需要让一个格子存放整组元素，也不需要二维数组。

本轮全部填完后：

a = output;

这会把本轮结果复制回 a，供下一轮继续排序。暂存数组还使我们能够在读取原数组时，避免覆盖尚未处理的元素。

后面的竞赛模板将 output 创建在循环外，并用 a.swap(output) 交换两个向量的存储。交换后，a 持有本轮结果，output 持有旧数据；下一轮会覆盖 output 的全部位置，因此不必将它清零。默认分配器下，这种交换不逐个复制元素，也避免了每轮重新创建暂存数组。

5. 拆解 output[--count[digit]]

核心语句是：

output[--count[digit]] = x;

它等价于：

--count[digit];
output[count[digit]] = x;

以个位为 5 的分组为例，前缀和计算完成后，count[5] == 7，该组占据下标 5、6。

第一次放入该组的元素时：

--count[5];           // 从 7 变成 6
output[6] = 75;

第二次放入时：

--count[5];           // 从 6 变成 5
output[5] = 45;

每放一个元素，该组的可用位置就向左移动一格。需要留意：一旦开始填入，count 就不再保存原始的前缀和，而是在记录各组尚未填入部分的右边界。

6. 为什么从后往前遍历？

因为我们填入同一分组时，也是从右向左填的。倒序读取可以保留当前位相同的元素的原有顺序，这种性质叫作稳定性。

原数组中，45 在 75 前面，它们的个位都是 5：

原来顺序：45 → 75

倒序读取，先遇到 75，将它放到组内右侧；再遇到 45，将它放到左侧：

结果顺序：45 → 75

用完整数组追踪一次填入过程，会更清楚：

最终得到：

170  90  802  2  24  45  75  66

这里的倒序遍历是与“从分组右边界向左填入”配合的。如果改成记录每组左边界并向右填入，也可以设计正序读取的稳定版本。

7. 稳定性如何让整个数字有序？

假设按个位排完后，有：

21  12

它们的个位顺序是 1、2。接下来按十位排序，得到：

12  21

十位不同，直接由十位决定先后。对于十位相同的元素，例如 21、23，稳定排序则会保留上一轮已经建立的个位顺序。

所以每完成一轮，就多保证一位：

• 按个位排完，最低一位有序。
• 按十位稳定排序后，最低两位组成的数值有序。
• 按百位稳定排序后，最低三位组成的数值有序。

当最高位也处理完，所有有效位都参与了排序，整个数值自然有序。

用循环不变式证明正确性

设已经处理了最低 k 位，我们维护以下性质：数组按每个数的最低 k 位组成的数值非递减排列。这个数值在数学上可以写成 x mod 10^k，不要求代码实际计算 10^k。

初始情况： 第一轮按个位排序后，性质对 k = 1 成立。

递推情况： 假设最低 k 位已经有序，下一轮按第 k + 1 位稳定排序。对于任意两个元素，如果新处理的这一位不同，就由这一位决定先后；如果相同，稳定性保留它们之前的顺序，而之前的顺序已经保证最低 k 位有序。因此，最低 k + 1 位组成的数值有序。

终止情况： 处理完最大值的最高位后，所有元素的有效位都已覆盖，最低这些位组成的数值就是元素本身，所以数组整体有序。全零数组无需进入循环，本身已经有序。

如果破坏稳定性，会发生什么？

考虑 12、11。按个位正确排完后得到 11、12，接下来它们的十位都是 1。如果第二轮把同组元素的顺序反转，结果就变成 12、11，整个数组排序失败。

所以“每轮当前位有序”还不够；当前位相同时，必须保留低位已经排好的顺序。

8. 算法竞赛 C++ 模板

下面的版本使用 C++11 或更新标准。输入第一行为非负整数 n，随后输入 n 个非负 int 整数，输出升序结果。模板假设输入符合题目规定的数据范围。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

// 将非负 int 整数按从小到大排序
void radixSort(std::vector<int>& a) {
    if (a.empty()) return;

    int ma = *std::max_element(a.begin(), a.end());
    std::vector<int> output(a.size()); // 只分配一次，后续轮次复用

    // exp = 1 表示个位，10 表示十位，依此类推
    for (int exp = 1; ma / exp > 0; ) {
        std::size_t count[10] = {};

        // 1. 统计当前位上 0~9 各出现几次
        for (int x : a) {
            int digit = (x / exp) % 10;
            ++count[digit];
        }

        // 2. 前缀和：得到每组的右边界（不包含）
        for (int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }

        // 3. 倒序读取，从每组右侧向左填入，保持稳定性
        for (std::size_t i = a.size(); i > 0; --i) {
            int x = a[i - 1];
            int digit = (x / exp) % 10;
            output[--count[digit]] = x;
        }

        // 4. 交换存储，让 a 持有本轮排序结果
        a.swap(output);

        // 已处理最高位则结束，避免继续乘 10 导致 int 溢出
        if (exp > ma / 10) break;
        exp *= 10;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n) || n < 0) return 0;

    std::vector<int> a(n);
    for (int& x : a) {
        std::cin >> x;
    }

    radixSort(a);

    for (int i = 0; i < n; ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << a[i];
    }
    std::cout << '\n';

    return 0;
}

输入示例：

8
170 45 75 90 802 24 2 66

输出示例：

2 24 45 66 75 90 170 802

代码中的倒序循环从 a.size() 开始，每次读取 a[i - 1]，实际访问的下标依次是 n-1、n-2、…、0。这样可以避免无符号下标减到零以下的问题。

另一个细节是 exp 的更新。直接把 exp *= 10 写进循环更新部分，在最大值很大时可能发生有符号整数溢出。这里先判断 exp > ma / 10，处理完最高位后立即退出；只有下一次乘法结果不超过 ma 时才执行乘法。

空数组会直接返回；如果所有元素都是 0，循环无需执行，数组本来就有序。

9. 时间与空间复杂度

设元素数量为 n，最大值的十进制位数为 d。

寻找最大值需要 O(n)。每一轮统计和填入都需要遍历数组，计算前缀和则只需要处理十个计数；模板中的交换为常数时间。因此总时间复杂度为 O(n + d × (n + 10))，对非空数组、十进制表示通常写为 O(dn)。分析时可以约定 0 的位数为一位，即使代码会跳过全零数组的排序轮次。

额外空间主要是长度为 n 的 output 和长度为 10 的 count，空间复杂度为 O(n + 10)，即 O(n)。

更一般地，如果基数为 B，需要处理 d 位，则时间为 O(n + d(n + B))，额外空间为 O(n + B)。对于最大值 M > 0，位数为 floor(log_B M) + 1。

在常见的 32 位 int 竞赛环境中，非负整数至多有十位十进制数字，所以轮数有固定上限。但不要脱离数据类型和位数限制，无条件将基数排序写成 O(n)。

比较排序的 Ω(n log n) 下界针对仅通过比较获得顺序信息的模型。基数排序利用整数的位表示，不属于这个模型，因此没有违反这一下界。

10. 比赛中怎样判断是否适用？

基数排序适合具有明确位表示、位数受控的排序键。本模板还要求数值非负，并且可以接受 O(n) 的额外存储空间。

普通排序题并不一定需要基数排序。它是否比 std::sort 快，取决于数据规模、轮数、取位运算和内存访问等因素，需要结合题目限制与实际测量。学习时应先能说明算法为什么正确，再考虑常数优化。

扩展：一轮不一定只处理一个十进制位

“基数”就是每位可能取值的数量，十进制中是 10。对 uint32_t 无符号整数，也可以取 B = 256，每轮处理八个二进制位：

// x 为 uint32_t；shift 依次为 0、8、16、24
unsigned digit = (x >> shift) & 255u;

这样完整处理 32 位需要四轮，每轮使用 256 个计数位置。增加基数会减少轮数，但同时增加计数数组及每轮清零、前缀和的开销。

这是理解十进制版本后的进阶方向。若要迁移实现，需要同步修改数据类型、计数数组大小、取位方式和循环控制，不能只替换取位表达式。

11. 常见错误与边界情况

1. 没有清空 count。 每轮都要从零开始统计；前一轮的 count 已经被填入操作修改。
2. 配合 --count[digit] 却正序读取。 这会反转同组元素的顺序，破坏稳定性。
3. 把后置递减写进去。 output[count[digit]--] 会先使用分组右边界；这个边界不属于该组，可能越界。
4. 写成 output[digit] = x。 同一位的多个元素会覆盖同一个格子。应通过 count 分配不同位置。
5. 边读边直接覆盖 a。 可能改掉尚未读取的元素，应先写入独立的暂存数组。
6. 直接使用 exp *= 10 而不检查。 最大值接近类型上限时可能溢出。模板在乘法之前判断是否结束。
7. 空数组仍解引用 max_element。 应在求最大值之前返回。
8. 将负数直接交给本模板。 当前位可能为负，导致下标非法；有符号整数需要另行设计排序键或处理方案。尤其不能随意对最小负数取绝对值，它的正值可能超出原类型范围。
9. 用无符号下标写 i >= 0 的倒序循环。 无符号数不会小于零；模板使用 i > 0 并访问 i - 1。

下面这些输入适合检查模板边界：

自己练习实现时，可以复制同一份随机数组：一份使用基数排序，另一份使用 std::sort，比较两个结果是否完全一致。随机对拍之外仍要单独检查上面的边界。

12. 学完后做三个自测

自测一：手推一轮。 对 53、21、43、12、31 按个位稳定排序，结果是什么？

答案是 21、31、12、53、43。个位为 1 的 21、31 保持原顺序，个位为 3 的 53、43 也保持原顺序。

自测二：解释一行代码。 为什么 output[--count[digit]] = x 先减再写？

因为前缀和给出的是该组右边界的后一格，先减一才是当前可用位置。放入后边界随之左移，为同组的下一个元素留出不同位置。

自测三：迁移到双关键字。 如果希望先按成绩升序，再按学号升序，怎样用稳定排序实现？

先按次要关键字“学号”稳定排序，再按主要关键字“成绩”稳定排序。第二轮中，成绩相同的记录保留学号的升序。这与基数排序先低位、后高位的思路相同。

能够独立手推分组边界、解释稳定性，并写出循环不变式后，再尝试不看模板实现一次。检查代码时，沿着“统计次数 → 前缀和 → 稳定填入 → 交换结果 → 处理下一位”逐步核对即可。