当前位置:

首页 > 编程开发 > C++如何实现基数排序(Radix Sort)

C++如何实现基数排序(Radix Sort)

基数排序要求数据能拆分为固定位数数字位,常用LSD稳定迭代实现。通过字节作为基数、计数排序子过程处理整数。负数可通过异或0x80000000转为无符号偏移保持顺序。每轮需确保稳定性,避免越界访问。

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

C++如何实现基数排序(Radix Sort)

### 为什么实践中通常选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起来非常耗时。
本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
作者最新文章
编程开发 C++
相关文章 更多
C++动态数组初始化怎么写?常用语句与代码示例
C++动态数组初始化怎么写?常用语句与代码示例

深入解析C++中动态数组的初始化机制,涵盖new操作符的不同用法、基本类型与类对象的初始化差异,以及为何在现代C++开发中应优先使用std::vector。

C++类构造与析构函数详解
C++类构造与析构函数详解

C++类构造与析构函数详解 C++这门语言,可以说是从C语言这棵大树上衍生出的高级果实,如今的应用普及度有目共睹。作为一种静态类型的通用编程语言,它厉害的地方在于融合了多种编程哲学——无论是传统的面向过程,还是主流的面向对象,乃至数据抽象、泛型编程这些高级概念,它都能很好地支持。正因为这份卓越的扩展

C++中std::upper
C++中std::upper

C++中std::upper_bound用法解析 在C++标准模板库(STL)的算法工具箱里,upper_bound() 绝对算得上是一把精准的“探针”。它的核心任务很明确:在一个已经排好序的区间 [first, last) 内,帮你快速定位到第一个**严格大于**指定值 value 的那个元素。这

C++常对象与成员解析
C++常对象与成员解析

C++中“常”概念全景解析:从对象、成员到指针与引用 在C++的世界里,“常量性”是一个强大的保障机制。它不仅仅是一个const关键字那么简单,而是构建健壮、安全程序的重要基石。今天,我们就来系统梳理一下围绕“常”的一系列概念:常成员、常对象、常指针与常引用。理解它们,是写出高质量C++代码的关键一

c++如何将结构体写入SQLite数据库_对象关系映射方案【进阶】
c++如何将结构体写入SQLite数据库_对象关系映射方案【进阶】

直接用SQLiteCAPI绑定结构体需要手动处理字段展平与顺序对齐,ORM库虽省代码但存在隐式行为风险。小项目建议原生绑定,中大型项目可搭配编译期校验使用轻量ORM。绑定std::string需传指针与长度,注意生命周期;浮点字段比较需设误差范围。

什么是编程,学习编程的意义是?
什么是编程,学习编程的意义是?

编程是编写程序指令,让设备按意图运行,常用Python、C等语言或Scratch图形化编程。学习编程能跟上科技时代,锻炼自学与解决问题能力,提升逻辑思维,代表行动力,推动事物前进。各司其职,编程者尽本分。

编程是门艺术_是编程艺术吗?
编程是门艺术_是编程艺术吗?

编程被争论是否为艺术。从定义看,编程是技能表达,但并非所有编程都是应用开发。写代码如音乐、文章,有独特风格。好代码需耐心与逻辑能力。编程是艺术,但应用开发不等同于编程艺术。

【编程的感受】
【编程的感受】

很多人提起编程,总觉得这是一门“不起眼”的学问——不就是写写代码嘛,能有多深?但真走进去了才会发现,编程里头的门道,远比表面看上去要丰富得多。 学习编程的过程中,最容易卡住的往往是那些基础语法。就拿那个常见的 for 循环来说吧,刚开始时怎么都绕不过弯来:为什么这么写能循环?循环条件到底怎么控制?一

对于懂得编程的人来说,编程对你来说有什么乐趣?编程大概是什么感觉?
对于懂得编程的人来说,编程对你来说有什么乐趣?编程大概是什么感觉?

解决编程问题后的痛快、完成作品的成就感、获取知识的满足感,以及用代码实现简化生活的惊喜与踏实,这些是编程独有的乐趣,只有真正写代码的人才能体会其中的酸甜苦辣、惊喜与满足,令人回味无穷。

趣味编程:少儿编程思维的启蒙之旅
趣味编程:少儿编程思维的启蒙之旅

Scratch图形化编程以拖拽积木块方式启蒙少儿编程思维,无需记忆代码语法。通过素材库、即时反馈和社区协作,帮助孩子在创作中理解顺序执行、条件判断等核心概念,锻炼逻辑、创造力和问题解决能力。

查看更多
精品专题 更多
装机必备
装机必备

正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

Windows
Windows

正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

PDF教程
PDF教程

正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

Mac软件 更多
Postman macOS版
Postman macOS版
Mac

Postman是一套面向API全生命周期的开发与测试平台,可在Mac上发送和调试多种协议请求,管理集合、环境及认证信息,并完成脚本测试、模拟服务、监控、文档发布和团队协作。它适合开发、测试及运维人员使用,提供个人免费方案。

Docker Desktop macOS版
Docker Desktop macOS版
Mac

Docker Desktop 是 Docker 官方为 Mac 提供的容器开发环境,集成 Docker Engine、命令行工具、Compose、Build、Kubernetes 与图形化管理界面。

Android Studio macOS版
Android Studio macOS版
Mac

Android Studio 是 Google 面向安卓应用开发提供的官方集成开发环境,基于 IntelliJ IDEA 构建。它整合智能代码编辑、Gradle 构建、界面预览、设备模拟、性能分析、调试测试及 APK 分析等工具。

WINDOWS 更多
Postman Windows版
Postman Windows版
Windows

Postman 是面向 API 全生命周期的开发与协作平台。Windows 桌面版可用于构建和发送 HTTP、GraphQL、gRPC、WebSocket、MQTT 等请求,并提供环境变量、集合、脚本测试、模拟服务、监控、文档及团队工作区等

Docker Desktop Windows版
Docker Desktop Windows版
Windows

Docker Desktop 为 Windows 开发者提供集成式容器环境,内置 Docker Engine、命令行工具、Compose、Build 与 Kubernetes 等组件,可在本机完成镜像构建、容器运行、日志查看和资源管理。

Android Studio Windows版
Android Studio Windows版
Windows

Android Studio 是 Google 面向 Android 应用开发提供的官方集成开发环境,以 IntelliJ IDEA 为基础,集成智能代码编辑、Gradle 构建、设备模拟、界面预览、调试测试及性能分析工具,