什么是基数排序
基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
以数组 [53, 3, 542, 748, 14, 214] 为例，使用基数排序进行升序排序：
第一轮排序后：542、53、3、14、214、748
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ │ │ 542 │ 53 │ 14 │ │ │ │ 748 │ │
│ │ │ │ 3 │ 214 │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
第二轮排序后：3、14、214、542、748、53
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 3 │ 14 │ │ │ 542 │ 53 │ │ │ │ │
│ │ 214 │ │ │ 748 │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
第三轮排序后：3、14、53、214、542、748
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 3 │ │ 214 │ │ │ 542 │ │ 748 │ │ │
│ 14 │ │ │ │ │ │ │ │ │ │
│ 53 │ │ │ │ │ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
kotlin 实现
fun radixSort(nums: IntArray) {
val max = nums.maxOrNull() ?: return
var exp = 1 // 当前位数，1表示个位，10表示十位，100表示百位……
val count = IntArray(10) // 0-9 10个桶
val output = IntArray(nums.size)
while (max / exp > 0) {
count.fill(0)
// 统计每个位的出现次数
for (n in nums) {
val digit = (n / exp) % 10
count[digit]++
}
// 累加 count，转换成“位置数组”
for (i in 1 until 10) {
count[i] += count[i - 1]
}
// 从后往前遍历，保持稳定性
for (i in nums.lastIndex downTo 0) {
val digit = (nums[i] / exp) % 10
output[count[digit] - 1] = nums[i]
count[digit]--
}
// 拷贝回原数组
output.copyInto(nums)
exp *= 10
}
}
fun main() {
val arr = intArrayOf(53, 3, 542, 748, 14, 214)
radixSort(arr)
println(arr.joinToString())
}
复杂度
时间复杂度
基数排序的时间复杂度是 O(k⋅n)，其中 n 是排序元素个数，k 是数字位数，
k 决定了进行多少轮处理，而 n 是每轮处理的操作数目。
基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小。
空间复杂度
O(n + k)，其中 n 是排序元素个数，k 是计数桶数组 size。
最后，Radix Sort 是稳定排序算法（如果两个元素值相同，排序后它们的相对顺序不会改变）。 适合大量整数数据排序，尤其是范围不大、位数少的场景。