C++ 基数排序的实现实例代码

前言基数排序radix sort是一种非比较排序它不比较元素的大小而是按「位」逐轮分桶从最低位到最高位依次处理最终得到整体有序。对固定宽度的整数它的复杂度是 O(d(nb))d 是位数、b 是基数与 n log n 的比较排序走了完全不同的路线。常见的误解有三个。第一以为基数排序一定比std::sort快——它需要额外空间、需要多轮遍历只有在键的位数固定且数据量较大时才可能占优具体差异必须自行测量不能想当然。第二以为基数排序可以随意选择分桶方式——每一轮的分桶必须是稳定的否则高位排好后低位顺序会被打乱。第三以为它天然支持负数——按无符号位模式排序会把负数排到正数后面需要先做符号位变换。本文用基数 256每次处理一个字节实现 32 位无符号整数的排序再扩展到有符号整数最后讨论复杂度和适用边界。所有代码以 C17 为准。一、算法思想以十进制为例要排序[170, 45, 75, 90, 802, 24, 2, 66]按个位分桶收集后得到[170, 90, 802, 2, 24, 45, 75, 66]按十位分桶收集后得到[802, 2, 24, 45, 66, 75, 90, 170]按百位分桶收集后得到[2, 24, 45, 66, 75, 90, 170, 802]。每一轮都建立在前一轮的结果之上所以每一轮的分桶必须稳定相同「当前位」的元素必须保持上一轮结束时的相对顺序。这一点是基数排序正确性的基石。对二进制数据把基数取成 256 意味着每轮看 8 位32 位整数只需 4 轮。基数取 2 的幂有个额外好处取某一位段可以用移位加掩码不需要除法或取模。二、用计数排序完成一轮分桶每一轮分桶本质上是一次计数排序counting sort统计每个桶有多少元素算出每个桶的起始下标再按原顺序把元素放进对应位置。因为是按原顺序扫描、按顺序放置稳定性自然成立。// 适用于 C17#include array#include cstddef#include cstdint#include vectorvoid radixSort(std::vectorstd::uint32_t a) {constexpr int kBits 8;constexpr std::uint32_t kMask 0xFFu;constexpr int kPasses 32 / kBits; // 4 轮std::vectorstd::uint32_t buffer(a.size());for (int pass 0; pass kPasses; pass) {const int shift pass * kBits;std::arraystd::size_t, 256 count{};// 1. 统计每个桶的元素个数for (std::uint32_t v : a) {count[(v shift) kMask];}// 2. 前缀和count[i] 变成第 i 个桶的起始下标std::size_t total 0;for (std::size_t c : count) {const std::size_t old c;c total;total old;}// 3. 按原顺序放入缓冲保证稳定for (std::uint32_t v : a) {buffer[count[(v shift) kMask]] v;}a.swap(buffer);}}几个实现细节count用std::size_t而不是int避免元素个数超过INT_MAX时的溢出。前缀和循环里先把旧值存下来再覆盖因为c既要做累加源又要写入新值。写成total c; c total;就错了——那样c会变成「累计到当前桶的末尾」而不是「起始」。第三步的循环里count[...]是后置自增先取当前位置写入再把该桶的写指针后移。a.swap(buffer)之后buffer持有的是上一轮的旧数据下一轮直接覆盖不需要清零。三、负数与符号位std::uint32_t的排序解决了无符号情形。有符号整数不能直接按位模式排——负数的最高位是 1按无符号比较会被当成很大的数全部排到正数后面。标准的处理办法是翻转符号位把每个数异或0x80000000负数的高位变成 0、非负数的高位变成 1映射后的无符号顺序就与原来的有符号顺序一致。排完再翻回来。// 适用于 C17#include cstddef#include cstdint#include vector// 此处沿用上一节定义的无符号版本 radixSortvoid radixSortSigned(std::vectorstd::int32_t a) {std::vectorstd::uint32_t mapped(a.size());for (std::size_t i 0; i a.size(); i) {mapped[i] static_caststd::uint32_t(a[i]) ^ 0x80000000u;}radixSort(mapped); // 按无符号排序for (std::size_t i 0; i a.size(); i) {a[i] static_caststd::int32_t(mapped[i] ^ 0x80000000u);}}static_caststd::uint32_t(a[i])对负数做的是模 2³² 的转换标准明确规定结果不依赖实现。反向转换static_caststd::int32_t在 C20 之前是实现定义行为implementation-definedC20 起有符号整数被规定为补码表示该转换的结果被明确定义。在只支持补码的平台上这段代码的行为与预期一致如果要写完全不依赖实现定义的代码可以用std::memcpy按位复制或使用 C20 的std::bit_cast。另一种做法是给所有元素加上一个偏移量让最小值变成 0排序后再减回去。但这要求事先求出最小值且偏移后的值不能溢出处理起来比翻转符号位麻烦。四、复杂度与适用边界设元素个数为 n基数为 b这里是 256轮数为 d这里是 4指标基数排序std::sort时间复杂度O(d(n b))平均 O(n log n)额外空间O(n b)O(log n) 栈空间是否稳定是LSD 实现否std::stable_sort才稳定是否比较元素否是对键类型的要求能按位拆分支持严格弱序比较基数排序的优势来自「不做比较」当 n 远大于 b^d 时它避免了 log n 次比较。但它也有明确的代价需要一份与原数组等大的缓冲区且对每个元素都要完整扫过 d 轮。元素很少、或者 d 很大比如 64 位整数需要 8 轮时常数开销可能超过收益。实际工程中是否使用基数排序应当基于测量用std::chrono::steady_clock记录排序前后的时间戳多次运行取中位数并注意缓存状态、数据分布、编译器优化选项对结果的影响。不要凭「非比较排序一定更快」的印象做决定。还有一个前提容易被忽略基数排序要求键可以按固定宽度拆位。字符串、浮点数、自定义结构体都需要额外处理。浮点数可以先把位模式映射成「可按无符号比较」的形式正数翻转符号位负数整体取反但这一步的细节很容易写错非必要不建议自己实现。五、完整示例// 适用于 C17#include array#include cstddef#include cstdint#include iostream#include vectorvoid radixSort(std::vectorstd::uint32_t a) {constexpr int kBits 8;constexpr std::uint32_t kMask 0xFFu;constexpr int kPasses 32 / kBits;std::vectorstd::uint32_t buffer(a.size());for (int pass 0; pass kPasses; pass) {const int shift pass * kBits;std::arraystd::size_t, 256 count{};for (std::uint32_t v : a) count[(v shift) kMask];std::size_t total 0;for (std::size_t c : count) {const std::size_t old c;c total;total old;}for (std::uint32_t v : a) {buffer[count[(v shift) kMask]] v;}a.swap(buffer);}}int main() {std::vectorstd::uint32_t data{170u, 45u, 75u, 90u, 802u, 24u, 2u, 66u};radixSort(data);for (std::uint32_t v : data) {std::cout v ;}std::cout \n;return 0;}按标准语义输出应为升序的2 24 45 66 75 90 170 802。注意buffer的大小与输入相同如果输入为空buffer也是空的四轮循环体内不会写入任何元素swap也是空操作行为正确。常见坑点1. 分桶不稳定❌ 每轮把元素按桶分组时使用「头插」或反向扫描。 ✅ 严格按原数组顺序扫描并按计数得到的起始位置顺序写入。2. 前缀和写错❌total c; c total;桶的起始位置变成结束位置。 ✅ 先保存old c再c total; total old;。3. 从最高位开始排MSD却按 LSD 的方式收集❌ 高位先排、低位后收最终顺序完全错乱。 ✅ LSD 基数排序必须从最低位开始MSD 需要递归分桶是另一种实现。4. 有符号数直接按位排序❌ 把int直接转uint32_t排序负数全部跑到末尾。 ✅ 先异或0x80000000翻转符号位排完再翻回来。5. 复用缓冲区时忘记它保存的是旧数据❌ 以为swap后buffer已清空直接在其上累加。 ✅ 每轮都是完整覆盖写入不依赖缓冲区原有内容。6. 用int做计数数组❌ 元素个数超过INT_MAX时计数溢出。 ✅ 计数与下标统一用std::size_t。7. 轮数算错❌ 32 位整数按 8 位分桶只跑 3 轮高 8 位没参与排序。 ✅kPasses 32 / kBits确保覆盖全部位。8. 对浮点数直接套用整数版本❌ 把float的位模式当无符号整数排序负数顺序错误。 ✅ 浮点需要专门的位模式映射不确定时改用比较排序。总结要点说明排序方向LSD从最低位到最高位每轮算法稳定计数排序复杂度O(d(n b)) 时间O(n b) 空间稳定性稳定前提是每轮分桶稳定负数处理翻转符号位或加偏移适用场景固定宽度整数、数据量大、可接受额外内存基数排序的核心只有两句话按位分轮每轮稳定。把计数排序这一轮写对剩下就是循环。真正决定它是否值得用的不是理论复杂度而是数据规模、键宽度和内存预算——这三点应当用测量说话而不是凭感觉。