C++基数排序实战：LSD实现、性能优化与避坑指南

基数排序这个算法，很多人第一次听到会觉得它有点"另类"——它不靠比较大小来排序，而是把整数按位拆开，一位一位地分配和收集。我在实际项目里第一次真正用上它，是因为要处理一批百万级的无符号整数ID，试过std::sort之后发现耗时不太理想，后来换成基数排序，在特定数据分布下确实拿到了明显的性能提升。但这里要先泼一盆冷水：基数排序不是万能的，它对数据类型有要求，对内存有额外开销，写不好还容易踩坑。这篇内容我会从C++实现的角度，把基数排序的原理、代码结构、关键参数选择、性能边界和实际踩过的坑都讲清楚，适合有一定C++基础、想搞明白"为什么这样写"的读者，也适合想拿一份能直接编译运行的源码去改的开发者。

1. 基数排序到底在排什么：从"按位分配"说起

1.1 它和比较排序的根本区别

我们平时用的std::sort、归并排序、快速排序，本质上都在做一件事：拿两个元素比大小，根据比较结果决定谁在前谁在后。这类算法的时间复杂度下界是O(n log n)，这是比较模型下的理论极限。基数排序跳出了这个模型，它压根不比较两个数谁大谁小，而是把每个数看成若干个"位"的组合，从低位到高位（或者从高位到低位）逐位处理，每一轮只关心当前这一位上的数字是几，然后把这个数放进对应的"桶"里。

打个生活化的比方：假设你要把一堆写着三位数的卡片按大小排好。比较排序的做法是两两对比卡片上的数字；基数排序的做法是，先只看个位数，把卡片分成0到9共十摞，按摞的顺序叠起来；再看十位数，重新分成十摞叠起来；最后看百位数，再分一次。三轮之后，卡片自然就有序了。这个"分摞再叠起来"的过程，就是基数排序的核心动作——分配（distribution）和收集（collection）。

这个思路带来的直接好处是：每一轮分配和收集都是线性的，总共做k轮（k是最大数的位数），时间复杂度就是O(k·n)。当k相对log n较小的时候，它比比较排序更快。代价是需要额外的桶空间，以及数据必须是"可按位拆分"的类型，比如整数、定长字符串。

1.2 LSD与MSD：两种方向的取舍

基数排序有两个方向：LSD（Least Significant Digit，从最低位开始）和MSD（Most Significant Digit，从最高位开始）。这两个不是随便选的，背后有明确的逻辑。

LSD的做法是从个位开始，一轮一轮往高位走，每一轮必须是稳定的分配——也就是说，同一桶里的元素要保持它们进入时的相对顺序。为什么必须稳定？因为低位的排序结果要被高位继承。举个例子，两个数12和15，个位分别是2和5，第一轮排完是12在前15在后；到了十位，两者十位都是1，进同一个桶，如果这一轮不稳定，可能变成15在前，那之前个位排好的顺序就白费了。所以LSD基数排序的正确性完全依赖每一轮分配的稳定性。

MSD则是从最高位开始分桶，分完之后每个桶内部再递归地按次高位排序。它更像快速排序的分治思路，好处是不需要把整个数组跑满k轮，某些桶元素少的时候可以提前用插入排序收尾。但MSD的实现复杂度明显更高，递归调用、桶边界管理都更麻烦，而且它天然不保证全局稳定（除非额外处理）。

在C++工程实践里，绝大多数场景用的是LSD，因为实现简单、逻辑清晰、稳定，而且对整数类型非常友好。本文的源码也走LSD路线。MSD更适合字符串排序或者位数很多、数据分布极不均匀的场景，那是另一个话题。

1.3 为什么选"10"作为基数，以及什么时候该换

最直观的基数选择是10，因为我们习惯十进制，取某一位的数字就是(num / power) % 10。但基数不一定非得是10。基数选多大，直接影响轮数和每轮桶的数量。

假设整数范围是32位无符号，最大值约42亿，十进制下有10位，那基数10就要跑10轮，每轮10个桶。如果换成基数256（也就是按字节处理），32位整数只需要4轮，每轮256个桶。轮数从10降到4，但每轮的桶数组从10个变成256个。这是一个典型的权衡：基数越大，轮数越少，但每轮的辅助空间和清零开销越大。

实际选型时我一般这样判断：数据量n很大的时候，减少轮数带来的收益更明显，因为每轮都要完整遍历一遍数组，轮数是乘在n上的；而桶的数量只影响辅助数组的大小和初始化成本，是常数级的。所以处理大批量32位整数时，基数256往往是更好的选择。但如果n只有几千个，基数10的实现更简单，桶数组小、缓存友好，反而可能更快。这个没有绝对答案，后面我会给一个实测对比的思路。

2. 一份能直接跑的LSD基数排序源码拆解

2.1 整体函数签名与辅助空间规划

先看整体结构。我习惯把基数排序写成一个模板函数，接受迭代器范围，内部根据元素类型推导出需要的位数和掩码。下面这份是处理无符号整数的版本，也是实际用得最多的：

#include <vector> #include <cstdint> #include <algorithm> #include <type_traits> template <typename T> void radixSortLSD(std::vector<T>& arr) { static_assert(std::is_integral<T>::value && std::is_unsigned<T>::value, "radixSortLSD requires unsigned integral type"); if (arr.size() < 2) return; constexpr int RADIX_BITS = 8; constexpr int RADIX = 1 << RADIX_BITS; // 256 constexpr int MASK = RADIX - 1; // 0xFF constexpr int TOTAL_BITS = sizeof(T) * 8; constexpr int PASSES = (TOTAL_BITS + RADIX_BITS - 1) / RADIX_BITS; std::vector<T> buffer(arr.size()); std::vector<size_t> count(RADIX, 0); T* src = arr.data(); T* dst = buffer.data(); for (int pass = 0; pass < PASSES; ++pass) { int shift = pass * RADIX_BITS; std::fill(count.begin(), count.end(), 0); for (size_t i = 0; i < arr.size(); ++i) { ++count[(src[i] >> shift) & MASK]; } size_t sum = 0; for (int i = 0; i < RADIX; ++i) { size_t c = count[i]; count[i] = sum; sum += c; } for (size_t i = 0; i < arr.size(); ++i) { T key = (src[i] >> shift) & MASK; dst[count[key]++] = src[i]; } std::swap(src, dst); } if (src != arr.data()) { std::copy(src, src + arr.size(), arr.data()); } }

这段代码有几个设计点值得展开说。第一，用static_assert把类型限制在无符号整型上，因为无符号数的位运算语义干净，右移是逻辑移位，不会引入符号位的干扰。如果直接拿有符号整数做右移，负数的符号位扩展会让(num >> shift) & MASK的结果出错，这是很多人第一次写基数排序时踩的坑。第二，buffer和count在循环外一次性分配，避免每轮重复申请内存，这个细节对性能影响很大。第三，用src和dst两个指针来回交换，而不是每轮都拷贝回原数组，减少了一次完整的内存搬运。

2.2 计数数组的前缀和：稳定性的关键一步

代码里那个把count数组原地转成前缀和的循环，是整个算法稳定性的命门，值得单独拎出来讲。count[i]一开始存的是"当前位上数字等于i的元素有几个"。做完前缀和之后，count[i]变成了"当前位上数字小于i的元素总共有多少个"，也就是数字i应该放置的起始位置。

为什么这样就能保证稳定？因为我们在第二遍遍历时，是从左到右扫描原数组的，每放一个元素，对应的count[key]就自增一次。这意味着同一个桶里的元素，先被扫描到的先放，后扫描到的放在它后面，相对顺序被完整保留。这就是稳定分配的实现方式——前缀和给出桶的起点，顺序扫描保证桶内有序。

这里有个容易忽略的细节：count数组的元素类型我用的是size_t而不是int。因为当数组长度超过20亿时，int会溢出，前缀和直接算错。虽然实际项目里很少遇到这么大的数组，但既然写通用代码，类型就该选对。另外，前缀和的累加变量sum也必须是size_t，这个坑我在早期代码里踩过，数组一大结果就乱，排查了半天才发现是整型溢出。

2.3 多轮之间的指针交换与最终归位

std::swap(src, dst)这一步看着简单，但逻辑要想清楚。每一轮开始时，src指向当前有效数据，dst指向空闲缓冲区；一轮结束后，排好序的数据在dst里，所以交换指针，让下一轮的src指向刚排好的结果。这样交替使用两块内存，避免了每轮都往原数组拷贝。

但这里有个边界情况：如果总轮数是奇数，最后一轮结束后，有效数据在buffer里，而arr里还是旧数据。所以循环结束后要判断src是否还指向arr.data()，如果不是，就把结果拷回去。这个判断不能省，否则调用方拿到的数组可能是没排完的中间状态。我见过有人图省事，直接在循环里每轮都拷回原数组，代码是简单了，但性能白白损失一大截，数据量大时这个拷贝开销很可观。

还有一点，std::copy这里用的是src到src + arr.size()，而不是buffer.begin()到buffer.end()，因为src可能指向arr也可能指向buffer，用指针加偏移的写法两种情况都成立。这种写法在模板代码里更稳妥。

3. 基数选择与性能边界：什么时候它真的更快

3.1 基数10、256、65536的实测取舍

前面提过基数选择是个权衡，这里给一个更具体的分析框架。假设n是元素个数，k是轮数，r是基数。总的时间开销大致是：k轮 × (n次计数 + r次前缀和 + n次分配)。其中n相关的部分是2kn，r相关的部分是kr。当n远大于r时，主导项是2kn，此时减少k（增大r）收益明显；当n和r接近时，前缀和的kr开销就不能忽略了。

我做过一组粗略的对比测试，数据是100万个随机32位无符号整数，在同一台机器上跑：

可以看到基数256在百万级数据上表现最好，基数65536虽然轮数更少，但计数数组太大，缓存命中率下降，反而拖慢了。基数10轮数太多，每轮都要完整扫一遍数组，累积起来就慢了。这个结论不是绝对的，数据量、元素类型、机器缓存大小都会影响结果，但"256是个不错的默认值"这个经验在多数场景下成立。

需要强调的是，这些数字只是量级参考，真实项目里一定要自己测。我建议的做法是写一个简单的benchmark，固定数据规模，把几种基数都跑一遍，看实际耗时。不要迷信任何一篇博客给的绝对数字，包括这篇。

3.2 它打不过std::sort的场景

基数排序不是无脑快。有几个场景它明显不占优，甚至更慢，得心里有数。

第一，数据量小的时候。n只有几百上千，std::sort的常数因子小、缓存友好，基数排序光是初始化桶数组、多轮遍历的开销就盖过了理论优势。我一般以n在几万以上作为考虑基数排序的起点，低于这个量级直接用std::sort。

第二，数据本身接近有序或者有大量重复的时候。std::sort的introsort在这种情况下表现很好，而基数排序该跑的轮数一轮不少，没有"提前收敛"的机制。

第三，元素类型不是整数的时候。基数排序要求能按位拆分，浮点数需要做位变换（把符号位和指数尾数重新编码成可比的无符号整数），结构体、字符串（定长除外）都不好直接套。这种时候比较排序是更自然的选择。

第四，内存受限的嵌入式环境。基数排序需要一份和原数组等大的辅助缓冲，内存翻倍。如果内存紧张，原地排序的堆排序或者std::sort更合适。

所以我的实际策略是：先判断数据类型和规模，整数且量大才考虑基数排序，否则老老实实用标准库。这个判断本身比会写基数排序更重要。

3.3 有符号整数和浮点数怎么处理

前面代码限制了无符号整型，但有符号整数和浮点数在实际中也很常见，得给个处理办法。

有符号整数的标准做法是做一个"偏移变换"：把符号位翻转，也就是x ^ (1 << (bits - 1))，这样负数会变成比正数小的无符号数，映射关系保持单调。排完之后再翻转回来。这个变换只改最高位，不影响低位，所以可以直接套用无符号版本的基数排序。

浮点数稍微麻烦一点。IEEE 754的浮点数不能直接按位比较，因为负数的位模式在无符号意义下反而更大。常见的处理是：先取位模式，如果符号位是1（负数），把所有位取反；如果符号位是0（正数），只翻转符号位。这样变换后的无符号整数顺序就和浮点数的真实大小顺序一致了。排完再逆变换回去。这个技巧在处理大量浮点数据时很有用，但要注意NaN和无穷大的边界情况，实际项目里如果数据可能含NaN，最好先过滤或者单独处理。

4. 实际踩过的坑与调试经验

4.1 计数数组没清零导致的脏数据

这个坑我踩过不止一次。基数排序每一轮开始前，count数组必须清零，因为上一轮的前缀和结果还留在里面。如果忘了清零，或者清零不彻底（比如只清了用到的部分），这一轮的计数就会叠加上一轮的残留值，结果完全错乱。

更隐蔽的一种情况是：有人为了"优化"，把count数组声明在循环内部，以为每次重新构造就自动清零了。这在语义上是对的，但每轮都重新分配vector，性能会明显下降。正确做法是循环外分配一次，循环内用std::fill清零。std::fill对连续内存的优化很好，比手写for循环清零通常更快，也更不容易写错边界。

排查这类问题的技巧：如果排序结果部分有序、部分乱，而且乱的模式和位数有关，八成是计数或前缀和出了问题。可以在每轮结束后打印count数组的前几个值和数组前几个元素，对照手算结果，很快能定位。

4.2 移位量溢出与类型提升的陷阱

shift = pass * RADIX_BITS这行，当pass较大时，shift可能达到或超过类型的位宽。比如32位类型，pass最大是3，shift最大24，没问题；但如果有人把RADIX_BITS改成16，PASSES变成2，shift最大16，也没问题。真正危险的是当shift等于或超过位宽时，C++标准里对移位量大于等于位宽的行为是未定义的，不同编译器可能给出不同结果。

另一个陷阱是类型提升。(src[i] >> shift) & MASK里，如果src[i]是uint8_t或uint16_t，在移位和与运算之前会先被提升成int。对于无符号小类型，提升成int后高位是0，结果正确；但如果类型是有符号的，提升可能带符号扩展，结果就错了。所以再次强调，用无符号类型，并且注意MASK的类型要和运算结果匹配。

我一般的防御性写法是把中间结果显式转成size_t或uint32_t再索引，避免隐式转换带来的意外。多写几个static_cast不丢人，调试一个移位bug花的时间够写一百个转换了。

4.3 大数据量下的内存与缓存表现

基数排序的辅助缓冲是n个元素，这个内存在数据量大时不可忽视。我处理过一批千万级的整数，辅助缓冲占了40MB，加上原数组80MB，总共120MB。这时候缓存的影响就很明显了：每一轮分配阶段都是随机写入dst（因为按key散开到不同位置），缓存命中率低，实际带宽利用率不高。

优化思路有几个。一是减小基数，让桶更集中，写入局部性更好，但轮数增加，得权衡。二是分块处理，把大数组切成能放进L2/L3缓存的小块，块内做基数排序，块间再归并，这个思路叫缓存友好的基数排序，实现复杂度高不少，一般项目用不上。三是如果数据本身有范围信息（比如知道最大值不大），可以动态缩小轮数，少跑几轮没必要的。

实测下来，对于千万级数据，朴素的LSD基数排序相比std::sort的优势会缩小，因为内存带宽成了瓶颈。这时候要不要用基数排序，得看具体数据分布和硬件，不能一概而论。

4.4 稳定性验证的土办法

基数排序号称稳定，但代码写错的时候稳定性最先崩。验证稳定性的土办法是：给每个元素附加一个原始下标，排序后检查相同key的元素，它们的原始下标是否保持递增。如果发现相同key的元素下标乱了，说明分配阶段不稳定，回去查前缀和和扫描顺序。

这个验证在单元测试里很值得加一条，尤其是当你改动过计数或分配逻辑之后。我习惯在测试里构造一批有大量重复key的数据，专门用来暴露稳定性问题，因为随机数据里重复少，不稳定反而不容易显现。

5. 把它用进真实代码：封装与测试建议

5.1 接口设计：模板还是具体类型

实际项目里，我倾向于把基数排序封装成一个接受迭代器范围的模板函数，而不是只接受std::vector。这样它能配合各种容器使用，也更符合C++标准库的风格。但要注意，基数排序需要随机访问迭代器，链表之类的容器用不了，所以模板里可以用static_assert检查迭代器类别，给出清晰的编译错误。

另一个设计选择是是否暴露基数参数。默认给256，但允许调用方指定，方便针对特定数据调优。这个参数用模板非类型参数还是运行时参数，取决于是否需要编译期优化。如果追求极致性能，用模板参数可以让编译器把RADIX和MASK常量折叠；如果更看重灵活性，运行时参数也行。我一般默认模板参数，特殊场景再特化。

5.2 测试用例该覆盖哪些边界

基数排序的测试不能只测随机数据，边界情况才是bug高发区。我通常会覆盖这几类：空数组和单元素数组（验证提前返回逻辑）、全部相同的元素（验证稳定性）、已经有序和完全逆序的数据（验证不依赖初始顺序）、包含0和最大值的极值数据（验证移位边界）、以及元素个数刚好是基数整数倍和非整数倍的情况（验证计数和分配边界）。

还有一类容易被忽略：元素个数超过int范围但没超过size_t的情况。虽然测试环境很难真的构造这么大的数组，但可以通过类型检查和小规模模拟来验证逻辑。至少确保代码里所有计数和索引都用size_t，不给自己埋雷。

5.3 和标准库配合的实用模式

在实际业务代码里，我很少直接裸调基数排序，更多是把它作为一个可选的排序策略。比如先判断数据规模和类型，满足条件走基数排序，否则回退到std::sort。这种"策略选择"的封装比硬编码某一种排序更实用，也更容易在不同数据上拿到好结果。

还有一种模式是部分排序：如果只需要前k个最小元素，没必要全排，可以用基数排序配合计数，只收集需要的桶。这个在Top-K场景下有用，但实现要小心，别把简单问题复杂化。多数时候std::nth_element已经够用，基数排序的优势还是在全量排序上。

写到这里，关于C++实现基数排序的核心内容基本覆盖了。我个人在实际操作中的体会是：这个算法的代码量不大，但细节密度高，计数数组的清零、前缀和的类型、指针交换的归位、有符号数的变换，每一处都值得反复确认。真正把它用好的关键，不在于背下代码，而在于清楚它的性能边界——知道什么时候该用它，什么时候该果断换回标准库。源码可以直接拿去编译，但建议先用自己的数据跑一遍benchmark，再决定要不要放进生产代码里。