基数排序（Radix Sort）

算法原理

基数排序（Radix Sort）也不比较元素——它按位摆弄顺序。LSD（最低位优先）版本只有一套动作，重复若干轮：分配——按当前数位把每张卡扔进对应的桶（个位是 3 就进桶 3）；收集——按桶序 0 → 9 依次把桶里的卡收回数组。只要桶是先入先出的队列，每轮收集完，数组就按"当前位有序"，且同位的卡片保持上一轮定下的相对次序。个位轮排完再跑十位轮，十位轮收完，整个序列就有序了——因为十位相同时，次序由个位轮已经定好。

本动画在 8 个元素 [38, 17, 52, 9, 41, 25, 60, 13] 上演示完整两轮：轮① 看个位（8 张卡逐张入桶，桶 0–9 里落位 60/41/52/13/25/17/38/9，收回来数组变成 [60,41,52,13,25,17,38,9]）与轮② 看十位（再分配再收集，得到 [9,13,17,25,38,41,52,60]）。全程一次比较都没有——顺序是"分装 + 按桶序收回"摆出来的，不是比出来的。

稳定性在轮② 是承重墙：13 和 17 十位相同、同进桶 1——13 个位轮先收完所以先入桶、叠在上层，出桶时 13 先 17 后，轮① 定下的次序原样带进终态。桶若改成后进先出，17 会翻到 13 前面，排序直接出错。

节拍（动画严格按此演示）：

1. 宣告：本轮活跃数位（个位/十位）在整行卡片上点亮青色；
2. 分配：按行序左→右逐卡起飞，落进 桶[当前位]——先入在上、后入在下，原槽位留空洞不挤动（一拍一卡）；
3. 收集：按桶序 0→9，桶内自上而下逐卡飞回数组行左起第一个空槽（一拍一卡）；头卡离桶后次卡上移补位；空桶静默跳过不占拍；
4. 两轮收完——整行转绿，有序。

动画怎么看

• 青色数字：当前轮活跃数位——轮① 每张卡的个位亮、轮② 十位亮；卡片上哪个数字发光，这一轮就按谁入桶；
• 数组行空洞：分配取走的卡留下虚框槽位，槽位永久不挤动；收集按槽 0→7 游标从左到右回填；
• 桶内叠放次序：卡自上而下叠放，上层先出——"先入先出"不是注释，是看得见的层序；13 叠在桶 1 上层、17 在下层，就是终态 13 前 17 后的全部理由；
• 暗桶：没卡可分的桶（轮① 的 4/6、轮② 的 7/8/9）整桶降暗——空桶不参与收集，一拍不占；
• 单卡 9：没有十位，按 0 入桶 0——"缺位补 0"的诚实语义；
• 绿行 + 大✓：终幕整行转绿并从左到右逐卡脉冲——升序可读，两轮收工。

复杂度分析

C++ 参考代码

#include <iostream>
#include <vector>
using namespace std;

// 基数排序（LSD 分配-收集版）：十进制，桶即 FIFO 队列
void radixSort(vector<int>& a) {
    vector<vector<int>> buckets(10);
    for (int digit = 1; digit <= 10; digit *= 10) {   // 逐位：个位 → 十位 → …
        for (int x : a) buckets[x / digit % 10].push_back(x);  // 1) 分配：按当前位入桶

        int i = 0;
        for (auto& b : buckets)                       // 2) 收集：桶序 0..9
            for (int x : b) a[i++] = x;               //    队列先入先出 ⇒ 稳定

        for (auto& b : buckets) b.clear();            //    桶清空，进入下一位
    }
}

int main() {
    vector<int> a = {38, 17, 52, 9, 41, 25, 60, 13};
    radixSort(a);
    for (int x : a) cout << x << ' ';  // 输出：9 13 17 25 38 41 52 60
    cout << endl;
    return 0;
}

什么时候用基数排序

元素是定长小位数（整数、定长字符串、日期拆位）且位数 d 小时，基数排序用 O(d(n + k)) 的时间与零比较跑赢任何基于比较的 O(n log n)——n 越大优势越明显，因为比较排序的下界 Ω(n log n) 对它不适用。它对稳定性有硬依赖：每一轮都必须保序，否则高位轮会把低位轮排好的次序搅乱——这也是它常和计数排序搭档的原因（教科书里"按位稳定排序"的内核就是计数排序；本动画为了看得见顺序如何被保住，用了桶即队列的分配-收集版，二者逐位等价）。反过来，浮点数、位数悬殊的变长数据、或内存紧张的场景都不适合它：d 要按最长元素算，k 只桶加上桶内容的开销也不小。写法上最易错的是取位公式 x / digit % 10 的边界与"桶必须先入先出"——本动画的青色数位与桶内层序正是这两处的可视化。