std::sort不是基数排序的替代品，因其为比较型排序、最坏O(n log n)，而基数排序对固定位宽整数可达O(n×k)；但需手动控制位宽、进制与内存布局，标准库不提供接口。
为什么 std::sort 不是基数排序的替代品
因为 std::sort 是比较型排序，最坏 O(n log n)，而基数排序对整数可做到 O(n × k)（k 是位数），当数据范围固定、n 很大时，实际更快。但它的前提是：你得自己控制位宽、进制和内存布局——标准库不提供现成接口。
常见错误现象：std::sort 在处理上百万个 int32_t 时比手写基数排序慢 1.5–2 倍；有人试图用 std::stable_sort 模拟计数排序，结果因内存分配抖动反而更慢。
- 适用场景：批量排序无符号整数（
uint32_t、size_t）、或已归一化为非负整数的 key（比如哈希桶索引、离散化后的 ID） - 不适用：带符号整数直接丢进去会错——负数补码最高位为 1，排在正数后面，需先做偏移转换
- 性能关键点：每轮计数排序的桶数组必须栈分配（如
int bucket[256]），堆分配或std::vector会显著拖慢
如何用 8-bit 分桶实现 uint32_t 的 4 轮基数排序
按字节拆分，每轮处理 8 位，共 4 轮。比 16-bit 分桶更省内存（256 个桶 vs 65536），缓存友好，实测在 x86-64 上吞吐更高。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 输入数组必须是
std::vector<uint32_t></uint32_t>或裸指针 + size，避免迭代器抽象开销 - 每轮用两个缓冲区交替：原数组 → 临时数组 → 原数组，避免拷贝全部数据，只交换指针/引用
- 计数阶段用
bucket[i] = 0初始化，别用std::fill——循环展开或 memset 更快 - 偏移累加时用前缀和：遍历
bucket，把bucket[i]改成 “小于等于 i 的元素总数”，方便后续直接定位写入位置
示例关键片段（第 0 轮，处理最低字节）：
for (size_t i = 0; i < n; ++i) {
uint8_t b = static_cast<uint8_t>(arr[i]);
bucket[b]++;
}
// 前缀和
for (int i = 1; i < 256; ++i) {
bucket[i] += bucket[i-1];
}
// 逆序写入（保证稳定）
for (size_t i = n; i-- > 0; ) {
uint8_t b = static_cast<uint8_t>(arr[i]);
out[--bucket[b]] = arr[i];
}
处理 int32_t 时怎么避免符号位搞乱顺序
补码下 -1 == 0xFFFFFFFF，比 INT_MAX 还大，直接排序会让负数全排在最后。不能靠 abs()，会溢出；也不能简单加偏移（如 +2147483648），得用位操作绕过符号解释。
正确做法：把 int32_t 当作 uint32_t 重解释，再异或一个掩码翻转符号位。
- 转换公式：
uint32_t key = *p ^ 0x80000000U（p指向int32_t） - 原理：把最高位从“符号位”变成“大小位”——原来负数高位为 1，异或后变 0，自然排在前面；正数高位为 0，变 1，排在后面
- 还原时再异或一次即可，无需额外存储；整个过程零开销，编译器通常优化成单条
xor指令 - 错误示范：用
static_cast<uint32_t>(x) + 0x80000000U</uint32_t>—— 对负数是未定义行为（有符号转无符号在 C++20 前依赖实现）
什么时候该放弃基数排序改回 std::sort
基数排序不是银弹。当数据量小（n ）、或 key 分布极度稀疏（比如全是 <code>0 和 0x7FFFFFFF）、或内存受限时，它反而更慢甚至崩掉。
- 缓存失效：每轮扫描整个数组 + 随机写入 256 个桶的起始位置，若
n太小，CPU 缓存反复换入换出，不如std::sort的局部访问模式 - 分支预测失败：桶计数循环中
bucket[b]++的b若高度随机，现代 CPU 的分支预测器会大量失准 - 容易被忽略的点：如果你要排序的是结构体数组（比如
struct { int key; float val; }），按 key 排序时必须同时搬运整个 struct —— 此时每轮 memcpy 成本飙升，除非你用索引间接排序，否则收益可能归零
