go|Go数据结构与算法-基数排序 Go语言数据结构与算法|#

title: Go数据结构与算法-基数排序
tags: go,算法
介绍基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基本思想基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
算法复杂度时间复杂度为：O(K * N)
排序过程
假设有数组 [27 38 12 101 27 16]

[UNSORTED]:[27 38 12 101 27 16] [DEBUG bit]1 # 按个位排 [DEBUG arr][101 12 16 27 27 38] [DEBUG bit]10 # 按十位排 [DEBUG arr][101 12 16 27 27 38] [DEBUG bit]100# 按百位排 [DEBUG arr][12 16 27 27 38 101] [SORTED]:[12 16 27 27 38 101]

实用场景 【go|Go数据结构与算法-基数排序】待比较的元素必须是“可取基数的”。时间复杂度低（k 因子一般不高），但基数排序的空间复杂度高，内存开销较大。总体上来说，使用范围比较窄。
演示

package mainimport ( "algorithms" "fmt" )func main() { arr := algorithms.GetArr(5, 1000) //arr = []int{27, 38, 12, 101, 27, 16} fmt.Println("[UNSORTED]:\t", arr) fmt.Println("[SORTED]:\t", radixSort(arr)) }func radixSort(arr []int) []int { max := getMax(arr) // 数组中最大值决定了循环次数，101 循环三次 for bit := 1; max/bit > 0; bit *= 10 { arr = bitSort(arr, bit) fmt.Println("[DEBUG bit]\t", bit) fmt.Println("[DEBUG arr]\t", 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 }