直接用 count[arr[i]] 会越界，因 arr[i] 可能为负；需偏移映射为 count[arr[i]−min_val]，并逆序回填保证稳定。
为什么直接用 count[i] 当索引会越界
计数排序要求输入是已知范围的非负整数，但实际数据常含负数或稀疏分布。若数组最小值是 -100，最大值是 200，直接用 count[arr[i]]++ 会让 arr[i] == -100 时访问 count[-100] —— 这是未定义行为，大概率崩溃或静默错误。
核心解法是「偏移映射」：把原值 x 映射到非负索引 x - min_val。这要求提前扫描一遍确定 min_val 和 max_val，再分配大小为 max_val - min_val + 1 的计数数组。
- 不预扫描而硬设偏移（如统一加
1000）会导致空间浪费严重，[-1, 1]和[-1000, 1000]都要开 2001 元素 - 若忽略负数直接断言
arr[i] >= 0，上线后遇到非法输入就 crash，不是稳定 - 映射必须全程一致：计数、累加、回填三阶段都用同一偏移量，否则位置错乱
std::vector<int></int> 计数数组比 new int[] 更安全
手动 new 分配后容易忘 delete[]，异常路径下必然泄漏；而 std::vector 自动管理生命周期，且支持移动语义，避免深拷贝开销。
注意初始化方式：std::vector<int> count(range_size, 0)</int> 比 std::vector<int>(range_size)</int> 更明确——后者依赖默认初始化（int 是 0，但逻辑意图更清晰）。
- 别用
count.resize(range_size)后循环赋 0，多一次遍历 - 若范围极大（如
max_val - min_val > 1e7），计数排序本身就不适用，应换桶排序或基数排序 - vector 的
.data()可直接传给 C 风格函数，无需额外转换
累加计数数组时，为什么从 i = 1 开始而非 i = 0
累加目的是让 count[i] 表示「≤ 映射值 i 的元素个数」，从而定位每个值在输出数组中的**右边界**。若从 0 开始累加：count[0] += count[-1] 会越界；正确做法是跳过 i = 0，从 i = 1 往后做 count[i] += count[i-1]。
回填必须**逆序遍历原数组**：对每个 arr[i]，先算映射索引 idx = arr[i] - min_val，查 count[idx] 得到它应放的末位置，然后 count[idx]--。逆序保证相同值的相对顺序不变（稳定性的关键）。
- 正序回填会使相同值按逆序排列，破坏稳定性
- 累加后
count[idx]表示「最后一个该值的位置 + 1」，所以回填用--count[idx]刚好落到有效下标 - 如果漏掉
--count[idx]，所有相同值都会写到同一个位置，覆盖掉前面的
完整可运行的稳定计数排序函数
以下代码处理任意整数区间，自动检测范围，内存安全，保持稳定性：
void countingSort(std::vector<int>& arr) {
if (arr.empty()) return;
auto [min_it, max_it] = std::minmax_element(arr.begin(), arr.end());
int min_val = *min_it, max_val = *max_it;
int range_size = max_val - min_val + 1;
std::vector<int> count(range_size, 0);
for (int x : arr) count[x - min_val]++;
for (int i = 1; i output(arr.size());
for (int i = arr.size() - 1; i >= 0; --i) {
int idx = arr[i] - min_val;
output[--count[idx]] = arr[i];
}
arr = std::move(output);
}
</int></int>
最易被忽略的是：std::minmax_element 返回的是迭代器，必须解引用；以及 --count[idx] 必须在赋值前执行——这两处写反，排序就全乱了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
