标准计数排序默认不稳定，因其原始实现中count数组仅记录频次，正向遍历输入时相同元素的相对顺序被破坏；稳定性需通过累计频率表+反向遍历实现，确保后出现的相同元素填入输出数组更靠后位置。
为什么标准计数排序默认不稳定
计数排序的原始实现中，count 数组只记录每个值的出现次数，填充输出数组时若按正向遍历输入，相同元素的相对顺序会被打乱。比如输入 [2, 1, 2, 0]，两个 2 的先后关系在简单累加后无法保留——本质是没区分“第几个 2”。稳定性的关键在于：**必须让后出现的相同元素，填到输出数组中更靠后的位置**。
用累计频率表 + 反向遍历输入实现稳定
核心思路是把 count 数组转为“小于等于该值的元素总数”，即累计频率（cumulative count），再从输入数组末尾开始处理：
- 先构建
count：统计每个键值的频次，下标对应键值（要求键值范围小且非负） - 再原地转换为累计频率：
count[i] += count[i-1]（i 从 1 开始），此时count[i]表示值 ≤ i 的元素个数 - 反向遍历输入数组
arr：对每个arr[j]，取count[arr[j]] - 1作为其在output中的索引，填入后执行count[arr[j]]--
这个 -- 操作保证了下次遇到相同值时，会填到前一个位置，从而维持输入中靠后的元素在输出中也靠后。
C++ 实现要点与边界处理
实际写 C++ 版本时，容易忽略三个细节：
立即学习“C++免费学习笔记（深入）”；
-
count数组大小必须覆盖[0, max_val]全区间，不能只开max_val + 1就完事——如果输入含0，下标0必须合法 - 累计频率转换时，循环起始必须是
i = 1，否则count[0]会被错误叠加；且需确保count已初始化为 0 - 反向填充时，
count[val] - 1是当前可用的最后一个位置，填完立刻count[val]--，不可颠倒顺序
示例关键片段：
int max_val = *max_element(arr.begin(), arr.end());
vector<int> count(max_val + 1, 0);
for (int x : arr) count[x]++;
for (int i = 1; i <= max_val; i++) count[i] += count[i-1];
vector<int> output(arr.size());
for (int i = arr.size() - 1; i >= 0; i--) {
int val = arr[i];
output[count[val] - 1] = val;
count[val]--;
}
当输入含负数或范围过大怎么办
原生计数排序不支持负数，因为数组下标不能为负。常见应对方式有两种：
- 偏移法：找出最小值
min_val，所有数减去它，使最小值变为 0；排序后再加回。但要求max_val - min_val仍可控（比如几千以内） - 放弃计数排序：若值域达
1e9级别，空间和初始化成本爆炸，应换用std::stable_sort或基数排序（radix sort）
另外，C++ 标准库没有内置计数排序，std::sort 是不稳定的，std::stable_sort 底层可能是归并，时间复杂度 O(n log n)，和计数排序的 O(n + k) 不在一个量级——选哪个，取决于你手上的 k（值域跨度）到底有多大。
