基数排序不直接用std::sort因其是非比较型算法，时间复杂度O(d×n)优于std::sort的O(n log n)，但需数据可拆位、额外空间，且std::sort无法满足其特定需求。
为什么基数排序在 C++ 中不直接用 std::sort
因为 std::sort 是基于比较的排序（如 introsort），时间复杂度下限是 O(n log n)；而基数排序是非比较型算法，对整数或固定长度字符串可做到 O(d × n)（d 是位数），适合大量小范围整数排序。但它要求数据能按“位”拆解，且需额外空间 —— 这正是手动实现时最常出错的地方。
用 std::vector 实现 LSD 基数排序（适用于非负整数）
LSD（Least Significant Digit）从低位开始逐轮计数排序，稳定、易实现。关键点不是“写循环”，而是处理好桶数组复用、偏移累加、结果回填三个环节：
- 每轮用大小为 10 的
count数组统计 0–9 各数字出现次数 - 必须做前缀和转换成位置偏移（
count[i] += count[i-1]），否则回填会错位 - 要**逆序遍历原数组**进行回填（保证稳定性），填完后交换指针/拷贝回原容器
- 最高位轮次结束后，结果就在输入容器中，无需额外判断符号位
void radixSort(std::vector& arr) { if (arr.empty()) return; const int maxVal = *std::max_element(arr.begin(), arr.end()); for (int exp = 1; maxVal / exp > 0; exp *= 10) { std::vector output(arr.size()); std::vector count(10, 0); for (int x : arr) count[(x / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i-1]; for (int i = arr.size() - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[--count[digit]] = arr[i]; } arr = output; } }
如何扩展支持负数和 int 全范围？
直接对负数取模行为未定义，且 (x / exp) % 10 在 x 为负时可能为负值。不能简单加偏移再模 10 —— 那会破坏位权意义。正确做法是：先分离符号，或改用 256 进制 + 无符号 reinterpret（更安全）：
- 推荐方案：将
int按字节（unsigned char）分 4 轮处理，用reinterpret_cast取第(&x) i字节 - 避免手动处理符号位翻转（如补码偏移），除非你明确需要 MSD 方式且控制输入范围
- 若坚持十进制 + 负数，须先将所有数统一加
INT_MIN转为无符号区间，排完再减回 —— 但要注意溢出（int加法可能 UB）
性能陷阱：桶大小、缓存与模板化优化
用 std::vector 看似合理，但在高频调用场景下，频繁分配/清零小数组会拖慢速度。实际工程中常见改进：
立即学习“C++免费学习笔记（深入）”；
- 把
count和output提到函数外作为参数传入，复用内存（尤其在多次排序同尺寸数组时） - 对
exp循环，如果最大值很小（如全在 [0, 999]），提前 break，别硬跑 10 轮 - 用
std::array替代vector，避免堆分配；但注意不能泛型适配不同进制（如 256） - 编译器对小数组循环展开效果有限，别盲目加
[[unroll]]—— 实测 clang/gcc 对for(i=1;i 自动展开了
真正影响性能的往往不是算法本身，而是内存访问模式：LSD 天然随机读（arr[i] 取 digit）、顺序写（output），不如快排局部性好。数据量小于 10⁴ 时，std::sort 通常更快。
