计数排序

计数排序适用于取值范围为 0..k 的整数。它先统计每个值出现的次数，再用前缀和算出位置，最后把元素写入输出数组。时间复杂度为 O(n + k)，额外空间为 O(n + k)，且能保持相等元素的原始顺序。

如果知道有多少元素小于等于某个值，就能算出这个值对应区间的末尾位置。像给宾客安排座位：先统计每组人数，累加后划出各组的座位区间，再让宾客入座。整个过程不需要比较两个元素谁大谁小。

计数排序如何把次数变成位置

算法分成三个阶段，同一个 count 数组在不同阶段有不同含义。

先统计频次。遍历输入，对每个值 v 执行 count[v] += 1。此时 count[3] = 3 表示数值 3 出现了三次。元素的值只用来索引计数数组，不与另一个元素比较。

再计算前缀和。从左到右执行 count[i] += count[i - 1]。这一步之后，count[3] 表示“小于等于 3 的元素总数”。例如它变为 7，就说明所有值不大于 3 的元素占据前七个位置，最后一个 3 应在下标 6。数组还是那几个格子，含义已经从频次变成了区间边界。

为什么计数排序要倒序放置

第三阶段分配输出数组，从后向前遍历输入。读到值 v 后，先减少 count[v]，再写入 out[count[v]]。前缀和记录的是对应区间末尾之后的位置，所以必须先减一。

倒序遍历保证稳定性。输入中最后一个 v 最先被读取，占据这一组最后的位置；倒数第二个 v 占据它左边的位置，以此类推。相等元素虽然从右向左放置，最终顺序仍与输入一致。

如果改成正序遍历，却仍从各组末尾向前填，相等元素就会反向排列。只检查数值大小看不出问题，但按键排序的记录会失去原始顺序。基数排序也依赖每轮排序的稳定性，不能忽略这一点。

计数排序逐步演示

默认输入为 [2, 5, 3, 0, 2, 3, 0, 3]，共有八个元素，k = 5。相等元素按原始顺序加上标记，例如 3ᵃ、3ᵇ、3ᶜ。

1. 统计频次：0 出现两次，2 出现两次，3 出现三次，5 出现一次，得到 count = [2, 0, 2, 3, 0, 1]。
2. 计算前缀和：从左到右累加，得到 [2, 2, 4, 7, 7, 8]。其中 count[3] = 7 表示有七个元素小于等于 3。
3. 放置 3ᶜ：从 arr[7] = 3 开始，把 count[3] 从 7 减到 6，写入 out[6] = 3。最后一个 3 占据这一组的最后位置。
4. 放置 0ᵇ：读到 arr[6] = 0，count[0] 从 2 减到 1，写入 out[1] = 0。
5. 放置 3ᵇ：读到 arr[5] = 3，count[3] 从 6 减到 5，写入 out[5] = 3，恰好在 3ᶜ 左边。
6. 完成其余放置：2ᵇ 写入 out[3]，0ᵃ 写入 out[0]，3ᵃ 写入 out[4]，5 写入 out[7]，2ᵃ 写入 out[2]。结果为 [0, 0, 2, 2, 3, 3, 3, 5]，每组相等元素仍按原始顺序排列。

动画把计数行放在输入与输出之间。统计阶段，每次访问使对应计数增加；前缀和完成后，这一行变成位置记录。放置时，元素经过对应位置格再进入输出。重复值的标记和分组括号用于核对稳定性。

时间与空间复杂度

输出数组需要 n 个位置，计数数组需要 k + 1 个位置，因此额外空间为 O(n + k)。这是一种稳定的非原地排序。输入是否有序，不改变统计、前缀和与放置阶段的遍历范围。

限制主要来自 k。如果只有四个数，却分布在 0..29，就要分配 30 个计数格，前缀和还需经过其中 29 个位置。场景面板提供了这组输入，可以对比元素数量与计数范围各自带来的工作量。若 k 增长到十亿，计数数组也会占用约十亿个位置，即使输入仍只有四个数。

本课把键值限制在 30 以内，是为了让计数行放得下；这不是计数排序算法本身的上限。

边界情况

• 空数组：求 max(arr) 前需要单独处理。本课界面要求至少一个元素。
• 单元素数组：统计和放置各执行一次，前缀和仍需遍历对应的键值范围。
• 全部相等：计数集中在一个格子，倒序放置后仍保持原始顺序。
• 全部为零：k = 0，前缀和循环不执行，频次已经能确定输出区间。
• k 远大于 n：结果仍正确，但时间和空间可能主要消耗在计数数组上。

常见错误

• 从前向后放置：配合“边界递减”的写法会倒转相等元素的顺序。测试时应区分记录身份，不能只检查数值是否有序。
• 先写入再递减：前缀和指向区间末尾之后的位置，必须先减一，否则会越过该组边界。
• 按 n 分配计数数组：需要的是 max(arr) + 1 个格子，而不是 len(arr) 个。
• 直接输入负数、浮点数或字符串：这个实现用非负整数作下标。负整数需要先做偏移，其他类型不能直接套用这种计数方式。