基数排序不直接用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 count(10) 看似合理，但在高频调用场景下，频繁分配/清零小数组会拖慢速度。实际工程中常见改进：

立即学习“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 通常更快。