计数排序适用于整数且值域较小的场景，如分数0–100、RGB分量0–255等；遇负数需偏移处理，值域过大时空间和时间开销反超比较排序。
计数排序适合什么场景
计数排序不是通用排序算法，它只适用于整数且范围不太大的情况。比如对 std::vector<int></int> 排序，若所有元素都在 [0, 1000] 内，用计数排序比 std::sort 更快、稳定、且时间复杂度是 O(n + k)（k 是值域大小）。但一旦数据里有负数、浮点数或值域极大（如 [-1e9, 1e9]），就别硬上——内存会爆，或者效率反不如比较排序。
处理负数的常见错误和修正方法
原生计数排序假设输入非负，遇到负数直接下标越界。典型错误是写成：count[arr[i]]++，而 arr[i] 是负数时访问非法内存。
解决办法是做偏移（offset）：先遍历一次找最小值 min_val，把每个数映射到非负区间：index = arr[i] - min_val。注意：
-
count数组大小必须是max_val - min_val + 1，不能只用max_val + 1 - 输出时要还原：
result[j] = i + min_val（其中i是count的下标） - 如果只排非负数，
min_val == 0，偏移可省略，但显式写出更安全
用 vector 实现的完整可运行片段
下面是一个兼顾负数、不依赖额外库函数、清晰可调试的版本：
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
void countingSort(std::vector<int>& arr) {
if (arr.empty()) return;
<pre class="brush:php;toolbar:false;">int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
int range = max_val - min_val + 1;
std::vector<int> count(range, 0);
for (int x : arr) {
count[x - min_val]++; // 映射到 [0, range)
}
int idx = 0;
for (int i = 0; i < range; ++i) {
while (count[i]-- > 0) {
arr[idx++] = i + min_val;
}
}}
关键点：
- 用
std::min_element和std::max_element避免手写循环出错 -
count初始化为0，确保每个桶清空 - 覆盖原数组（in-place）时，用
while循环展开频次，比嵌套for更直观
性能与空间取舍提醒
计数排序的空间开销由值域决定，不是由数组长度决定。例如 arr = {1, 2, 1000000}，哪怕只有 3 个数，range 也会是 1000000，count 分配百万个 int。这时候它已经比 std::sort 慢且耗内存。
真正该用它的场合是：你知道值域上限（比如考试分数 0–100、RGB 分量 0–255、小写字母 ASCII 97–122），并且实际数据量较大（>1e4）、需要稳定排序或极致线性时间。
偏移计算和边界检查看似啰嗦，但漏掉任意一环都会导致崩溃或静默错误——尤其在 C++ 里，越界写 count 不报错，只悄悄破坏其他变量。
