计数排序（Counting Sort）

算法原理

计数排序（Counting Sort）压根不比较元素——它直接问"每个值出现了几次"。设值域为 0..k：开 k 个计数桶，扫一遍输入，值 v 出现一次就往桶 v 里投一颗珠子；然后按桶序 0 → k-1 输出——桶 c[0]=2，就向输出连续写两个 0；桶里是几就写几遍。写完的序列天然有序，因为输出的次序就是值的大小次序——位置不是比出来的，是数出来的。

本动画在 10 个元素、值域 0..9 上演示完整两幕：计数（逐卡投珠，桶内数字涨到 [2,0,3,0,2,1,0,1,0,1]）与倾倒（按桶序把卡片逐张直飞输出行的连续空槽，桶每落一张卡数字减一，减到 0 即"倒空"退居背景）。同值卡片带小写角标（0ᵃ/0ᵇ、2ᵃ/2ᵇ/2ᶜ、4ᵃ/4ᵇ），同值卡按输入顺序依次飞出——输出后角标次序不变，这就是计数排序的稳定性，肉眼可见。

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

1. 计数：从左到右扫输入，值 v 对应桶 v 计数 +1；输入行不动，卡片等倾倒幕才起飞；
2. 倾倒：按桶序 0→9，当前桶按输入序逐张出卡，直飞输出行的下一个连续空槽（一拍一卡）；
3. 空桶（计数 0）无卡可倒，直接跳过；桶倒空即降透明退场；
4. 输出行填满——有序，且同值保持原相对次序。

动画怎么看

• 橙色卡：当前活动卡（计数拍正在读的卡 / 倾倒拍正在飞的卡），全屏唯一；飞行途中由橙渐变绿，落定即绿；
• 金色小球：计数拍的投珠，从卡底飞落桶顶，落点即散；
• 桶内大数字：两段生命——计数幕往上涨（pop 连击就是"计数"的具象），倾倒幕逐次减一，减到 0 桶变暗；
• 金框桶：当前正在倾倒的桶，接力棒随桶序 0→9 右移；空桶 1/3/6/8 从倾倒开始就一直暗着——没货的桶不参与输出；
• 绿卡（带 ✓）：已落位的输出卡，终身不褪；落位槽从左到右一格不跳；
• 右下小字母角标：同值卡的身份（4ᵃ/4ᵇ……）——终幕按 0 组→2 组→4 组逐卡金脉冲验证：角标次序与输入一致，稳定性成立。

复杂度分析

C++ 参考代码

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

// 计数排序（稳定倾倒版）：值域 [0, k)
// 逐值输出 count[v] 个 v——同值按输入序，天然稳定
void countingSort(const vector<int>& a, int k, vector<int>& out) {
    vector<int> count(k, 0);
    for (int x : a) count[x]++;          // 1) 计数：值 v 投进桶 v

    out.clear();
    for (int v = 0; v < k; v++)          // 2) 倾倒：按桶序 0..k-1
        for (int t = 0; t < count[v]; t++)
            out.push_back(v);            //    桶里几个就连续输出几个 v
}

int main() {
    vector<int> a = {4, 2, 7, 0, 4, 9, 2, 5, 0, 2};
    vector<int> out;
    countingSort(a, 10, out);
    for (int x : out) cout << x << ' ';  // 输出：0 0 2 2 2 4 4 5 7 9
    cout << endl;
    return 0;
}

什么时候用计数排序

计数排序的适用条件写在复杂度里：值域 k 要小。元素是 0..100 万以外的稠密小整数（年龄、分数、字符、哈希桶序号）时，它用 O(n + k) 的时间与零比较把任何基于比较的 O(n log n) 甩开——n 越大优势越明显，因为比较排序的下界 Ω(n log n) 对它不适用。它最常见的身份其实是基数排序（Radix Sort）的内核：按位稳定排序用的正是计数排序，"先按个位、再按十位"逐位倒腾，稳定性在那里不是美德而是命门——这也是本动画用角标可视化稳定性的原因。反过来，值域巨大而元素稀疏（比如任意 int）时，k 一大桶数组就吃光内存，此时换桶排/基数组合或直接回到比较排序。写法上最易错的是值域边界的开闭与"倾倒按桶序、同值按输入序"——本动画的投珠拍与角标亮波正是这两处的可视化。