计数排序是结构适配而非加速技巧，仅当数据全为整数、值域小且连续、重复多时可达o(n)；需先验证范围k=max-min+1是否≤n/2，再正向填充计数数组实现。

计数排序不是“加速技巧”，而是一种结构适配——它只在数据满足特定条件时，才能自然达成 $O(N)$ 时间。关键不在“怎么写代码”，而在“怎么确认场景匹配”。

适用前提必须同时满足

• 待排序元素全是整数
• 所有值落在一个已知、较小的连续区间内（例如 0–99、1–255、-100 到 +100）
• 实际出现的数值种类远少于总元素个数（即重复多、范围窄）

只要这三个条件成立，计数排序就能绕过比较逻辑，直接按频次摊平时间消耗。

第一步：快速判断是否值得用

别急着编码，先做三件事： - 扫一遍数组，记下最小值和最大值，算出范围 $k = \text{max} - \text{min} + 1$ - 如果 $k > 2N$（比如 10 万个数，范围却超过 20 万），空间开销大、缓存不友好，不如改用快排或三路快排 - 如果 $k \leq N/2$（比如 10 万个年龄数据，范围仅 0–120），就是理想场景

第二步：精简实现，避开常见坑

核心是“偏移映射”和“正向填充”，不需要前缀和+反向遍历也能稳定输出： - 计数数组大小为 $k$，索引 $i$ 对应原始值 $\text{min} + i$ - 遍历原数组，执行 `count[num - min]++` - 再用两个嵌套循环重建结果：外层扫 `count`，内层按次数重复写入 `min + i`

这样写更直观，也避免了经典教材中“反向遍历保证稳定性”带来的理解负担——当你的业务只要求数值有序（不要求相同年龄员工保持录入顺序），正向填充完全够用。

第三步：实战典型场景举例

- 学生成绩重排（0–100 分，10 万人）：$k = 101$，$O(N + k) \approx O(N)$，比快排快 3–5 倍 - IP 地址段统计后按段号排序（如 192.168.1.0–192.168.1.255）：提取最后 8 位当作整数，范围固定为 0–255 - 状态码聚合排序（HTTP 状态：200, 201, 400, 401, 403, 404, 500）：把状态码映射为 0–6 索引，再还原

这些都不是“强行套算法”，而是数据天然带结构——计数排序只是把这层结构显性地用起来。

第四步：边界与降级处理

- 若发现有非整数（如字符串状态 `"PENDING"`）、或范围过大（如时间戳毫秒级），立刻放弃，切到桶排序或基数排序子流程 - 可加轻量兜底：当 $k > N \times 1.5$ 时，自动 fallback 到 `Arrays.sort()`（Java）或 `std::sort()`（C++） - 不要为节省几 MB 内存而压缩计数数组（比如用 bitset 存布尔值）——频次信息一旦丢失，就不再是计数排序

它不复杂，但容易忽略匹配前提。真正高效的 $O(N)$，永远始于对数据分布的诚实观察。