基数排序（Radix Sort）
基数排序不是一次把所有数字排好，而是按位一轮一轮排，并依赖“每一轮排序必须稳定”这个前提。
定义
基数排序是一种非比较排序算法，按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
核心思路
将整数按位数切割成不同的数字，然后按每个位数分别比较：
LSD（Least Significant Digit）：从最低位开始排序 MSD（Most Significant Digit）：从最高位开始排序
原数组: [170, 45, 75, 90, 802, 24, 2, 66]
按个位排序: [170, 90, 802, 2, 24, 45, 75, 66]
按十位排序: [802, 2, 24, 45, 66, 170, 75, 90]
按百位排序: [2, 24, 45, 66, 75, 90, 170, 802]
最终结果: [2, 24, 45, 66, 75, 90, 170, 802]
为什么稳定性是关键
按个位排完以后，十位排序必须保留个位阶段已经形成的相对次序。
如果某一轮排序不稳定，前面位数建立起来的信息就会被打乱，最后结果就不正确。
这也是为什么基数排序通常会把 计数排序 当作子过程。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(d×(n+k)) | d是位数，k是基数（通常10） |
| 空间复杂度 | O(n+k) | 需要额外的计数数组和输出数组 |
| 稳定性 | ✅ 稳定 | 使用稳定的计数排序 |
适用条件：
- 整数或可以转换为整数的数据
- 位数d不能太大
Go 代码
Go 实现
package main
import "fmt"
func countingSortByDigit(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
// 统计
for i := 0; i < n; i++ {
index := (arr[i] / exp) % 10
count[index]++
}
// 累加
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
// 构建输出数组
for i := n - 1; i >= 0; i-- {
index := (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index]--
}
// 复制回原数组
copy(arr, output)
}
func radixSort(arr []int) {
if len(arr) == 0 {
return
}
// 找最大值
maxVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
// 对每一位进行计数排序
for exp := 1; maxVal/exp > 0; exp *= 10 {
countingSortByDigit(arr, exp)
}
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println("原始数组:", arr)
radixSort(arr)
fmt.Println("排序后:", arr)
}易错点
基数排序最大的坑，不在按位取数，而在“适用条件”和“稳定子过程”。
- LSD 写法通常要求每一轮都稳定。
- 负数、变长字符串这类场景不能直接套最基础版本。
- 位数
d很大时，线性时间优势会被吃掉。 - 如果只是普通通用排序题，快排 / 归并通常更直接。
算法变体
经典题目
基础应用
字符串排序
- 根据字符出现频率排序 - LeetCode 451
数字处理
- 按位排序 - LeetCode 1356
优缺点
优点
- ✅ 线性时间：O(d×(n+k))，d较小时很快
- ✅ 稳定排序：保持相等元素的相对顺序
- ✅ 不需要比较操作
- ✅ 适合处理大量数据
缺点
- ❌ 位数限制：位数d较大时性能差
- ❌ 只适用于整数：或可转换为整数的数据
- ❌ 空间复杂度高：需要O(n+k)额外空间
- ❌ 实现复杂：比简单排序复杂
应用场景
- 整数排序：大量整数，位数不多
- 字符串排序：定长字符串
- 数据库排序：大量记录按字段排序
- 外部排序：数据量大，可以分批处理
LSD vs MSD
| 特性 | LSD | MSD |
|---|---|---|
| 排序方向 | 从低位到高位 | 从高位到低位 |
| 实现难度 | 简单 | 复杂（递归） |
| 适用场景 | 定长数据 | 不定长数据 |
| 性能 | 稳定 | 可能提前终止 |
基数排序 vs 其他排序
| 特性 | 基数排序 | 计数排序 | 快速排序 |
|---|---|---|---|
| 时间复杂度 | O(d×(n+k)) | O(n+k) | O(n log n) |
| 适用数据 | 整数/字符串 | 小范围整数 | 通用 |
| 稳定性 | 稳定 | 稳定 | 不稳定 |
| 比较排序 | 否 | 否 | 是 |