基数排序这个词，在多数算法教科书里被放在“高级排序”一章，但讲真，它比快速排序更简单，门槛也更低。我第一次被它圈粉，是在给一批将近八十万的定长编号做排序时。原来的实现用的默认快排，处理完整份数据花了大概三秒；换成基数排序，同样这份数据只用了不到零点几秒。区别不在于用了什么奇技淫巧，而在于它压根不走“比较大小”这条路。
基数排序属于非比较排序，核心思想一句话就能讲清：把整数按位拆开，从低位到高位（也有从高位到低位的版本）逐趟做稳定排序。它不需要知道“a 是否大于 b”，只需要知道“a 的某一位数字是几”。适合数据量较大、位数相对较少且可接受额外空间的场景。典型代表有手机号排序、银行卡号排序、IP整数排序、批量文件编号排序。
如果你刚学完冒泡、快排和归并，想理解“比较排序 O(n log n) 的下限是怎么被绕开的”；或者你正在处理定长编码数据，想把排序延迟降下来，这篇文章正好对路。后面我会把原理、稳定性、完整代码、两趟手工模拟、负数与空间问题都过一遍，很多细节是教科书里不会展开讲的。
1. 基数排序的设计思路与本质：不谈比较，也能排序
1.1 最像“人工整理档案”的过程
如果你想整理一抽屉两位数卡片，要求最后按从小到大排好，最自然的想法是两两比较，让大的向后移动。这是冒泡排序。
基数排序提供了另一条路：先看个位。个位是0的卡片放进0号格，是1的放进1号格……一直到9号格。全部放完之后，从0号格开始，把卡片按顺序收成一叠。这个过程叫“分配-收集”。然后，再看这叠卡片的十位，重复一遍刚才的动作。做完第二趟，你手头就是一叠整体有序的卡片。整个过程没有出现过“这张卡片比那张大”的判断。
第一次接触这个操作的人都会有一个疑问：光按个位、十位分类，凭什么最终就全局有序了？原因在于，第i趟结束时，数组已经保证“后i位组成的数字”是有序的，这称之为“后缀有序”。第一趟结束后，个位有序；第二趟结束后，因为十位是更高位，十位不同则十位大的排后面，而十位相同时维持了上一趟的个位顺序，所以“十位+个位”整体有序。这个“高位权重更高但依赖低位顺序”的递推关系，是整个算法的根基。
1.2 稳定是第一生命线
我见过不少人第一次写基数排序时，图省事，内层排序直接用了快速排序或者不稳定的选择排序，然后跑出来的结果一塌糊涂。问题几乎都出在同一处：稳定性没有保证。
稳定性的定义是，值相同的元素在排序前后保持相对位置。基数排序为什么必须依赖稳定？因为第二趟排序面对的是十位，它只能决定“十位不同时谁先谁后”，对于十位相同的元素，只能靠第一趟留下的相对顺序来决定谁先谁后。如果这里顺序被打乱，整个后缀有序就断了。
一个最简单的测试数据是 [12, 11] 两个数。第一趟按个位得到 [11, 12]；第二趟按十位，两个数的十位都是1，稳定排序会保持原数组中 11 和 12 的顺序，也就是11在前；如果内层排序不稳定，把这两个数交换成 [12, 11]，那结果就是错的。所以写代码时，“从后往前回填”这个细节不是玄学，而是稳定性的直接保证。
1.3 LSD 与 MSD：两条路线
LSD 是最常见的实现。对整数，从最低位向最高位，逐趟排序。它的特点是：每一趟都在向“后缀有序”逼近，整数场景下逻辑最简单，也是文章后面实操的主角。
MSD 则是从最高位开始的。第一趟按最高位分桶，桶与桶之间天然建立了大小关系；接着桶内递归地对下一位做同样的处理。它天然适合字符串：字典序中，最前面的字符优先级最高，正好符合“先看最高位”的思路。缺点是桶内递归让实现复杂度上了一个台阶，处理不好容易栈溢出。
有人会问，整数用 MSD 不行吗？行，只是结果需要再拼接，而且递归过程里每个桶内还要继续分，性能上不如 LSD 直截了当。所以实际工程中看到的大多数“基数排序”实现都是 LSD，这不代表 MSD 没用，只是选型时要注意数据形态。
2. 几个关键参数和实现选择：别一上来就写代码
先提醒一句，写代码之前有两个参数值得先想清楚：基数和每一趟的内层排序方式。这两个选择直接决定性能上限，很多初学者跳过这一步，拿着十进制模板就跑，结果换一种数据就懵了。
2.1 基数（进制）选多少，决定趟数和空间
基数排序有一个隐藏参数，进制 base。这个值真的会直接影响性能，但很多教材都只是拿十进制举例子，不提怎么选。
先说趟数。数组的最大值如果是 max，那么在 base 进制下，它的位数 d 大约是 log_base(max) 向上取整。比如 max=999，十进制下 d=3，十六进制下 d≈2，二进制下 d≈10。趟数就是从最低位到最高位需要处理的轮数。
一趟的代价主要包含 O(n) 的扫描填入，以及 O(base) 的计数数组清零和前缀和。总体复杂度就是 O(d × (n + base))。如果 base 取2，计数数组只有两个元素，空间非常省，但整数需要约32趟（32位场景），每趟都要完整扫描数组，时间不理想。如果 base 取256，一个32位整数最多4趟，但每次要准备一个长度为256的计数数组，空间是 O(n+256)。绝大多数情况下，256这个值在实际工程里是性价比之王——趟数少，计数数组也不大，恰好和字节对齐。教学场景下用10最直观，代码给人看也容易懂。
2.2 内层排序为何是计数排序的不二之选
每一趟，我们只对“某一位”做一次排序。这个内层排序的选择是决定整个算法能不能保住稳定性的关键。
第一个候选是计数排序。它在值域较小（base 可控）时复杂度为 O(n+base)，稳定，实现极简单，几乎是量身定做。第二个候选是桶排序，也能稳定，但桶本身还要再维护内部顺序，复杂化了。第三个候选是插入排序，虽然稳定，但 O(n²) 的代价在数据量大时完全不可接受。第四个候选是快排，快但不稳定，直接淘汰。
我的建议很明确：写基数排序时，内层一律用计数排序，不要自己发明别的方法。原因也很简单：这个场景里，值的范围恰好就是 0 到 base-1，计数排序不需要比较，只需要统计和回填，整个过程的常数因子非常小。
2.3 一趟的完整动作：频次、前缀和、倒序回填
现在把一趟拆成三个动作，每一步都不能错。
先准备一个长度为 base 的 int 数组 count，全部清零。然后遍历原数组，取出当前位 digit，执行 count[digit]++。这一步只是统计各个数字出现几次。
第二步，把 count 数组转成前缀和形式：从 i=1 开始，count[i] = count[i] + count[i-1]。改造之后，count[i] 的含义变成“当前位小于等于 i 的元素一共有多少个”。有了这个数，我们就知道每种 digit 的最后一段位置在 output 的哪里。
第三步，从原数组的最后一个元素倒着遍历，对每个元素算出 digit，令 pos = count[digit] - 1，把它放进 output[pos]，同时 count[digit]--。为什么必须倒着？因为正着遍历时，同一个 digit 的元素会先取到前面的位置，导致相对顺序反转。倒着填，后出现的元素反而先落到后面的位置，于是同 digit 内部保持了原数组的相对顺序，稳定就有了保障。这个细节是很多教程里一笔带过但代码里绝不能错的地方。
3. 实操过程与代码实现：从零手写一个 LSD 基数排序
3.1 准备数据与运行环境
我不会用什么高级库，就是标准 Java 数组。测试数据选用 [12, 65, 77, 32, 89, 47, 51, 23]。这组数最大为 89，两位数，正好演示两趟完整流程。你也可以随手换成任何一组非负整数数组跑。
3.2 完整代码
代码写成两个方法：radixSort 负责入口，countingSortByDigit 负责一趟。
public static void radixSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 找到最大值，确定需要多少趟 int max = arr[0]; for (int v : arr) { if (v > max) { max = v; } } int base = 10; // exp 表示当前位的权值：1、10、100…… for (int exp = 1; max / exp > 0; exp *= base) { countingSortByDigit(arr, exp, base); } } private static void countingSortByDigit(int[] arr, int exp, int base) { int n = arr.length; int[] count = new int[base]; int[] output = new int[n]; // 第一步：统计频次 for (int v : arr) { int digit = (v / exp) % base; count[digit]++; } // 第二步：前缀和，确定每个数字的落点区间 for (int i = 1; i < base; i++) { count[i] += count[i - 1]; } // 第三步：从后往前回填，保证稳定性 for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % base; int pos = count[digit] - 1; output[pos] = arr[i]; count[digit]--; } // 拷贝回原数组 System.arraycopy(output, 0, arr, 0, n); }代码里 exp 是当前位的权重，第一趟 exp=1 时，digit = (v/1)%10 拿到个位；第二趟 exp=10 时，digit = (v/10)%10 拿到十位。循环条件 max / exp > 0 很安全，因为当 exp 超过 max 时条件为假，不会出现 exp 溢出问题。
有个小坑要提醒：如果数组里有负数，这份代码直接跑会出问题，因为负数取模后 digit 是负数，count 数组越界。负数怎么处理我在后面专门讲。
3.3 手工模拟第一趟：按个位分配与收集
拿代码的思路，我们用 [12, 65, 77, 32, 89, 47, 51, 23] 走一遍个位。
先统计每个数字个位出现的频次：个位为1的有51，共1个；个位为2的有12和32，共2个；个位为3的有23，共1个；个位为5的有65，共1个；个位为7的有77和47，共2个；个位为9的有89，共1个。
转成前缀和之后，count[0]=0, count[1]=1, count[2]=3, count[3]=4, count[4]=4, count[5]=5, count[6]=5, count[7]=7, count[8]=7, count[9]=8。意思是：个位小于等于2的元素总共有3个，个位小于等于7的元素总共有7个。
从原数组尾部向前遍历：
- 23，个位3，应放 index 3，output[3]=23
- 51，个位1，应放 index 0，output[0]=51
- 47，个位7，应放 index 6，output[6]=47
- 89，个位9，应放 index 7，output[7]=89
- 32，个位2，应放 index 2，output[2]=32
- 77，个位7，应放 index 5，output[5]=77
- 65，个位5，应放 index 4，output[4]=65
- 12，个位2，应放 index 1，output[1]=12
第一趟结束后数组变成 [51, 12, 32, 23, 65, 77, 47, 89]。验证一下个位：从左到右是1、2、2、3、5、7、7、9，确实是一个非递减序列。注意这里个位同为2的两个数，原数组里12在32前面，第一趟结束后仍然是12在32前面，稳定性在这一步就已经体现出来了。
3.4 手工模拟第二趟：按十位分配与收集
现在对 [51, 12, 32, 23, 65, 77, 47, 89] 按十位排序。十位频次分别如下：十位为1的有12，共1个；十位为2的有23，共1个；十位为3的有32，共1个；十位为4的有47，共1个；十位为5的有51，共1个；十位为6的有65，共1个；十位为7的有77，共1个；十位为8的有89，共1个。
前缀和后，count[1]=1, count[2]=2, count[3]=3, count[4]=4, count[5]=5, count[6]=6, count[7]=7, count[8]=8。
从右往左回填：
- 89，十位8，pos=7，output[7]=89
- 47，十位4，pos=3，output[3]=47
- 77，十位7，pos=6，output[6]=77
- 65，十位6，pos=5，output[5]=65
- 23，十位2，pos=1，output[1]=23
- 32，十位3，pos=2，output[2]=32
- 12，十位1，pos=0，output[0]=12
- 51，十位5，pos=4，output[4]=51
最终结果 [12, 23, 32, 47, 51, 65, 77, 89]，整体有序。你可以自己挑一组三位数再走一遍，思路完全一样，只是多了百位一趟。关键点在于，每一位排序结束时，数组已经满足“后几位组成的数”有序。
3.5 复杂度与空间分析
时间复杂度是 O(d × (n + base))，其中 d 是最大元素在 base 进制下的位数。每一趟里，统计频次是 O(n)，前缀和是 O(base)，回填是 O(n)。所以总操作量等于趟数乘以单趟代价。
对于固定范围的整数，base 取 256，d 最大也就是4，复杂度近似 O(4n)，这就是基数排序能突破比较排序下限的原因——比较排序至少需要 n log n 次两两比较，而基数排序用“按位分配”绕开了比较。
空间复杂度是 O(n + base)。output 数组长度 n，count 数组长度 base。如果数据量大且内存紧张，这会成为一个考量因素。稳定性方面，算法整体是稳定的，因为每一趟内层计数排序都保持了稳定。这个特性让基数排序在很多业务场景里特别有价值：你可以先按主关键字排，再按次关键字排，层级顺序不会乱。
4. 常见问题与排查技巧
4.1 负数怎么处理
这是我被问得最多的问题，也是一个非常容易踩的坑。直接对负数数组跑上面的代码，digit 可能是负数，count[digit] 会越界，轻则 ArrayIndexOutOfBounds，重则程序崩溃。
最简单的办法是全量偏移。先扫描数组找到最小值 min，如果 min < 0，把每个元素加上 -min，让所有元素变成非负数；排完序后再整体减去 -min。这个方法实现容易，但要注意如果数组里的数很大，加上偏移后可能溢出 int，需要用 long 临时存储或在排序后用 long 接收。
第二种办法是把负数和正数分开处理。负数取绝对值后单独用基数排序，得到的结果是绝对值从大到小的序列，反转后就是负数从小到大的序列；正数部分照常排序，最后拼接。这个思路代码稍复杂，但不会溢出。
第三种办法是把所有 int 看成无符号数处理。利用补码性质，负数会被当成比正数更大的值，排序后负数集中在尾部，再把负数段整体翻到前面。这个方法性能最高，但代码理解成本也高，日常遇到负数数据时我推荐前两种。
4.2 数据的位数不齐怎么办
实际场景里，同一批数据很可能一个是 123，一个是 4，另一个是 88。搞不清位数会不会导致排序错乱。
其实不会。代码计算 digit 时，如果这个数根本没有当前位，比如 4 的十位是0，那么 digit=0，它会进入0号桶。可以说这是“隐式补零”，无需真的把数字补齐成等长字符串。只要数组里没有负数，0号桶在每一趟都会被正确对待。位数为空的那一位，天然放在所有非0值的前面，这与数值大小完全吻合。
4.3 空间占用太大怎么办
如果数据规模非常大，每趟都开一个长度 n 的 output 数组可能会让人肉疼。有三个方向可以处理。
第一，改用链式桶。不用 output 数组和前缀和，而是准备 base 个链表队列，每一趟把元素挂到对应桶后面，收集时按桶顺序串起来。缺点是维护链表结点有额外开销，速度通常比数组实现慢，但空间上更灵活。
第二，减少基数。把 base 从 256 降到 16，甚至 10，虽然趟数变多了，但每趟的计数数组更小，内存占用峰值更低。
第三，如果数据满足某些特殊结构，可以尝试所谓的“原地基数排序”，不借助完整 output 数组，直接在原数组内搬移元素。这类实现写起来复杂、稳定性也难保证，除非内存真的见底，否则不建议自己造。
4.4 什么时候该用基数排序，什么时候该用快排归并
这个判断我做了一个小口诀：数据量大、位数少、值域集中、能接受额外空间，优先考虑基数排序。反过来，如果数据比较随机、位数差异大，或者内存非常紧张，快排和归并往往更合适。
举个例子，100万个手机号，每一位都是0~9，最大位数11，用 base=10 需要11趟，总操作量约1100万；就算不用字节优化，也已经明显少于快排需要的约两千万次比较。位数短的时候，基数排序是真的能碾压比较排序的。但如果拿它去排一批长度差距很大的字符串或浮点数，效果就可能不如精心调优的快速排序。
5. 三段实战复盘：什么场景下我把基数排序当首选
5.1 场景一：定长编号排序
某次数据清洗时，遇到一张几百万行的流水表，里面有一列固定长度的业务编号，比如“ID+年月日+序号”的混合格式。由于是ASCII字符，本质上是定长字符串，依然可以按位排序，相当于做 20 趟 base=128 的基数排序。换成基数排序后，排序耗时下降了不止一个量级。
对于这种定长编码，基数排序的优势在于它不像字符串比较那样依赖字典序的反复比较，而是直接按每一个字符位做一次稳定分配。批次越多，效果越明显。
5.2 场景二：整数按字节处理
处理32位非负整数时，把每个整数当成4个字节，base=256，做4趟基数排序。这是很多高性能排序库的内部做法。因为一趟的计数数组只有256个坑，可以全部塞进CPU缓存，实际运行速度非常快。
这种“字节序排序”写法其实不复杂：exp 从1开始，每趟乘以256；对每个整数取出当前字节时，用 (v / exp) % 256。代码跟前面几乎一样，只是 base 从10换成了256。有个细节要注意，如果整数有符号，负数会排在正数后面，使用时要处理好符号问题。
5.3 场景三：时间戳字符串排序
日志场景里，时间戳字符串往往是固定格式，例如“YYYY-MM-DD HH:mm:ss”。当做字符串排序时，基数排序天然合适。第一趟先按秒排，接着按分钟、小时……一路向上。由于字符串高位（年、月）权重大，等排完最高位后，所有日志就按时间有序了。
也许有人会觉得，直接对字符串用字典序排序不是更方便吗？如果数据量特别大，字典序比较本身耗时不低。按位稳定排序让每个字符位的处理都变成简单的分桶，能有效降低整体耗时。我处理过接近千万级的日志行排序，这个方案稳定且快。
6. 把基数排序用好的三条经验
6.1 先看数据形态再决定选型
基数排序很强，但不是万能的。我自己的经验是，它最适合两类数据：非负整数和定长编码。遇到浮点数、长度不一的文本、结构体对象，先想想有没有更合适的方案。尤其是浮点数的 IEEE 754 表示虽然是可排序的，但处理起来远比整数麻烦，不值得为了炫技去搞。
6.2 稳定性在工程里会带来红利
很多教程把稳定性当成一道概念题，但在实际开发中，它意味着你可以“低成本地做多级排序”。比如报表里先按城市分组，组内再按金额排序，基数排序天然胜任：先按金额排一趟，再按城市排一趟，由于城市排序是稳定的，组内金额顺序自然保留。换成不稳定的快排，你得额外保证分组时不能打乱顺序，写起来容易出错。
6.3 一个容易翻车的小坑：exp 溢出
如果你用 Java 处理 int 数组，条件循环不要写成 for (int exp = 1; exp <= max; exp *= base)，因为 exp 可能会在某个时刻溢出成负数，导致死循环。用 while (max / exp > 0) 这种写法更安全，我已经看到不止一个人在这上面翻车了。
基数排序就是这么个东西：入手不复杂，但很多细节需要实际操作过才能体会到。你完全可以先跑通上面的代码，然后把负数处理、base调整、字符串版本逐一加上去，慢慢就会形成自己的经验。
