高性能实现)
1. 浮点数排序为什么不能直接套用整数基数排序
很多人第一次听到"浮点数-基数排序"这个组合，第一反应是：基数排序不是给整数用的吗？浮点数有小数位、有指数、有正负号，怎么可能直接按位拆？这个疑问非常合理，因为浮点数的二进制表示和整数完全不是一回事。
IEEE 754 标准下的单精度浮点数由三部分组成：1 位符号位、8 位指数位、23 位尾数位。双精度则是 1 位符号位、11 位指数位、52 位尾数位。如果直接把浮点数的二进制位当成整数来比较，会得到一个反直觉的结果：正数的二进制位模式确实随数值增大而增大，但负数的二进制位模式却是随数值增大而减小的。也就是说，负数的位模式越大，实际数值反而越小。
这就是浮点数基数排序的第一个核心障碍：符号位导致正负数的位模式顺序相反。解决思路其实很直接——把所有浮点数的位模式映射成一个单调递增的无符号整数序列，然后对这个整数序列做基数排序，最后再映射回来。这个映射过程不需要排序，只需要对每个元素做常数时间的位操作。
具体来说，对于 32 位浮点数，映射规则是：如果符号位为 1（负数），则对整个 32 位取反；如果符号位为 0（正数），则只翻转符号位。这样处理后，所有浮点数就变成了一个单调递增的 32 位无符号整数序列。排序完成后，反向操作即可还原。
这个技巧在业内被称为"浮点数到可排序整数的双射变换"，它不改变元素之间的相对顺序，只是把比较关系从浮点语义搬到了整数语义上。理解这一点，是掌握浮点数基数排序的关键前提。
注意：这个变换只适用于 IEEE 754 格式的浮点数。如果你的数据是定点数或者自定义浮点格式，映射规则需要重新推导。
2. 从位模式到桶：基数排序的完整链路拆解
2.1 为什么选择基数排序而不是比较排序
在讨论具体实现之前，有必要先回答一个问题：既然浮点数可以用比较排序（如快速排序、归并排序）处理，为什么还要费劲做基数排序？答案在于时间复杂度。比较排序的下界是 O(n log n)，而基数排序在特定条件下可以达到 O(n)。当数据量达到千万级甚至亿级，且数据分布相对均匀时，基数排序的线性优势会非常明显。
另一个常被忽略的优势是稳定性。基数排序天然稳定，这对于多关键字排序场景非常重要。比如先按时间戳排序，再按用户 ID 排序，如果第二轮排序是稳定的，那么同一用户内的记录仍然保持时间戳有序。比较排序要做到这一点，需要额外携带原始索引，增加了内存开销。
当然，基数排序也有代价：它需要额外的桶空间，且对数据范围敏感。如果浮点数的指数分布极其分散，桶的数量会膨胀。但在实际工程中，大多数浮点数据（如传感器读数、金融价格、科学计算结果）的指数范围是可控的，这正是基数排序发挥优势的场景。
2.2 桶的划分策略：按字节还是按位
基数排序的桶划分有两种常见策略：按位（1 位一桶）和按字节（8 位一桶）。按位划分需要 32 轮（单精度）或 64 轮（双精度），每轮只有两个桶，缓存友好但轮次太多。按字节划分只需要 4 轮或 8 轮，每轮 256 个桶，轮次少但桶数组较大。
实测下来，按字节划分在大多数现代 CPU 上表现更好。原因在于：256 个桶的计数数组只占 1KB（用 uint32 计数），完全可以放进 L1 缓存。而 4 轮遍历的内存访问模式也比 32 轮更连续。对于双精度浮点数，8 轮 256 桶的方案同样优于 64 轮 2 桶方案。
不过，如果你的数据量很小（比如几千个元素），按位划分的常数开销更低，反而可能更快。选择哪种策略，需要根据数据规模和硬件特性做权衡。我通常的做法是：数据量超过 10 万时用按字节，否则用按位。
2.3 计数与前缀和：基数排序的核心循环
基数排序的每一轮包含三个步骤：计数、前缀和、重排。计数阶段遍历所有元素，统计每个桶中的元素个数。前缀和阶段把计数数组转换成每个桶的起始位置。重排阶段根据起始位置把元素放入临时数组。
这三个步骤中，前缀和是最容易被写错的地方。正确的做法是：对于 i 从 1 到 255，count[i] += count[i-1]。这样 count[i] 就变成了第 i 个桶的结束位置（或者起始位置，取决于重排方向）。如果重排时从后往前遍历，count[i] 应该表示结束位置；如果从前往后遍历，count[i] 应该表示起始位置。
我见过不少实现因为前缀和方向搞反，导致排序结果不稳定甚至完全错误。一个简单的验证方法是：排序后检查相邻元素是否满足非递减关系，同时检查相同元素的相对顺序是否保持不变。
// 单轮基数排序的计数与前缀和示例（按字节） void counting_sort_pass(uint32_t *src, uint32_t *dst, int n, int shift) { uint32_t count[256] = {0}; for (int i = 0; i < n; i++) { count[(src[i] >> shift) & 0xFF]++; } // 前缀和：count[i] 表示第 i 个桶的起始位置 uint32_t sum = 0; for (int i = 0; i < 256; i++) { uint32_t tmp = count[i]; count[i] = sum; sum += tmp; } // 重排：从前往后遍历，保证稳定性 for (int i = 0; i < n; i++) { uint32_t byte = (src[i] >> shift) & 0xFF; dst[count[byte]++] = src[i]; } }这段代码的关键在于：前缀和计算后，count[i] 表示第 i 个桶的起始写入位置。重排时每写入一个元素，count[byte] 自增，指向下一个空位。由于是从前往后遍历源数组，相同桶内的元素保持了原始相对顺序，稳定性得以保证。
3. 浮点数映射的边界情况与精度陷阱
3.1 负零、无穷与 NaN 的处理
浮点数有一些特殊值：负零（-0.0）、正无穷（+Inf）、负无穷（-Inf）、NaN（非数）。这些值在映射到可排序整数时，需要特别小心。
负零的位模式是 0x80000000，正零是 0x00000000。按照前面的映射规则，负零会被映射成 0x7FFFFFFF，正零会被映射成 0x80000000。这意味着负零排在正零前面。但在 IEEE 754 语义中，负零和正零是相等的。如果你的排序结果要求负零和正零相邻且顺序无关紧要，这个映射是可以接受的。但如果要求严格相等，就需要在映射前把负零统一转成正零。
无穷大的处理相对简单：正无穷的位模式是 0x7F800000，映射后是 0xFF800000；负无穷的位模式是 0xFF800000，映射后是 0x007FFFFF。它们会分别排在最大正数和最小负数的位置，符合数学语义。
NaN 是最麻烦的。NaN 的位模式有多个，且 NaN 与任何值比较都不相等。在排序场景中，通常的做法是把所有 NaN 统一映射到一个固定值（比如最大值或最小值），或者直接在排序前过滤掉。如果业务逻辑允许，我建议在排序前就把 NaN 替换成一个哨兵值，避免排序过程中出现不可预期的结果。
3.2 双精度浮点数的映射差异
双精度浮点数的映射逻辑和单精度类似，但操作的是 64 位整数。符号位是第 63 位，指数位是第 62 到 52 位，尾数位是第 51 到 0 位。映射规则同样是：负数取反整个 64 位，正数只翻转符号位。
需要注意的是，双精度浮点数的基数排序需要 8 轮（按字节），每轮 256 个桶。计数数组用 uint64 还是 uint32 取决于数据量。如果数据量超过 40 亿，必须用 uint64 计数，否则会溢出。对于大多数工程场景，uint32 足够。
另一个差异是内存对齐。64 位整数在 32 位系统上可能需要特殊处理，但在 64 位系统上自然对齐。如果你在做跨平台实现，建议用memcpy而不是指针强转来读取位模式，避免对齐问题。
3.3 精度丢失的常见误区
有人担心：把浮点数映射成整数再排序，会不会丢失精度？答案是不会。映射过程是双射的，每个浮点数的位模式唯一对应一个整数，排序后再映射回来，位模式完全不变。精度丢失只可能发生在映射函数写错的情况下，比如错误地截断了某些位。
真正需要注意的是排序稳定性对浮点数相等判断的影响。两个浮点数可能在数学上相等，但位模式不同（比如 +0.0 和 -0.0）。如果你的业务逻辑认为它们相等，那么排序后它们的相对顺序应该保持不变。但由于映射后它们的整数值不同，基数排序会把它们当成不同的元素处理。这种情况下，需要在映射前做归一化处理。
4. 性能实测：基数排序与快速排序的对比
4.1 测试环境与数据构造
为了给出有参考价值的性能数据，我构造了三组测试数据：第一组是均匀分布的随机浮点数，范围在 -1000 到 1000 之间；第二组是指数分布的浮点数，模拟科学计算中的数量级差异；第三组是包含大量重复值的浮点数，模拟传感器读数场景。每组数据量从 10 万到 1000 万不等。
测试平台是一台普通的开发机，CPU 为 8 核，内存 32GB，编译器优化级别 -O2。对比对象是 C 标准库的qsort和一个手写的三路快速排序。基数排序采用按字节划分，4 轮 256 桶。
4.2 实测数据与结果分析
| 数据量 | 数据类型 | 快速排序耗时 | 基数排序耗时 | 加速比 |
|---|---|---|---|---|
| 10 万 | 均匀分布 | 12 ms | 8 ms | 1.5x |
| 100 万 | 均匀分布 | 150 ms | 65 ms | 2.3x |
| 1000 万 | 均匀分布 | 1800 ms | 620 ms | 2.9x |
| 100 万 | 指数分布 | 145 ms | 70 ms | 2.1x |
| 100 万 | 大量重复 | 95 ms | 55 ms | 1.7x |
从数据可以看出，基数排序在数据量越大时优势越明显。这是因为快速排序的 O(n log n) 中 log n 随数据量增长，而基数排序的 O(n) 是线性的。在 1000 万数据量下，基数排序比快速排序快了近 3 倍。
指数分布的数据下，基数排序的优势略有下降，因为指数分布导致高位字节的桶分布不均匀，缓存局部性变差。但即便如此，仍然有 2 倍以上的加速。
大量重复值的数据下，快速排序的三路划分已经做了优化，所以差距缩小到 1.7 倍。但如果用普通的两路快速排序，差距会更大。
4.3 内存开销与缓存友好性
基数排序需要额外的临时数组，大小和原数组相同。对于 1000 万个双精度浮点数，原数组占 80MB，临时数组再占 80MB，总共 160MB。这个内存开销在大多数服务器上可以接受，但在嵌入式设备上可能是个问题。
缓存友好性方面，基数排序的每一轮都是顺序遍历，预取器可以很好地工作。而快速排序的划分过程是跳跃式的，缓存命中率较低。这也是基数排序在大数据量下更快的原因之一。
一个优化技巧是：如果数据量小于 L2 缓存容量，可以在临时数组和原数组之间交替进行每一轮，避免额外的内存拷贝。如果数据量大于缓存容量，则每轮都需要完整的内存读写，此时内存带宽成为瓶颈。
5. 工程落地中的坑与优化技巧
5.1 桶计数溢出的隐蔽问题
计数数组用 uint32 时，如果某个桶的元素个数超过 40 亿，就会溢出。这在单机场景下几乎不可能，但在分布式排序的合并阶段，如果多个节点的数据汇聚到一个桶，就可能触发。我建议在计数阶段加一个断言：如果某个桶的计数达到 uint32 最大值，就切换到 uint64 计数或者报错。
另一个隐蔽问题是前缀和溢出。即使每个桶的计数不溢出，前缀和累加后也可能超过 uint32 范围。比如 256 个桶，每个桶 2000 万，总和就是 51 亿，超过 uint32 最大值。这种情况下，前缀和数组必须用 uint64。
5.2 负零与 NaN 的业务处理
在实际业务中，负零和 NaN 的处理策略取决于具体场景。金融场景通常不允许 NaN，遇到就报错。科学计算场景可能允许 NaN，但需要把它们排在最后。传感器场景可能把 NaN 视为无效读数，直接过滤。
我的建议是：在排序前增加一个预处理步骤，根据业务规则把特殊值替换成哨兵值。这样排序逻辑保持纯粹，特殊值的处理逻辑独立可测。预处理的时间复杂度是 O(n)，相对于排序的 O(n) 可以忽略。
5.3 并行化与分块排序
基数排序的每一轮内部是数据并行的，但轮与轮之间是串行的。可以利用多线程加速每一轮的计数和重排。计数阶段可以用原子操作或者每个线程独立计数再合并。重排阶段可以用前缀和划分每个线程的写入区间，避免竞争。
分块排序是另一种思路：把大数组切成多个块，每个块独立排序，然后归并。但归并的复杂度是 O(n log k)，k 是块数。如果块数太多，归并开销会抵消基数排序的优势。我通常把块大小设为 L2 缓存容量的 1/4，这样每块排序时数据都在缓存内，速度最快。
5.4 与其他排序算法的混合策略
纯基数排序并不总是最优。如果数据量很小（比如小于 1000），插入排序可能更快。如果数据已经基本有序，快速排序的适应性更好。一个实用的混合策略是：先用快速排序做粗排，当子数组大小降到阈值以下时切换到插入排序，同时如果检测到数据范围适合基数排序，就切换到基数排序。
这种混合策略在标准库中很常见。比如某些实现会在快速排序的递归深度超过阈值时切换到堆排序，避免最坏情况。基数排序可以作为快速排序的补充，在数据分布均匀且数据量大时接管。
6. 从位操作到业务语义的完整代码路径
6.1 映射与反映射的封装
把映射逻辑封装成两个内联函数，既保证性能又提高可读性。对于单精度浮点数：
static inline uint32_t float_to_sortable(float f) { uint32_t bits; memcpy(&bits, &f, sizeof(bits)); return (bits & 0x80000000) ? ~bits : (bits | 0x80000000); } static inline float sortable_to_float(uint32_t u) { uint32_t bits = (u & 0x80000000) ? (u & 0x7FFFFFFF) : ~u; float f; memcpy(&f, &bits, sizeof(f)); return f; }这两个函数是互逆的，可以验证：对任意浮点数 f，sortable_to_float(float_to_sortable(f)) == f。注意这里用了memcpy而不是指针强转，避免严格别名规则的问题。
6.2 完整排序函数的组装
完整的基数排序函数需要处理：映射、多轮计数排序、反映射。每一轮在 src 和 dst 之间交替，最后根据轮数的奇偶决定是否需要拷贝回原数组。
void radix_sort_float(float *arr, int n) { uint32_t *src = malloc(n * sizeof(uint32_t)); uint32_t *dst = malloc(n * sizeof(uint32_t)); for (int i = 0; i < n; i++) { src[i] = float_to_sortable(arr[i]); } for (int shift = 0; shift < 32; shift += 8) { counting_sort_pass(src, dst, n, shift); uint32_t *tmp = src; src = dst; dst = tmp; } // 4 轮后 src 指向最终结果 for (int i = 0; i < n; i++) { arr[i] = sortable_to_float(src[i]); } free(src); free(dst); }这段代码的轮数是 4（32 位除以 8），每轮交换 src 和 dst。4 是偶数，所以最终结果在 src 中。如果是奇数轮，结果会在 dst 中，需要额外拷贝。
6.3 测试用例与验证方法
验证排序正确性，不能只看最终数组是否有序，还要检查映射的单调性。我通常写三个测试：第一，随机生成 100 万个浮点数，排序后检查非递减；第二，生成包含负零、正零、无穷、NaN 的边界数组，检查特殊值的位置；第三，生成大量重复值，检查排序稳定性。
稳定性测试的方法是：给每个元素附加一个原始索引，排序后检查相同值的元素索引是否递增。如果递增，说明稳定；否则不稳定。这个测试能发现前缀和方向错误等隐蔽 bug。
7. 什么时候不该用浮点数基数排序
7.1 数据量小且分布未知的场景
如果数据量只有几千个，基数排序的常数开销（分配桶、多轮遍历）可能比快速排序还大。而且如果数据分布未知，桶的利用率可能很低，浪费内存和缓存。这种情况下，直接用标准库的排序函数更省心。
7.2 内存受限的嵌入式环境
基数排序需要两倍于原数组的内存。在内存只有几十 KB 的嵌入式设备上，这个开销可能无法承受。此时可以考虑原地基数排序的变体，但实现复杂度高，且性能提升有限。更实际的选择是使用原地比较排序。
7.3 需要自定义比较逻辑的场景
基数排序依赖于位模式的单调映射，只能处理"按数值大小排序"这一种逻辑。如果你需要按绝对值排序、按某种业务规则排序，或者比较逻辑涉及多个字段，基数排序就不适用了。这种情况下，比较排序的灵活性是无可替代的。
我在实际项目中遇到过这样的需求：浮点数需要按"距离某个参考值的远近"排序。这种排序无法用位模式映射表达，只能老老实实用比较排序。所以，选择排序算法时，先确认比较逻辑是否能用位模式表达，再考虑性能优化。
7.4 数据频繁插入删除的动态场景
基数排序适合静态数据的批量排序。如果数据频繁插入删除，每次都要重新排序，开销太大。这种场景应该用平衡树或者跳表，支持 O(log n) 的插入和删除，同时保持有序。基数排序的优势在于一次性处理大量静态数据，而不是动态维护有序性。
8. 个人实操中的几点体会
浮点数基数排序这个技术点，我最早是在处理大规模传感器数据时接触到的。当时数据量是每天 5000 万条，每条包含多个浮点字段，需要按时间戳和数值分别排序。用快速排序跑一次要十几秒，换成基数排序后降到三秒以内，效果非常明显。
踩过的坑主要有两个：一是负零的处理，早期版本没有归一化，导致排序结果中 -0.0 和 +0.0 交替出现，下游的聚合逻辑出了偏差；二是计数数组的溢出，在一次数据量突增的场景中，uint32 计数溢出导致排序结果错乱，排查了很久才定位到。
我的建议是：如果你的数据量在百万级以上，且浮点数的指数范围可控，基数排序值得一试。但一定要做好边界测试，特别是特殊值和溢出场景。另外，映射函数的正确性可以用随机测试验证：生成随机浮点数，检查映射后的整数顺序是否和浮点数比较顺序一致。这个测试跑一百万次，基本能覆盖所有边界情况。
最后分享一个小技巧：如果只需要排序，不需要保留原始数组，可以在映射后直接在原数组上操作，省去一次内存分配。具体做法是把浮点数组的指针强转成 uint32 指针（注意对齐），然后原地映射。这样内存开销减半，但要注意类型双关的合规性问题，用memcpy逐元素处理更安全。
