计数排序必须反向遍历填充结果数组以保证稳定性：正向遍历时相同元素会逆序填入，破坏原始相对顺序；反向遍历时每个值最后一次出现先定位、再递减计数，从而保持稳定。
计数排序为什么必须用反向遍历填充结果数组
因为正向遍历会破坏稳定性：相同元素的相对顺序会被打乱。比如输入 [2, 1, 2, 0]，若从左到右处理，第一个 2 会填到位置 3，第二个 2 填到位置 2（累计频次递减后），结果中两个 2 的顺序就颠倒了。
反向遍历确保每个值最后一次出现的位置先被写入，再递减计数，这样相同值的原始先后关系就被保留下来。
- 累计频率表构建完成后，
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；之后两次扫描：第一次统计频次，第二次累加得到前缀和。
- 不要用
std::vector—— 这在(max_val + 1) 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 分配会失败或耗尽内存，此时不应使用计数排序。
- 输入为空时，提前返回，避免
min_element/max_element解引用空迭代器 - 用
long long计算range防止max_val - min_val溢出 int -
count容器类型推荐std::vector，因为频次不可能为负，且可能超过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 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);</size_t>
}
稳定性的关键不在“是否记录原始下标”，而在于反向遍历 + 累计频次递减写入。一旦跳过偏移处理、误用正向填充、或忽略值域检查，算法就会在边界 case 上静默失败。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
