基数排序

基数排序从最低位开始，逐位对整数排序，每一轮都保持稳定性。对于 d 位的数，十进制版本的时间复杂度为 O(d·n)，额外空间为 O(n + b)，其中 b 是桶数，十进制下为 10。它不比较两个完整数值的大小。

像按六位邮编整理包裹：先根据末位放入十个桶，按桶号顺序收回，再处理倒数第二位，直到处理完最高位。每次只看一位，最后却能得到完整邮编的顺序。关键在于同一个桶内保持原顺序，让前一轮的结果传到下一轮。

基数排序如何逐位排序

外层循环依次处理个位、十位、百位。最大值有 d 位，就需要 d 轮。每轮取出当前位，把数放入对应的 0–9 号桶，再按桶号从小到大收回。

这里有两个条件。

每轮必须稳定。 当前位不同，按当前位决定顺序；当前位相同，则保留前几轮按低位排出的顺序。后一轮不能打乱同桶元素，否则低位的信息就丢失了。

缺少的高位按 0 处理。 例如 8 没有十位，处理十位时进入 0 号桶。这使位数较少的非负数排在前面，不需要另写一套排序规则。

本课代码使用桶列表：十个列表，从末尾追加元素，收回时依次拼接。教材也常用计数数组与前缀和实现按位排序；两者都能保持稳定性，每轮时间都是 O(n + b)。桶列表与动画中的十个桶一一对应，便于观察放入和取出的顺序。

基数排序逐步演示

默认输入为 [35, 42, 8, 32, 12, 25]。最大值 42 有两位，所以先处理个位，再处理十位。

第一轮：个位。 按输入顺序分配：

• 35 进入 5 号桶。
• 42 进入 2 号桶。
• 8 进入 8 号桶。
• 32 进入 2 号桶，排在 42 后面。
• 12 进入 2 号桶，排在 32 后面。
• 25 进入 5 号桶，排在 35 后面。

此时 2 号桶为 [42, 32, 12]，5 号桶为 [35, 25]，8 号桶为 [8]，其余为空。按 0→9 的顺序收回，并从每个桶的前端依次取出，得到 [42, 32, 12, 35, 25, 8]。个位依次为 2、2、2、5、5、8，已经有序。

第二轮：十位。 必须处理第一轮的结果，而不是重新读取原数组：

• 42 进入 4 号桶。
• 32 进入 3 号桶。
• 12 进入 1 号桶。
• 35 进入 3 号桶，排在 32 后面。
• 25 进入 2 号桶。
• 8 的十位为 0，进入 0 号桶。

3 号桶中是 [32, 35]。这一轮没有比较 32 与 35 的完整数值，只因第一轮让 32 在前，追加操作又保留了这个顺序，结果便保持正确。

再次按 0→9 收回，得到 [8, 12, 25, 32, 35, 42]。两轮就完成了排序，没有一次比较两个完整数值谁大谁小。

时间与空间复杂度

每轮分配 n 个元素，再按 b 个桶收回，共执行 d 轮。对于固定的十进制桶数，输入是否已经有序不会改变轮数；n 和最大值的位数 d 才决定主要工作量。

当位数短且固定，O(d·n) 可以低于比较排序的 O(n log n)。这没有突破比较排序的下界，因为算法通过数位取值获取顺序信息，没有使用元素间的大小比较。

可以加载“大键值”场景 [7, 3, 9, 2, 50000]。一个五位数让整组数据都要经历五轮。后四轮中，四个小数都进入 0 号桶，仍需分配和收回。O(d·n) 表示的是每一位都要处理 n 个元素，不能省略 d。

边界情况

• 空数组：if not arr 直接返回，不求最大值，也不执行按位排序。
• 单元素数组：若最大值只有一位，只需一轮，放入桶后收回，数值不变。
• 短数与长数混合：缺少的高位按 0 处理。默认输入中的 8 就是这种情况。
• 重复值：每轮稳定分配，相等元素的原始顺序得以保留。
• 某一位全部相同：场景 [34, 31, 38, 32, 36, 35] 的十位都是 3。十位这一轮全部进入同一个桶，不改变个位排序的结果，但仍要执行一轮分配与收回。
• 负数：本课的十进制 LSD 版本只处理非负整数。负数需要处理符号，例如将绝对值排序后调整负数部分；不属于本课实现。

常见错误

• 用同一套流程从最高位开始：后续低位排序会打乱已经建立的高位顺序。MSD 基数排序是另一种算法，需要在各桶内部递归，不能直接沿用这里的平铺收回方式。
• 使用不稳定的内层排序：若第二轮把 3 号桶中的 [32, 35] 变成 [35, 32]，最后就会得到 [8, 12, 25, 35, 32, 42]。这一轮之后不会再检查个位，错误也不会自动修复。
• 写死排序轮数：固定三轮会漏掉更高数位，也会给小数增加无用轮次。应根据最大值计算轮数。
• 认为基数排序总比 O(n log n) 快：位数较多或键长变化大时，d 不能忽略。它更适合短、定长且取值有界的键，例如整数、定长字符串或日期编码。