计数排序动画演示
不比较大小，先数每个值有几个，再按前缀和回填位置。
键盘：← → 单步 ·空格 播放/暂停 · R 重置 ·Home/End 到两端
计数排序整趟都不比大小。它先数一遍：每个取值出现几次，得到一张直方图；再做前缀和：把「v 有几个」变成「值 ≤ v 的一共有几个」，这一步才是排序；最后倒着扫原数组，按前缀和给出的上界把每个元素放到该待的格子里，放完一个就把那个上界减一。
这一页给你三段：输入序列、计数条、输出序列。计数条下面写的数字是取值本身，不是下标。复杂度是 O(n + k)，k 是值域宽度，所以它只在取值范围跟元素个数差不多时划算；范围一大就得换基数排序或者桶。它还是稳定的——倒着扫加「取上界减一」让原数组里靠前的同值元素仍然落在前面。
计数排序演示怎么用
- 三段对照：上边那排是输入，中间是计数表（条下面写的数字是取值本身），下边那排是正在填出来的输出；回填时哪格亮起就是它落定了。
- 认三色：输入上的黄色是这一轮正在处理的元素，绿色表示它已经被数过或已经搬走；计数条上的黄色是刚被改过的那一格。
- 读计数：计数条分三档累加：计数、前缀和、回填，各自正好是 n、格子数减一、n，跑完可以拿来验算。
- 自定义：自定义那栏写一串整数最能体现它的脾气，比如 3 5 3 9 5 3；塞进很大的数会看到它换成只列出现过的取值。
常见问题
为什么回填要倒着扫原数组？
前缀和给的是「值 ≤ v」的上界，同值的几个元素要从上界往下依次占格子。倒着扫时先碰到后面那个元素，把它放到更靠后的格子，前面那个随后落在它左边，相对次序就保住了。顺着扫会把这层次序颠倒。
值域一大它就废了吗？
是的，O(n + k) 里的 k 一大，光开格子就比排序本身贵。常见出路有两条：基数排序按位把值切成几轮，每轮的值域只有 10 或 16，套用它；桶排序则先粗分区间，桶内部改用插入或快排。
它算不算比较排序，能不能被 O(n log n) 下界拦住？
不算比较排序，那个下界管不到它。它把「取值范围有限」这个信息当成前提来用，代价是 O(k) 的额外空间和只对整数（或可离散化的取值）适用，本质是拿空间和一个先验条件换时间。