计数排序必须用前缀和才能稳定，因其将count数组转化为每个值的末尾位置指针，结合倒序遍历原数组，确保相同元素相对顺序不变；前缀和需包含count[0]到count[i]累加，长度为max_val+1，负数时须用偏移对齐下标。
为什么计数排序必须用前缀和才能稳定
计数排序稳定性的核心不在“计数”，而在“反向填充时的索引定位”。如果直接按 count[i] 的原始频次从左到右填，相同元素会按输入顺序倒置（比如输入中先出现的 3 反而填在后面），破坏稳定性。前缀和把 count 转成“每个值的末尾位置指针”，再倒序遍历原数组，就能保证相同值的相对顺序不变。
关键点：prefix[i] 表示值为 i 的元素在输出数组中的**最后一个可填位置（含）**，填完就执行 --prefix[i]。
- 前缀和必须包含
count[0]到count[i]的累加，不能跳过 0 - 前缀和数组长度应为
max_val + 1，而非max_val；若数据含负数，需整体偏移 - 倒序遍历原数组是硬性要求，正序会破坏稳定
C++ 中处理非零起点和负数的通用写法
标准计数排序假设数据范围是 [0, k]，但实际数组常含负数或最小值 > 0。硬编码 max_val 容易越界或浪费空间。更健壮的做法是先扫描获取 min_val 和 max_val，再用偏移量 offset = -min_val 对齐下标。
例如输入为 {-5, 0, 3, -2}，则 min_val = -5，max_val = 3，range = max_val - min_val + 1 = 9，所有值映射为 val + offset（即 -5→0, -2→3, 0→5, 3→8）。
立即学习“C++免费学习笔记（深入）”；
- 偏移后下标范围是
[0, range-1]，前缀和数组长度也必须是range - 还原时用
output[i] - offset，不是output[i] + offset - 不要用
vector<int>(max_val+1)</int>初始化计数数组——若min_val ，这会导致访问越界
完整可运行的 C++ 实现（含边界检查）
以下代码支持任意整数数组（含负数）、自动推导范围、堆栈安全（不依赖全局缓冲区），并做了基本输入校验：
#include <vector>
#include <algorithm>
#include <climits>
<p>std::vector<int> counting_sort(const std::vector<int>& arr) {
if (arr.empty()) return arr;</p><pre class='brush:php;toolbar:false;'>// 扫描获取范围
auto [min_it, max_it] = std::minmax_element(arr.begin(), arr.end());
int min_val = *min_it, max_val = *max_it;
int range = max_val - min_val + 1;
int offset = -min_val;
// 分配计数与前缀和数组（大小为 range）
std::vector<int> count(range, 0);
for (int x : arr) {
count[x + offset]++;
}
// 构建前缀和：prefix[i] = count[0]+...+count[i]
std::vector<int> prefix = count;
for (int i = 1; i < range; ++i) {
prefix[i] += prefix[i-1];
}
// 输出数组，倒序填充保证稳定
std::vector<int> output(arr.size());
for (auto it = arr.rbegin(); it != arr.rend(); ++it) {
int idx = *it + offset;
output[--prefix[idx]] = *it;
}
return output;}
注意：std::minmax_element 是 C++11 起支持的，若用旧编译器可改用两次 std::min_element/std::max_element。
性能与空间取舍：什么时候不该用计数排序
计数排序时间复杂度是 O(n + k)，其中 k 是值域大小。当 k ≫ n（比如数组只有 100 个数，但最大值是 1e9），空间开销和初始化成本会远超快速排序。
- 值域超过
1e6时，vector<int>(k)可能分配失败或触发系统 OOM - 即使
k合理，若原数组已基本有序，std::sort的 introsort 通常更快且 cache 友好 - 计数排序无法直接用于浮点数或自定义类型——没有天然的“桶索引”
真正适合它的场景很窄：小整数范围（如字节值 0–255、年龄 0–120）、嵌入式环境对 worst-case 时间敏感、或作为基数排序的子过程。
