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；之后两次扫描：第一次统计频次，第二次累加得到前缀和。

立即学习“C++免费学习笔记（深入）”；

• 不要用 std::vector<int>(max_val + 1)</int> —— 这在 min_val 时漏掉负数部分
• 累计阶段循环范围是 1 到 range - 1，即 for (int i = 1; i
• 最终 count[i] 存的是“≤ (min_val + i)”的元素总数，不是原始值 i 的累计

C++ 实现中容易忽略的内存与类型细节

原地排序不可行——计数排序本质需要输出缓冲区。若强行覆盖输入数组，反向填充时会读到已被改写的值，导致逻辑崩溃。

另外，count 数组大小取决于值域跨度，不是输入长度。当 max_val - min_val 极大（如 INT_MAX）时，vector<int></int> 分配会失败或耗尽内存，此时不应使用计数排序。

• 输入为空时，提前返回，避免 min_element/max_element 解引用空迭代器
• 用 long long 计算 range 防止 max_val - min_val 溢出 int
• count 容器类型推荐 std::vector<size_t></size_t>，因为频次不可能为负，且可能超过 int 上限

void countingSort(vector<int>& arr) { if (arr.empty()) return; int min_val = *min_element(arr.begin(), arr.end()); int max_val = *max_element(arr.begin(), arr.end()); long long range = (long long)max_val - min_val + 1; if (range > 1e7) throw runtime_error("Value range too large for counting sort"); <pre class='brush:php;toolbar:false;'>vector<size_t> count(range, 0); for (int x : arr) count[x - min_val]++; for (long long i = 1; i < range; ++i) count[i] += count[i-1]; vector<int> output(arr.size()); for (int i = arr.size() - 1; i >= 0; --i) { int idx = arr[i] - min_val; output[count[idx] - 1] = arr[i]; count[idx]--; } arr = move(output);

}

稳定性的关键不在“是否记录原始下标”，而在于反向遍历 + 累计频次递减写入。一旦跳过偏移处理、误用正向填充、或忽略值域检查，算法就会在边界 case 上静默失败。