计数排序适合非负整数或值域范围远小于元素个数的数据，需预估最小值min_val和最大值max_val，且max_val−min_val+1在内存可接受范围内（如≤10⁷），负数需通过偏移转换为非负下标。
计数排序适合什么数据特征
计数排序只在整数范围远小于元素个数时才有意义。比如 100 万个 int，但值全落在 [0, 999] 内——这时用计数排序比 std::sort 快得多；但如果值域是 [0, INT_MAX]，开数组直接炸内存。
关键判断点：
– 输入是否全为非负整数？（若含负数需偏移）
– 最大值 max_val 和最小值 min_val 是否可预估？
– max_val - min_val + 1 是否在内存可接受范围内（比如 ≤ 10⁷ 个 int）？
手写计数排序的三步核心逻辑
不依赖 STL 容器，用原始数组实现，避免动态分配开销：
- 第一步：扫描输入，找出
min_val和max_val，计算桶长range = max_val - min_val + 1 - 第二步：分配
count数组（new int[range]{}），再次遍历输入，对每个x执行count[x - min_val]++ - 第三步：按桶顺序展开结果：对每个
i从0到range-1，把min_val + i写入输出数组共count[i]次
注意：第三步必须原地或顺序写入，不能边统计边覆盖原数组——否则会破坏未处理的值。
立即学习“C++免费学习笔记（深入）”；
负数和内存安全怎么处理
遇到负数不能直接当数组下标，常见错误是硬写 count[x]++ 导致越界崩溃。正确做法是统一偏移：
- 若已知值域，比如
[-5000, 5000]，直接设offset = 5000，用count[x + offset] - 若值域未知，必须先遍历一次求出
min_val，再用x - min_val作下标 -
count数组建议用new int[range]{}（带初始化为 0），别用malloc，否则要手动memset - 记得
delete[] count—— 大量数据下漏释放会导致 OOM
示例片段（无负数场景）：
void counting_sort(int* arr, int n) {
if (n <= 1) return;
int min_val = *arr, max_val = *arr;
for (int i = 1; i < n; ++i) {
if (arr[i] < min_val) min_val = arr[i];
if (arr[i] > max_val) max_val = arr[i];
}
int range = max_val - min_val + 1;
int* count = new int[range]{};
for (int i = 0; i < n; ++i) count[arr[i] - min_val]++;
int idx = 0;
for (int i = 0; i < range; ++i)
while (count[i]-- > 0)
arr[idx++] = min_val + i;
delete[] count;
}
比 std::sort 快在哪？又容易栽在哪？
纯整数小范围下，计数排序是 O(n + k)，k 是值域大小；而 std::sort 是 O(n log n)，当 k [0, 9999] 数据，手写计数排序通常快 3–5 倍。
但几个坑很隐蔽：
- 没检查
range是否溢出：max_val - min_val是int，若差值超INT_MAX会回绕成负数，导致new int[negative]报错 - 误以为“小范围”=“数值小”，其实关键是“跨度小”。
[1000000, 1000009]跨度才 10，照样能用 - 多线程环境下不能复用同一块
count数组，也没法并行第三步的写入——它本质是串行展开
真正要上生产，得加一层校验：计算 range 前先判断 max_val >= min_val 且 max_val - min_val 这类硬限制。
