拜托，别再问我基数排序了！！！

vlambda
2020-10-30

拜托，别再问我基数排序了！！！

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。

它的工作原理是将待排序的元素拆分为多个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第一个关键字进行稳定排序，再对第二个关键字进行稳定排序，……最后对第N关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

基数排序需要借助一种稳定算法完成内层对关键字的排序。

通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。

主要思路

将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们可以采用我们前面讲解的计数排序或者桶排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

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

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

动图演示

算法描述

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行稳定排序（比如:利用计数排序适用于小范围数的特点）

过程文字描述

假设我们有一个数组序列为: [234, 351, 456, 782, 569],以下将为我们的具体排序过程:

每次操作的元素,采用**符号包围。

第一次排序(按照个位排序)：

35*1*
78*2*
23*4*
45*6*
56*9*

第二次排序(按照十位排序)：

2*3*4
3*5*1
4*5*6
5*6*9
7*8*2

第三次排序(按照百位排序)：

*2*34
*3*45
*4*56
*5*69
*7*82

经过三次排序后，我们将得到最终的排序结果为:[234, 345, 456, 569, 782]

这里有问题就是：

为什么我们要使用稳定排序呢? 稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.

实现

依据上述的各种演示和讲解,我们按照思路还是很容易实现相关代码的。

下面是我的实现代码,可以供大家参考下:

package sort

// 获取数组的最大位数(即最大值的位数)
func getMaxBit(array []int) (bit int) {
 max := array[0]
 for _, v := range array {
  if v > max {
   max = v
  }
 }
 if max == 0 {
  return 1
 }
 for max != 0 {
  bit++
  max = max / 10
 }
 return bit
}

// 获取指定元素和指定进制位的值(x=12345,b=1,则表示获取元素120,十进制位对应的值,为2)
func getBitValue(x int, bit int) (bitValue int) {
 for i := 1; i <= bit; i++ {
  x = x / 10
 }
 bitValue = x % 10
 return bitValue
}

func RadixSort(array []int) {
 arrayLen := len(array)
 if arrayLen < 1 {
  return
 }
 //获取最大位数
 maxBit := getMaxBit(array)

 // 循环比较每一个进制位
 for i := 0; i < maxBit; i++ {
  //定义10个桶子(每个进制位的值的范围只会在0-9之间)
  var bucketArray = [10][]int{}
  for _, v := range array {
   // 获取到数组元素此时进制位的值
   bitValue := getBitValue(v, i)
   // 将该数组元素加入到对应的bucket中
   bucketArray[bitValue] = append(bucketArray[bitValue], v)
  }
  //array数组重置为依据bucket得到的最新数组
  tmpArray := make([]int, 0)
  // 遍历0-9下标的桶,每个桶存储了该进制的数值对应的数组值
  for _, bucket := range bucketArray {
   for _, v := range bucket {
    tmpArray = append(tmpArray, v)
   }
  }
  copy(array, tmpArray)
 }
 return
}

几组测试案例

数组: [329, 457, 657, 839, 436, 720, 355]

数组: [0, 23, 12345, 345, 4569, 234567, 456, 9999, 2]

“
bit值代表对不同进制位进制处理后的数组,0代表个位,1代表十位...
”

复杂度

时间复杂度

最好、最坏、平均时间复杂度：O(d*(n+k))

“
d是最大值的位数，k是进制
”

空间复杂度

O(n+k)

稳定性

基数排序是一种稳定的排序算法。

在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。

总结

借助桶编号（键）经过多次分配和采集，最终得到一个有序序列，基数排序算法独树一帜，不像之前总结的排序算法，比如冒泡排序和优化后的快速排序，选择排序和优化后的堆排序，插入排序和优化后的希尔排序，归并排序等，实质上都要基于数的比较和移动。

基数排序的缺点是不呈现时空的局部性，因为在按位对每个数进行排序的过程中，一个数的位置可能发生巨大的变化，所以不能充分利用现代机器缓存提供的优势。

同时基数排序不具有原地排序的特点，占用一定的内存空间，当内存容量比较宝贵的时候，还是有待商榷。

参阅

图解基数排序（Radix Sort）

vlambda博客
学习文章列表