C++如何实现基数排序（Radix Sort）

基数排序并非适用于所有数据类型，它对数据格式有明确要求：待排序元素必须能被拆解为“有限位数的、固定范围的数字位”。最稳妥的选择是非负整数（`unsigned int`），当然，如果手动处理符号位，有符号整数也能用。浮点数需要先转为IEEE 754整数表示再排序——不过对初学者来说，这条路不太推荐。字符串也能用，但得统一长度或按字典序逐字符处理，这时通常叫做“MSD/LSD字符串排序”，实现逻辑和整数版不太一样。

### 为什么实践中通常选LSD，而不是MSD？ LSD更容易写成稳定、迭代、非递归的形式，空间可控，对CPU缓存也友好。MSD虽然理论上对长键更高效，但涉及分桶递归、前缀判断、空桶跳过等细节，稍不留神就会退化甚至爆栈。在实际工程中，除非键长差异极大（比如混合了短ID和长哈希），否则默认选LSD。 - LSD每轮只看1个digit（比如0–9或0–255），用计数排序作为子过程。 - digit基数（`base`）选10、16、256都可以；选256（即1字节）时，32位整数只需4轮，CPU缓存命中率很高。 - 必须保证每轮计数排序是稳定的——否则高位排序会打乱低位已排好的顺序，排序结果就乱了。 ### 怎么处理负数，避免排序错乱？ 直接对`int`按字节取digit，会把符号位当成普通位处理，结果就是-1（0xFF...FF）会排在最大正数后面。正确的做法是将`int`视为32位无符号整数重新解释（bit-reinterpret），再做一个偏移：让最小的`int`（即`INT_MIN`）对应0。这等价于异或`0x80000000`，也就是把最高位（符号位）当作大小比较的第一位。 ```cpp // 示例：将 int 转为偏移后的 uint32_t，用于 LSD 排序 auto key = static_cast(x) ^ 0x80000000; ``` 这样，所有负数都映射到`[0, 0x7FFFFFFF]`，正数映射到`[0x80000000, 0xFFFFFFFF]`，数值顺序就自然保持了。 ### 计数排序子过程的关键细节 基数排序里每轮的计数排序不是独立的算法，而是“针对当前digit的频次统计 + 原地重排”。常见的错误是新开数组复制两次（输入→计数→输出），这既浪费内存，又破坏局部性。更优的做法是这样的： - 先统计每个digit出现的次数（`count[0..base-1]`）。 - 做前缀和，得到每个digit在输出数组中的起始位置。注意：LSD要从右往左扫描原数组，这样才能保证稳定性。 - 用临时缓冲区暂存本轮结果（避免覆盖原数组），然后拷回。 - 当`base = 256`时，`count`数组只有256个`int`，可以直接放在栈上，完全不需要`new`。 另外，digit提取要保持一致：对`key`（已经偏移过的uint32_t），第`i`轮（i=0是最低字节）取`(key >> (i * 8)) & 0xFF`。 真正难的不是把代码写通，而是要确认：符号位处理了没有？有没有越界访问`count`？每轮重排后，数据是否仍保持前一轮的相对顺序？这些地方一旦出错，排序结果就会似是而非，debug起来非常耗时。