C语言中如何实现计数排序的稳定优化版，结合累计频率表与反向填充算法？

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

由于正向遍历会破坏稳定性：

反向遍历确保每个值最后一次出现的位置先被写入，再递减计数，这样相同值的原始先后关系就被保留下来。

• 累计频率表构建完成后，count[i] 表示值 ≤ i 的元素个数，不是“值为 i 的元素个数”
• 反向填充时，对每个 arr[j]，取 count[arr[j]] - 1 作为其在 output 中的下标
• 填完立即执行 count[arr[j]]--，为下一个相同值腾出前一位索引

如何正确初始化和构建累计频率表（避免越界与偏移）

如果输入含负数，直接用 arr[i] 当下标会访问非法内存。稳定版必须做偏移校正：找出最小值 min_val，所有值统一减去它，映射到非负区间 [0, max_val - min_val]。

累计频率表长度应为 range = max_val - min_val + 1，初始化为全 0；之后两次扫描：第一次统计频次，第二次累加得到前缀和。