基数排序不能直接用std::sort替代，因其是非比较型排序，对固定位宽整数可达O(n)，而std::sort下限为O(n log n)；但基数排序不通用，需手动处理负数偏移、类型映射等。
基数排序为什么不能直接用 std::sort 替代
因为 std::sort 是比较型排序，时间复杂度下限是 O(n log n)，而基数排序本质是非比较的，对固定位宽整数可做到 O(d·n)（d 是位数），比如处理 32 位整数且按 byte 分 4 轮时，d=4，实际就是 O(n)。但代价是：它不通用——不能直接排 double、string 或自定义类型，除非你手动定义“位展开规则”。
常见错误现象：std::sort 被误认为“万能排序函数”，结果在大量小范围整数（如像素值 0–255）场景下跑不过手写的基数排序。
- 适用场景：数组元素是
int、unsigned int或已映射为非负整数的索引（如计数排序前置） - 不适用场景：含负数未做偏移、浮点数未转比特表示、字符串长度不一且未补零
- 性能影响：每轮需计数 + 前缀和 + 输出数组搬运，空间开销 O(n + k)，k 是基数（如 256）
如何安全处理负数——别直接强转 unsigned int
直接把 int 强转成 unsigned int 再进基数排序，会把 -1 变成 4294967295，彻底打乱顺序。正确做法是做符号位偏移，让最小值变成 0。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 先扫一遍数组，拿到
min_val和max_val，确认值域宽度；若全为非负，跳过偏移 - 统一加上
-min_val，使所有数 ≥ 0；排序完再统一减回去 - 如果已知范围（如温度 -50 到 50），可硬编码偏移量 50，避免运行时扫描
- 注意溢出：
int加偏移后不能超过INT_MAX，否则改用long long中间存储
示例关键片段：
int offset = -min_val; for (int& x : arr) x += offset; // ... 基数排序 ... for (int& x : arr) x -= offset;
按 byte 还是按 bit 分桶？选 256 不是 2
按单 bit 分（基数=2）要跑 32 轮，缓存不友好，实际慢；按 byte 分（基数=256）只用 4 轮，每轮计数数组仅 256 个 int，L1 缓存全装得下。
参数差异与取舍：
- 基数选
256：适合 32/64 位整数，sizeof(int)决定轮数，代码简洁 - 基数选
65536（2¹⁶）：轮数减半，但计数数组翻倍（65536 个int≈ 256KB），可能挤出 L2 缓存，反而变慢 - 避免动态算基数：不要用
1 然后传参，编译期固定 <code>256更利于循环展开和常量传播
提取某字节的标准写法：(x >> (i * 8)) & 0xFF，其中 i 是第 i 轮（0 ≤ i
原地排序做不到，但可以避免 vector 多次扩容
基数排序天然需要输出缓冲区，所谓“原地”只是指不依赖递归栈或堆分配新容器——但你仍得准备一个和输入等长的临时数组。频繁 vector::resize 或 push_back 会触发多次内存分配，拖慢速度。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 构造时就指定容量：
std::vector<int> output(arr.size())</int>，而非默认构造后 push - 双缓冲交替：用两个数组 a/b，第 0 轮读 a 写 b，第 1 轮读 b 写 a，最后检查末轮输出是否在原数组，不是就
std::swap - 避免
std::vector<bool></bool>：它不是真正的容器，位压缩导致随机访问慢，计数数组必须用std::vector<int></int>
容易被忽略的一点：如果输入是 const std::vector<int>&</int>，别试图在函数内修改它——要么接受拷贝成本，要么要求调用方传入可写引用。
