计数排序适用于值域较小的整数，如[0,10000]或[-500,500]；需通过偏移处理负数，避免内存溢出，不适用于浮点数、字符串或大范围整数。
计数排序适合什么数据范围
计数排序只适用于整数，且值域不能太大。核心限制是：若最大值为 max_val、最小值为 min_val，则需分配长度为 max_val - min_val + 1 的计数数组。如果 max_val 是 1e9，直接崩——内存溢出或超时。
典型适用场景：vector<int></int> 中所有元素都在 [0, 10000] 或 [-500, 500] 范围内；比如成绩统计、字符频次（char 可映射为 0–255）、枚举状态码等。
- 输入含负数？必须做偏移：用
arr[i] - min_val作下标 - 输入全是大整数但数量极少？别用计数排序，改用
std::sort或基数排序 - 元素类型是
double或字符串？计数排序不适用，它不是泛型算法
如何写一个安全的 C++ 计数排序函数
标准实现要处理三件事：找极值、建计数桶、回填结果。关键点是避免硬编码 0 为起点，也别用 vector<int>(100000)</int> 这种危险写法。
下面是一个带偏移、支持负数、使用 size_t 防下标越界的版本：
立即学习“C++免费学习笔记（深入）”；
void countingSort(vector<int>& arr) {
if (arr.empty()) return;
int min_val = *min_element(arr.begin(), arr.end());
int max_val = *max_element(arr.begin(), arr.end());
int range = max_val - min_val + 1;
<pre class="brush:php;toolbar:false;">vector<int> count(range, 0);
for (int x : arr) {
count[x - min_val]++; // 偏移后下标必在 [0, range)
}
size_t idx = 0;
for (int i = 0; i < range; ++i) {
while (count[i]-- > 0) {
arr[idx++] = i + min_val;
}
}}
- 用
min_element/max_element而非手写循环，避免漏判空容器 -
count[i]-- > 0比for (int j = 0; j 更省一次乘法 - 没用额外输出数组，原地排序，但破坏了输入顺序（稳定版需另开 result 数组并反向遍历）
计数排序稳定吗？怎么改成稳定版本
基础版本不稳定——相同数值的相对顺序可能改变。要稳定，就得模拟“从右往左填入”的过程，并把计数数组转成“前缀和”，表示每个值最后应落在结果数组的哪个位置。
稳定版关键步骤：
- 先统计频次
- 对
count做前缀和：count[i] = count[0] + ... + count[i] - 倒序遍历原数组，对每个
x，执行：result[--count[x - min_val]] = x
这样能保证后出现的相同元素填在更靠右的位置，从而保持原有顺序。
为什么实际项目里很少直接写计数排序
因为 STL 没提供，而手写要考虑边界太多：溢出、负数、空输入、内存峰值、稳定性需求……稍不注意就比 std::sort 慢。
真正用到它的场合，往往是嵌入式或性能极端敏感的模块，例如：
- 图像处理中对像素灰度值（0–255）做直方图均衡化
- 网络包解析时按协议字段枚举值（如 TCP flag = 0–63）分桶
- LeetCode 简单题练手，但生产代码优先选
std::sort+ 自定义比较器
另外注意：C++20 的 std::ranges::sort 仍是基于比较的，不会自动切到计数排序——编译器不替你做这个决策。
