C++如何实现基数排序(Radix Sort)
作者:WarmHope
时间:2026-07-11
浏览:0
基数排序要求数据能拆分为固定位数数字位,常用LSD稳定迭代实现。通过字节作为基数、计数排序子过程处理整数。负数可通过异或0x80000000转为无符号偏移保持顺序。每轮需确保稳定性,避免越界访问。
基数排序并非适用于所有数据类型,它对数据格式有明确要求:待排序元素必须能被拆解为“有限位数的、固定范围的数字位”。最稳妥的选择是非负整数(`unsigned int`),当然,如果手动处理符号位,有符号整数也能用。浮点数需要先转为IEEE 754整数表示再排序——不过对初学者来说,这条路不太推荐。字符串也能用,但得统一长度或按字典序逐字符处理,这时通常叫做“MSD/LSD字符串排序”,实现逻辑和整数版不太一样。
(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起来非常耗时。
本文内容来源于互联网,如有侵权请联系删除。

作者最新文章
思源笔记
2026-09-16 17:42
在线PDF转TXT操作步骤与乱码排查指南
2026-09-04 13:02
PDF加水印后如何检查显示效果?在线工具操作步骤与避坑指南
2026-09-03 13:02
Xshell保持连接不断开及会话文件本地存储路径详解
2026-09-03 06:02
两个PDF怎么合并成一个?在线合并后怎么检查顺序?
2026-09-02 20:00
热门文章
更多
精品专题
更多
Mac软件
更多
WINDOWS
更多

































