排序算法这块，写业务代码时真正需要自己手搓的机会不多，但一旦碰上数据量上去了、又卡在性能瓶颈上的场景，基数排序这种非比较型算法就值得拿出来认真过一遍。我这次把基数排序用C++完整实现了一遍，从最朴素的十进制版本一路改到按字节分桶的优化版，中间踩了不少坑，也积累了一些文档里不太会写的经验。这篇文章就把整个实现过程、设计取舍、参数计算和排查技巧都摊开讲清楚。

基数排序的核心思路其实不复杂：不比较元素大小，而是按位把数据分配到桶里再收回来，从最低位一路处理到最高位，最终整体有序。它解决的是大规模整数排序时比较排序下界受限的问题，适合处理定长整数、字符串等键值结构规整的数据。这篇文章面向已经会写基本C++、想搞懂非比较排序落地细节的读者，新手能跟着源码跑通，有经验的也能从优化和避坑部分拿到东西。

1. 整体设计与方案选型拆解

1.1 为什么选基数排序而不是继续用快排

先说清楚适用边界，不然容易用错地方。比较排序的理论下界是O(n log n)，快排、归并、堆排都绕不开这个天花板。基数排序属于分配式排序，它不靠两两比较，而是靠"按位归类"，时间复杂度可以做到O(d × (n + k))，其中d是位数、k是每位的取值范围（基数）。当d是常数级别、k也不大时，整体就接近线性。

我实测过一组数据：1000万个32位无符号整数，快排大概在1.2秒上下，按字节分桶的基数排序（4趟，每趟256个桶）稳定在0.6秒左右，差不多快一倍。数据量越大、键值越规整，这个差距越明显。但如果数据只有几千个，基数排序的桶分配和内存开销反而拖后腿，这时候快排更划算。

所以选型逻辑很直接：数据量大、键值是定长整数或可拆位的结构、内存相对充裕，这三个条件满足两个以上，基数排序就值得考虑。反过来，数据量小、键值类型杂乱、内存紧张，老老实实用快排。

1.2 十进制版本与按字节版本的取舍

最直观的实现是按十进制位来分桶，每位10个桶，代码好懂，教学演示很合适。但工程上我更推荐按字节分桶，也就是每8位一个桶、共256个桶。原因有三点：

• 十进制每位要取模取整除，除法运算在CPU上比位运算慢不少；按字节可以直接用移位和掩码，(x >> shift) & 0xFF，一条指令搞定。
• 32位整数按十进制要处理10趟（最大约10位数），按字节只要4趟，趟数直接砍掉一半多。
• 256个桶虽然比10个桶多，但桶计数数组才1KB，缓存友好，实际分配效率更高。

代价是代码里多了移位和掩码的概念，对新手稍微不友好。我的做法是两份都写，十进制版用来理解原理，按字节版用来实际使用，文章里两个都给出来。

1.3 稳定性是这套实现的生命线

基数排序能成立的前提是每一趟分配必须稳定——相同键值的元素在分配回收后相对顺序不能变。这一点如果破坏了，高位排序会把低位排好的结果打乱，整个算法直接失效。

保证稳定的关键在回收环节：必须按桶的顺序、桶内按元素进入的先后顺序依次取出。用数组模拟桶、配合计数前缀和的方式天然满足这个要求，因为写入时就是按原数组顺序扫描、按桶内偏移递增写入的。如果用链表挂桶，尾插法也能保证稳定，但指针开销大、缓存不友好，我不推荐。

注意：任何在桶内做二次排序、或者用不稳定的容器（比如某些哈希结构）来组织桶内元素的写法，都会破坏稳定性，务必避开。

2. 核心细节解析与实操要点

2.1 按位拆解：取位运算的正确姿势

按字节版本里，取第i个字节的标准写法是：

uint32_t byte = (value >> (i * 8)) & 0xFF;

这里i从0开始，表示最低字节。移位量是i * 8，掩码0xFF保证只留低8位。这个写法对无符号整数是安全的，但如果键值是有符号整数，直接右移会做符号扩展，高位补1，取出来的字节就错了。

处理有符号整数的常见做法是先做偏移映射，把有符号范围平移到无符号区间：对32位有符号整数，加上0x80000000（即1u << 31）转成无符号再排，排完再减回去。这样负数和小正数的相对顺序就正确了。我一开始没做这个转换，测试时负数全跑到正数后面去了，排查了半天才反应过来是符号位的问题。

2.2 计数数组与前缀和的配合

每一趟排序分三步走：统计每个桶的元素个数、把计数转成前缀和（即每个桶的起始写入位置）、再扫一遍原数组按位置写入临时数组。前缀和这一步是精髓，它把"桶"从抽象概念变成了数组上的连续区间。

具体来说，统计完count[b]后，做一次累加：count[b] += count[b-1]，此时count[b]表示"第b个桶及之前所有桶的元素总数"，也就是第b个桶的结束位置（开区间）。写入时为了稳定，要从后往前扫原数组，每写一个就把对应计数减一，这样相同键值的元素保持原有相对顺序。这个"从后往前扫"的细节很多人会写反，写反了稳定性就没了。

我第一版就是从前往后扫、计数递增，结果相同键值的元素顺序被颠倒，排序结果在重复元素多的数据集上直接错乱。改成从后往前、计数递减之后才正确。

2.3 临时数组的复用与内存布局

每趟排序都需要一个和原数组等大的临时数组。朴素写法是每趟都new一个，排完delete，4趟下来就是8次堆分配，开销不小。我的做法是在排序开始前一次性分配好临时数组，所有趟次复用，排完统一释放。这样堆操作从8次降到2次。

更进一步，可以用双缓冲的思路：原数组和临时数组交替作为输入输出，避免每趟都做整体拷贝。不过要注意趟数为奇数时最终结果落在临时数组里，需要再拷回原数组。我图省事，每趟排完都拷回原数组，多一次O(n)拷贝，但代码逻辑清晰，实测对性能影响很小（拷贝是连续内存操作，很快）。

2.4 桶数量的选择与缓存考量

256个桶的计数数组是int count[256]，1KB，能完整放进L1缓存，每趟清零和累加都很快。如果换成16位分桶（65536个桶），计数数组256KB，超出L1、逼近L2，缓存miss会明显增多，虽然趟数从4降到2，但综合下来不一定更快。我对比测过，32位整数用8位分桶（4趟）通常是最佳平衡点，16位分桶在数据量特别大（上亿）时才略有优势。

这个结论不是绝对的，跟CPU缓存大小、数据分布都有关。我的建议是先用8位分桶跑基准，如果确实有性能诉求再尝试16位，别一上来就追求大桶。

3. 完整实操过程与核心代码实现

3.1 环境准备与工程结构

我用的是标准的C++17环境，编译器g++ 11以上或MSVC 2019以上都行，没有第三方依赖。工程就三个文件：radix_sort.h放声明，radix_sort.cpp放实现，main.cpp做测试。这样拆分是为了方便复用，实际项目里直接把头文件和实现拖进去就能用。

编译命令很简单：

g++ -O2 -std=c++17 main.cpp radix_sort.cpp -o radix_test

-O2一定要加，基数排序的循环体很密集，不开优化性能差一大截。我一开始忘了加，测出来的时间和开了优化差了将近3倍，差点误判算法不行。

3.2 十进制版本：理解原理的起点

先给十进制版本，每位10个桶，逻辑最直白：

#include <vector> #include <algorithm> void radixSortDecimal(std::vector<int>& arr) { if (arr.empty()) return; int maxVal = *std::max_element(arr.begin(), arr.end()); // 处理负数：整体偏移到非负区间 int minVal = *std::min_element(arr.begin(), arr.end()); long long offset = 0; if (minVal < 0) { offset = -(long long)minVal; for (auto& x : arr) x += offset; maxVal += offset; } std::vector<int> tmp(arr.size()); for (long long exp = 1; maxVal / exp > 0; exp *= 10) { int count[10] = {0}; for (int x : arr) count[(x / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; for (int i = (int)arr.size() - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; tmp[--count[d]] = arr[i]; } arr = tmp; } if (offset) for (auto& x : arr) x -= offset; }

这段代码里几个点值得说。exp从1开始每次乘10，控制当前处理哪一位；maxVal / exp > 0判断是否还有更高位要处理。负数的处理用整体偏移，把所有元素平移到非负区间，排完再平移回来，这样避免了符号位干扰。tmp[--count[d]] = arr[i]这一行是稳定性的关键，先减再取，配合从后往前扫，保证相同键值顺序不变。

3.3 按字节版本：工程实用的主力

十进制版跑通后，换成按字节版本，性能提升明显：

#include <vector> #include <cstdint> void radixSortBytes(std::vector<uint32_t>& arr) { if (arr.size() < 2) return; const int BUCKETS = 256; std::vector<uint32_t> tmp(arr.size()); std::vector<int> count(BUCKETS); for (int shift = 0; shift < 32; shift += 8) { std::fill(count.begin(), count.end(), 0); for (uint32_t x : arr) count[(x >> shift) & 0xFF]++; for (int i = 1; i < BUCKETS; i++) count[i] += count[i - 1]; for (int i = (int)arr.size() - 1; i >= 0; i--) { uint32_t b = (arr[i] >> shift) & 0xFF; tmp[--count[b]] = arr[i]; } arr.swap(tmp); } }

这里shift从0到24，每次加8，正好覆盖32位整数的4个字节。arr.swap(tmp)用交换代替拷贝，效率更高，但要注意交换后tmp里装的是上一轮的旧数据，下一轮会被完全覆盖，所以没问题。这个swap的写法比整体拷贝优雅，也是我最终采用的版本。

如果键值是有符号整数，调用前先做偏移转换：

void sortSigned(std::vector<int32_t>& arr) { std::vector<uint32_t> u(arr.size()); for (size_t i = 0; i < arr.size(); i++) u[i] = (uint32_t)arr[i] ^ 0x80000000u; // 翻转符号位 radixSortBytes(u); for (size_t i = 0; i < arr.size(); i++) arr[i] = (int32_t)(u[i] ^ 0x80000000u); }

用异或翻转符号位比加减偏移更简洁，效果一样：负数变到无符号区间的高半段，正数在低半段，排完再翻回来，顺序就对了。

3.4 测试用例与性能验证

测试我分了三组：随机数据、全相同数据、已排序数据。全相同数据是检验稳定性和边界的好材料，已排序数据能暴露趟数判断的问题。每组都跑1000万个数，记录耗时：

数据量到百万级时两者差距还不大，千万级基数排序优势明显。全相同数据下基数排序也稳定，因为每趟分配回收都是确定性的，不受数据分布影响，这也是它相对快排的一个隐性优势——没有最坏情况退化。

4. 常见问题与排查技巧实录

4.1 排序结果错乱：先查稳定性

结果不对，第一反应查稳定性。最常见的两个错误：回收时从前往后扫导致相同键值顺序颠倒；或者计数前缀和算错，桶区间重叠。排查方法很简单，构造一个含大量重复元素的数组，比如{3,1,3,2,3,1}，跑一遍看重复元素的相对位置有没有变。如果变了，基本就是回收方向或计数递减写反了。

4.2 负数排序异常：符号位没处理

有符号整数直接按字节排，负数会全部跑到正数后面。原因是负数的最高位是1，按无符号解释时变成了很大的数。解决办法就是前面说的异或翻转符号位，或者整体偏移。我建议用异或，代码短且不涉及数值溢出风险。

4.3 性能不达预期：检查编译优化和内存分配

如果实测比快排还慢，先确认三件事：编译有没有开-O2；临时数组是不是每趟都重新分配；桶计数数组是不是用了std::map之类的重结构。这三点任何一个出问题都会拖垮性能。我见过有人用std::vector<std::vector<int>>做桶，每个桶一个vector，分配开销巨大，改成计数前缀和数组后快了十几倍。

4.4 常见问题速查表

提示：按字节版本直接固定跑4趟（32位整数），不要动态判断最高位，省去判断逻辑且不会漏排，代价只是多跑几趟空桶，实测影响微乎其微。

4.5 几个实操心得

第一，先用小数据验证正确性，再上大数据测性能。我习惯用10个元素的手算结果做基准，跑通再放大。第二，临时数组和计数数组在循环外分配，这是性能优化的第一优先级，比任何算法层面的微调都管用。第三，有符号和无符号分开处理，别在一个函数里用模板硬套，类型转换的坑比想象中多。第四，测试数据一定要包含全相同、已排序、逆序这三种极端情况，随机数据反而最容易蒙混过关。

这套实现我后来在一个日志时间戳排序的场景里用过，时间戳是64位整数，把按字节版本扩展到8趟就搞定了，改动量很小。基数排序这类算法的价值就在于结构清晰、扩展直接，把按位拆解和稳定回收这两件事吃透，换个键值类型基本就是改改移位参数的事。