C++实现基于计数排序的稳定排序 _ 数组频率表与前缀和【源码】-C++-PHP中文网

计数排序必须用前缀和才能稳定，因其将count数组转化为每个值的末尾位置指针，结合倒序遍历原数组，确保相同元素相对顺序不变；前缀和需包含count[0]到count[i]累加，长度为max_val+1，负数时须用偏移对齐下标。

c++实现基于计数排序的稳定排序 _ 数组频率表与前缀和【源码】

为什么计数排序必须用前缀和才能稳定

计数排序稳定性的核心不在“计数”，而在“反向填充时的索引定位”。如果直接按 count[i] 的原始频次从左到右填，相同元素会按输入顺序倒置（比如输入中先出现的 3 反而填在后面），破坏稳定性。前缀和把 count 转成“每个值的末尾位置指针”，再倒序遍历原数组，就能保证相同值的相对顺序不变。

关键点：prefix[i] 表示值为 i 的元素在输出数组中的**最后一个可填位置（含）**，填完就执行 --prefix[i]。

前缀和必须包含 count[0] 到 count[i] 的累加，不能跳过 0
前缀和数组长度应为 max_val + 1，而非 max_val；若数据含负数，需整体偏移
倒序遍历原数组是硬性要求，正序会破坏稳定

C++ 中处理非零起点和负数的通用写法

标准计数排序假设数据范围是 [0, k]，但实际数组常含负数或最小值 > 0。硬编码 max_val 容易越界或浪费空间。更健壮的做法是先扫描获取 min_val 和 max_val，再用偏移量 offset = -min_val 对齐下标。

例如输入为 {-5, 0, 3, -2}，则 min_val = -5，max_val = 3，range = max_val - min_val + 1 = 9，所有值映射为 val + offset（即 -5→0, -2→3, 0→5, 3→8）。

偏移后下标范围是 [0, range-1]，前缀和数组长度也必须是 range
还原时用 output[i] - offset，不是 output[i] + offset
不要用 vector<int>(max_val+1)</int> 初始化计数数组——若 min_val ，这会导致访问越界

完整可运行的 C++ 实现（含边界检查）

以下代码支持任意整数数组（含负数）、自动推导范围、堆栈安全（不依赖全局缓冲区），并做了基本输入校验：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

#include <vector>
#include <algorithm>
#include <climits><p>std::vector<int> counting_sort(const std::vector<int>& arr) {
if (arr.empty()) return arr;</int></int></p>
<pre class="brush:php;toolbar:false;">// 扫描获取范围
auto [min_it, max_it] = std::minmax_element(arr.begin(), arr.end());
int min_val = *min_it, max_val = *max_it;
int range = max_val - min_val + 1;
int offset = -min_val;

// 分配计数与前缀和数组（大小为 range）
std::vector<int> count(range, 0);
for (int x : arr) {
    count[x + offset]++;
}

// 构建前缀和：prefix[i] = count[0]+...+count[i]
std::vector<int> prefix = count;
for (int i = 1; i < range; ++i) {
    prefix[i] += prefix[i-1];
}

// 输出数组，倒序填充保证稳定
std::vector<int> output(arr.size());
for (auto it = arr.rbegin(); it != arr.rend(); ++it) {
    int idx = *it + offset;
    output[--prefix[idx]] = *it;
}

return output;

}

注意：std::minmax_element 是 C++11 起支持的，若用旧编译器可改用两次 std::min_element/std::max_element。