计数排序通过偏移法处理负数：先求出数组最小值min_val，将所有元素减去min_val映射到非负区间，计数数组长度为max_val−min_val+1，排序后再统一加回min_val还原。
计数排序怎么处理负数？
标准 counting_sort 要求输入是非负整数，因为它的核心是用数组下标当键——下标不能为负。直接对含负数的数组调用，会触发越界访问或逻辑错乱。
解决办法是「整体平移」：找出最小值 min_val，把每个数减去它，让最小值变成 0，整个数组映射到非负区间；排序完再加回去。
- 必须先遍历一次数组求
min_val和max_val，否则无法确定计数数组大小 - 计数数组长度应为
max_val - min_val + 1，不是max_val + 1 - 如果数值范围太大（比如
min_val = -1e9, max_val = 1e9），计数数组会占几百 MB 内存，这时别硬上计数排序
示例关键片段：
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<int> count(range, 0);
for (int x : arr) count[x - min_val]++;
// ... 然后累加、反向填充
for (int i = 0, idx = 0; i < range; ++i)
while (count[i]-- > 0)
arr[idx++] = i + min_val; // 记得加回 min_val
基数排序怎么支持负数？
基数排序本身不限制正负，但常见实现（尤其是 LSD 版本）默认按字节或位分组时，会把负数的补码形式当成大正数处理，导致 -1 > 100 这种反直觉结果。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
根本原因是符号位参与了排序——LSD 从低位开始排，最高位（符号位）最后才被考虑，而高位为 1 的负数在无符号解读下数值极大。
- 最稳妥的做法：分离正负，分别排序，再合并（负数降序排，正数升序排）
- 更高效的做法：用补码偏移（bias），把有符号整数视作无符号整数处理——对 32 位
int，加0x80000000即可（即异或INT_MIN） - 注意：偏移只用于排序过程中的比较/分桶，原始值存储和输出不改变
偏移法示例（以 8 位为例）：
// 原始: -2 → 0xFE, 1 → 0x01 // 偏移后: -2 ^ 0x80 = 0x7E, 1 ^ 0x80 = 0x81 // 此时 0x7E < 0x81，排序位置正确
什么时候该放弃计数/基数排序？
两者都依赖「数值范围可控」这个前提。一旦出现以下情况，实际性能可能不如 std::sort：
- 输入中负数和正数跨度极大（如
[-1000000, 9999999]），计数数组稀疏且巨大 - 数据类型是
float或自定义结构体，无法自然映射到整数桶 - 元素数量少（
特别是对 vector<int> 排序，除非你明确知道值域很窄（比如成绩 0–100、年份 1970–2030），否则优先用 std::sort ——它内部是混合快排+堆排+插入排序，对各种分布都鲁棒。
负数排序最容易被忽略的细节
不是算法写错，而是边界处理漏掉一两个符号：
- 计数排序里
x - min_val可能溢出（若min_val是INT_MIN），应改用static_cast<long long>(x) - min_val防止 UB - 基数排序用偏移法时，必须保证所有整数类型宽度一致（比如混用
int和long会出错） - 如果排序的是指针或索引而非原始值，平移或偏移后记得还原——这点在写泛型模板时特别容易忘
