计数排序适用于值域较小的整数，如[0,10000]或[-500,500]；需通过偏移处理负数，避免内存溢出，不适用于浮点数、字符串或大范围整数。
计数排序适合什么数据范围
计数排序只适用于整数，且值域不能太大。核心限制是：若最大值为 max_val、最小值为 min_val，则需分配长度为 max_val - min_val + 1 的计数数组。如果 max_val 是 1e9，直接崩——内存溢出或超时。
典型适用场景：vector 中所有元素都在 [0, 10000] 或 [-500, 500] 范围内；比如成绩统计、字符频次（char 可映射为 0–255）、枚举状态码等。
- 输入含负数？必须做偏移：用
arr[i] - min_val作下标 - 输入全是大整数但数量极少？别用计数排序，改用
std::sort或基数排序 - 元素类型是
double或字符串？计数排序不适用，它不是泛型算法
如何写一个安全的 C++ 计数排序函数
标准实现要处理三件事：找极值、建计数桶、回填结果。关键点是避免硬编码 0 为起点，也别用 vector(100000) 这种危险写法。
下面是一个带偏移、支持负数、使用 size_t 防下标越界的版本：
立即学习“C++免费学习笔记（深入）”；
void countingSort(vector& arr) {
if (arr.empty()) return;
int min_val = *min_element(arr.begin(), arr.end());
int max_val = *max_element(arr.begin(), arr.end());
int range = max_val - min_val + 1;
vector count(range, 0);
for (int x : arr) {
count[x - min_val]++; // 偏移后下标必在 [0, range)
}
size_t idx = 0;
for (int i = 0; i 0) {
arr[idx++] = i + min_val;
}
}
}
- 用
min_element/max_element而非手写循环，避免漏判空容器 -
count[i]-- > 0比for (int j = 0; j 更省一次乘法 - 没用额外输出数组，原地排序，但破坏了输入顺序（稳定版需另开 result 数组并反向遍历）
计数排序稳定吗？怎么改成稳定版本
基础版本不稳定——相同数值的相对顺序可能改变。要稳定，就得模拟“从右往左填入”的过程，并把计数数组转成“前缀和”，表示每个值最后应落在结果数组的哪个位置。
