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

本文共计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]]--

这个 -- 操作保证了下次遇到相同值时，会填到前一个位置，从而维持输入中靠后的元素在输出中也靠后。