C++如何实现基数排序（Radix Sort）-C++-PHP中文网

基数排序最适合非负整数，也可通过位重解释和偏移处理有符号整数；浮点数需转ieee 754整数表示（不推荐），字符串需统一长度或逐字符处理；实际优先选用lsd方式，因其稳定、迭代、缓存友好。

c++如何实现基数排序（radix sort）

基数排序适合什么数据类型

基数排序不能直接用于任意 int 或 float，它要求待排序元素能被拆解为「有限位数的、固定范围的数字位」。最稳妥的是非负整数（unsigned int），或者你手动处理符号位的有符号整数。浮点数需转为 IEEE 754 整数表示再排序（不推荐初学尝试）。字符串也可以用，但得统一长度或按字典序逐字符处理——这时更常叫「MSD/LSD 字符串排序」，和整数版实现逻辑不同。

为什么通常用 LSD（最低位优先）而不是 MSD

LSD 更容易写成稳定、迭代、非递归的形式，空间可控且缓存友好。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，也就是把最高位（符号位）当作大小比较的第一位。

// 示例：将 int 转为偏移后的 uint32_t，用于 LSD 排序
auto key = static_cast<uint32_t>(x) ^ 0x80000000;
</uint32_t>

这样，所有负数都映射到 [0, 0x7FFFFFFF]，正数映射到 [0x80000000, 0xFFFFFFFF]，自然保持数值序。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

计数排序子过程的关键细节

基数排序里每轮的计数排序不是独立算法，而是「针对当前 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 很费时间。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！