代码与动画 RADIX SORT · LSD
基数排序.
从个位起按当前数位稳定分桶，再按桶号依次收集。
时间 O(d(n + 10))空间 O(n + 10)非负整数
原理与执行逻辑
按个位、十位、百位依次执行稳定分桶。每轮只处理当前数位，但稳定性会保留较低数位已经建立的顺序，最终形成完整升序。
执行步骤
- 创建十个桶，从个位开始。
- 按当前数组顺序计算数位，将元素追加到对应桶尾部。
- 从桶 0 到桶 9 依次收集，桶内顺序保持不变。
- 处理更高一位，直到覆盖最大值的全部数位。
关键理解
每轮分桶必须稳定，否则高位相同的元素可能丢失低位顺序。当前 Demo 限定非负整数，位数不足的高位视为 0。
简短示例
[21, 12, 11] 按个位收集为 [21, 11, 12]；再按十位收集为 [11, 12, 21]。
代码与执行动画
STEP 0 / 31function radixSort(values) { let a = [...values]; const max = Math.max(...a); for (let exp = 1; exp <= Math.max(1, max); exp *= 10) { const buckets = Array.from({length: 10}, () => []); for (const value of a) { const digit = Math.floor(value / exp) % 10; buckets[digit].push(value); } a = buckets.flat(); } return a;}当前数据正在操作已访问 / 命中标记 / 指针
0
准备按数位排序
上行是数组，下方是桶 0 至 9；桶内按进入顺序保存数值。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
基数排序的操作规则
演示十进制 LSD 基数排序，元素按原顺序进入桶以保持稳定性。支持 0 与重复值，最多三轮；不处理负数。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目164. 最大间距打开题目
可用基数排序后扫描相邻差值；题目要求线性时间、线性额外空间，需要处理非负整数与空桶。
- 扩展练习912. 排序数组打开题目
排序扩展练习；题目包含负数，需要增加偏移或有符号数处理。