基数排序

Posted on By ᵇᵒ

什么是基数排序

基数排序(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 是稳定排序算法(如果两个元素值相同,排序后它们的相对顺序不会改变)。 适合大量整数数据排序,尤其是范围不大、位数少的场景。