基数排序

基数排序(Radix sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法原理

基数排序的算法原理：

  • 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

  • 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

LSD 基数排序动图演示:

基数排序 - 图1

基数排序算法实现:

  2. func main() {
  3.     array := []int{12, 3, 8, 5, 9, 11, 23, 36,20,28,21}
  4.     fmt.Println("before radixSort:",array)
  6.     radixSort(array)
  7.     fmt.Println("after radixSort:",array)
  8. }
  10. //获取数组的最大值
  11. func maxValue(arr []int) (ret int) {
  12.     ret = 1 
  13.     var key int = 10
  14.     for i := 0; i < len(arr); i++ {
  15.         for arr[i] >= key {
  16.             key = key * 10
  17.             ret++
  18.         }
  19.     }
  20.     return
  21. }
  23. func radixSort(arr []int) {
  24.     key := maxValue(arr)
  25.     tmp := make([]int, len(arr), len(arr))
  26.     count := new([10]int)
  27.     radix := 1
  28.     var i, j, k int
  29.     for i = 0; i < key; i++ { //进行key次排序
  30.         for j = 0; j < 10; j++ {
  31.             count[j] = 0
  32.         }
  33.         for j = 0; j < len(arr); j++ {
  34.             k = (arr[j] / radix) % 10
  35.             count[k]++
  36.         }
  38.         for j = 1; j < 10; j++ { //将tmp中的为准依次分配给每个桶
  39.             count[j] = count[j-1] + count[j]
  40.         }
  41.         for j = len(arr) - 1; j >= 0; j-- {
  42.             k = (arr[j] / radix) % 10
  43.             tmp[count[k]-1] = arr[j]
  44.             count[k]--
  45.         }
  46.         for j = 0; j <len(arr); j++ {
  47.             arr[j] = tmp[j]
  48.         }
  49.         radix = radix * 10
  50.     }
  51. }

运行结果:

  1. before radixSort: [12 3 8 5 9 11 23 36 20 28 21]
  3. after radixSort: [3 5 8 9 11 12 20 21 23 28 36]