计数排序必须用累计频率表以保证稳定性，因其能确定每个值最后应填入的位置，结合反向遍历使相同值保持输入顺序；需处理负数偏移、严格边界检查及自减更新。
为什么计数排序必须用累计频率表
稳定性的核心在于：相同值的元素，输出顺序要和输入顺序一致。只统计频次（比如 count[arr[i]]++）无法保留原始位置信息；而累计频率表（count[i] 表示 ≤ i 的元素个数）天然给出每个值「最后应填入的位置」——只要从原数组末尾开始遍历，就能让后出现的相同值填到更靠后的位置，从而保持稳定。
常见错误是直接用频次数组正向填充：output[count[val]--] = val，这会破坏稳定性，因为先遇到的 val 反而被填到后面。
- 累计前：若
arr = [2,1,2,0]，则count = [1,1,2] - 累计后：变成
[1,2,4]，表示值 0 占第 0 位，值 1 占第 1 位，值 2 占第 2–3 位 - 反向遍历时，第二个 2 会填入
output[3]，第一个 2 填入output[2]，顺序不变
如何正确构建累计频率表并处理偏移
输入数据可能含负数或非零起点（如 arr = [-5, -2, 0, 3]），不能直接用 arr[i] 当下标。必须先求出最小值 min_val，把所有值平移为非负：实际下标 = arr[i] - min_val。累计表长度为 max_val - min_val + 1。
累计过程必须从左到右累加：count[i] += count[i-1]，不能用前缀和函数库替代，否则容易忽略边界（如 i=0 时跳过）。
立即学习“C++免费学习笔记（深入）”；
- 若
min_val = -5，max_val = 3，则range = 9，count数组大小为9 - 原始值
-2映射到下标3（因为-2 - (-5) = 3） - 累计时，
count[0]保持不变，count[1] += count[0]，依此类推
反向填充时下标计算与边界检查
填充必须从原数组末尾开始（i = n-1 到 0），每次取 val = arr[i]，算出映射下标 idx = val - min_val，然后查累计表得位置 pos = count[idx] - 1，再执行 count[idx]--。这里 -1 是关键：累计值表示「≤ val 的总数」，但数组索引从 0 开始。
漏掉 -1 会导致越界或覆盖；不减 count[idx] 会导致重复值全挤在同一位置。
- 假设
count[idx] == 4，说明值val应填入第 4 个位置 → 索引是3，所以用count[idx] - 1 - 填完立刻
count[idx]--，为下一个相同值腾出前一位 - 务必确保
idx在[0, count.size())范围内，否则触发未定义行为
C++ 实现中容易被忽略的内存与类型细节
累计表和输出数组都需预分配足够空间。用 std::vector<int></int> 比裸指针安全，但要注意：若输入为空，min_val/max_val 无定义，需提前返回；若范围过大（如 max_val - min_val > 1e7），计数排序不再适用，应换算法。
count 数组元素类型必须是 size_t 或足够大的整型（如 long long），避免累加溢出；但最终填入 output 的索引仍要用 int 或 size_t 匹配容器 size_type。
- 不要写
vector<int> count(range)</int>后直接count[0] = freq[0]—— 这会覆盖初始 0 值，应先统计频次再累计 - 反向循环变量用
int i = n-1即可，不用size_t，避免i--下溢成极大正数 - 复制回原数组时，用
std::copy(output.begin(), output.end(), arr.begin())，别手写循环漏掉边界
稳定的关键不在“累计”本身，而在累计后是否严格按反向顺序、带偏移校验、带自减更新去填；任何一环松动，稳定性就没了。
