13 基本排序算法：基数排序

基数排序

原理

基数排序属于"低位优先”排序法，通过反复进行分配与收集操作完成排序。假设记录r[i]的关键字为keyi，keyi是由d位十进制数字构成的，即keyi=Ki1 Ki2 …Kid ，则每一位可以视为一个子关键字，其中Ki1 是最高位，Kid 是最低位，每一位的值都在0≤Kij ≤9的范围内，此时基数rd=10。如果keyi是由d个英文字母构成的，即keyi=Ki1 Ki2 …Kid ，其中'a'≤Kij ≤'z'，则基数rd为26。

排序时先按最低位的值对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。依此类推，由低位到高位，每一趟都是在前一趟的基础上，根据关键字的某一位对所有记录进行排序，直至最高位，这样就完成了基数排序的全过程。

基数排序的实现步骤如下：
（1）以静态链表存储n个待排记录。
（2）按最低位关键字进行分配，把n个记录分配到rd个链队列中，每个队列中记录关键字的最低位值相等，然后再改变所有非空队列的队尾指针，令其指向下一个非空队列的队头记录，重新将rd个队列中的记录收集成一个链表。
（3）对第二低位关键字进行分配、收集……依次进行，直到对最高位关键字进行分配、收集，便可得到一个有序序列。

动画演示过程

基数排序.gif

Go语言描述

• 基数排序：桶排序的一种扩展
• 平均时间复杂度：O(k*(n+m))
• 最坏时间复杂度：O(k*(n+m))
• 最好时间复杂度：O(k*(n+m))
• 空间复杂度：O(n+m)
• 稳定性：稳定

package sort

func RadixSort(arr []int) []int {
    max := getMax(arr)
    // 数组中最大值决定了循环次数,以10为倍数增加
    for bit := 1; max/bit > 0; bit *= 10 {
        arr = bitSort(arr, bit)
        // fmt.Printf("[DEBUG] 基数:%d \t 排序:%v\t\n", bit,arr)
    }
    return arr
}


/*
对指定的位进行排序
bit 可取 1，10，100 等值
*/
func bitSort(arr []int, bit int) []int {
    n := len(arr)
    // 各个位的相同的数统计到 bitCounts[] 中
    bitCounts := make([]int, 10)
    for i := 0; i < n; i++ {
        num := (arr[i] / bit) % 10
        bitCounts[num]++
    }
    for i := 1; i < 10; i++ {
        bitCounts[i] += bitCounts[i-1]
    }

    tmp := make([]int, 10)
    for i := n - 1; i >= 0; i-- {
        num := (arr[i] / bit) % 10
        tmp[bitCounts[num]-1] = arr[i]
        bitCounts[num]--
    }
    for i := 0; i < n; i++ {
        arr[i] = tmp[i]
    }
    return arr
}

// 获取数组中最大的值
func getMax(arr []int) (max int) {
    max = arr[0]
    for _, v := range arr {
        if max < v {
            max = v
        }
    }
    return
}