如何编写稳定计数排序算法，利用累计频率表和反向填充策略的源代码实现？

本文共计874个文字，预计阅读时间需要4分钟。

在实现计数排序的原始版本中，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（值域跨度）到底有多大。