学习回顾算法（基数排序算法）

太过爱你忘了你带给我的痛 2022-06-05 10:28 180阅读 0赞

## 基数排序概述 ##

基数排序（radix sort）属于分配式排序，又称为“桶子法”(bucket sort)或bin sort。顾名思义，它是透过键值，把要排序的元素分配到已经排好优先级的“桶”中，以达到排序的作用。比如数字中0，1，2，3，4，5，6，7，8，9。就是已经排好序的桶了。在某些时候基数排序的效率高于其他排序算法。

## 基数排序算法原理 ##

基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：  
（1）分配，先从个位开始，根据位值（0-9）分别放到0~9号桶中。  
（2）收集，将放置在0~9号桶中的数据按顺序放到数组中。

实现：  
最高位优先法（Most significant digit first）法，简称MSD法：先按K1排序，同一组中记录，关键码k1相等，再对各组按k2排序成分子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先（least significant digit）法：简称LSD法：先从kd开始排序，再对kd-1进行排序，一次重复，直到对k1排序后边得到一个有序序列。

## 算法分析 ##

**时间复杂性**  
设待排序列为N个记录，d个关键码，关键码的取值范围是radix，则进行链式基数排序的时间复杂度为：O(d（N + radix）)，其中，一趟分配时间复杂度为O(N)，一趟收集时间复杂度为O（radix），共进行d趟分配和收集。

**空间复杂度**  
需要2\*radix指向队列的辅助空间，已经用于静态链表的n个指针

**稳定性**  
要看实现，如果是使用最低位优先，基数排序是一种稳定排序算法

## 实现 ##

**1、golang实现**

package main
    
    import (
        "fmt"
    )
    
    //求数据的最大位
    func maxbit(values []int) (ret int) {
        ret = 1 //保存最大的位数
        var key int = 10
        iLen := len(values)
        for i := 0; i < iLen; i++ {
            for values[i] >= key {
                key = key * 10
                ret++
            }
        }
        return
    }
    
    func radixsort(values []int) {
        key := maxbit(values)
        iLen := len(values)
        tmp := make([]int, iLen, iLen)
        count := new([10]int)
        radix := 1
        var i, j, k int
        for i = 0; i < key; i++ { //进行key次排序
            for j = 0; j < 10; j++ {
                count[j] = 0
            }
            for j = 0; j < iLen; j++ {
                k = (values[j] / radix) % 10
                count[k]++
            }
    
            for j = 1; j < 10; j++ { //将tmp中的为准依次分配给每个桶
                count[j] = count[j-1] + count[j]
            }
            for j = iLen - 1; j >= 0; j-- {
                k = (values[j] / radix) % 10
                tmp[count[k]-1] = values[j]
                count[k]--
            }
            for j = 0; j < iLen; j++ {
                values[j] = tmp[j]
            }
            radix = radix * 10
        }
    }
    
    func main() {
        values := []int{
       2, 4, 7, 5, 8, 1, 3, 6, 6}
        fmt.Println(values)
        radixsort(values)
        fmt.Println(values)
        return
    }