高性能实现)
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 到 255count[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 ms8 ms1.5x100 万均匀分布150 ms65 ms2.3x1000 万均匀分布1800 ms620 ms2.9x100 万指数分布145 ms70 ms2.1x100 万大量重复95 ms55 ms1.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; }这两个函数是互逆的可以验证对任意浮点数 fsortable_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); }这段代码的轮数是 432 位除以 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逐元素处理更安全。
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 到 255count[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 ms8 ms1.5x100 万均匀分布150 ms65 ms2.3x1000 万均匀分布1800 ms620 ms2.9x100 万指数分布145 ms70 ms2.1x100 万大量重复95 ms55 ms1.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; }这两个函数是互逆的可以验证对任意浮点数 fsortable_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); }这段代码的轮数是 432 位除以 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逐元素处理更安全。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
