菜鸟学算法-9-基数排序

我想知道这是为什么 –费曼

基数排序

基数排序就是按照数字的”位”来排序。

“位“是进位的位，比如十进制的基数是 10，就可以按照个十百千万等位来排序

整体的流程分为：初始、补位、排个位、排十位、排百位、…

先按个位从小到大排序，然后再按十位、百位排序…
只要排序算法是稳定的，那么最后整体就是有序的。
为了方便看出数字每一位具体是多少，对位数少的数组进行了左边的补 0

可见算法的核心在于选择的排序算法是否是稳定的，稳定的意思是相同的元素的相对顺序不会改变

如果选择的排序算法是不稳定的，那么对一整列位数进行排序的时候很可能会影响之前已经排好序的位

在开始写算法前看一些相关的 api:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// 判断数字最长有几位，轮循数组
let array = [666, 520, 36, 49, 9, 600, 8, 502, 998, 32]
let maxLength = 0
for (let v of array) {
  let length = String(v).length
  if (length > maxLength) {
    maxLength = length
  }
}

// 根据最长的数字进行左边的补位0
String(321).padStart(maxLength, '0')

// 获取制定位上的数字
'321'[0] // '3'
'321'[1] // '2'
'321'[2] // '1'

对数组排序 maxLength 次，每一次的输出作为下一次的输入，sort 算法只要是稳定的排序算法就可以了
这里使用桶排序

个位上的数字范围是 0-9，所以需要 10 个桶

1
2
3
4


let buckets = []
for (let i = 0; i < 10; i++) {
  buckets.push([])
}

然后按个位上的数值把该元素放到不同的桶里

1
2
3
4
5
6
7
8


for (let v of array) {
  let pad = String(v).padStart(maxLength, '0')
  let bucketIndex = pad[maxLength - 1] //最后一位
  buckets[bucketIndex].push(v)
}

console.log(buckets)
// [ [ 520, 600 ], [], [ 502, 32 ], [], [], [], [ 666, 36 ], [], [ 8, 998 ], [ 49, 9 ] ]

因为桶的间隔是 1，所以不需要再排序了，直接按顺序输出每个桶的元素即可

1
2
3
4


let result = []
for (let bucket of buckets) {
  result.push(...bucket)
}

完整代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


function radioSort(array) {
  // 获取最大长度
  let maxLength = 0
  for (let v of array) {
    let length = String(v).length
    if (length > maxLength) {
      maxLength = length
    }
  }

  // 从个位开始排序
  for (let i = 0; i < maxLength; i++) {
    // 这一次的输出作为下一次的输入
    array = sort(array, i)
  }

  function sort(array, index) {
    let buckets = []
    // 0-9 10个数字分配10个桶放
    for (let i = 0; i < 10; i++) {
      buckets.push([])
    }
    for (let v of array) {
      let pad = String(v).padStart(maxLength, '0')
      let num = pad[maxLength - 1 - index] // 配合index取数字
      buckets[num].push(v) // 把数字放到对应的桶里
    }
    let result = []
    // 由于10个桶是有循序的所以轮询桶依次解构出来就行
    for (let bucket of buckets) {
      result.push(...bucket)
    }
    return result
  }

  return array
}

总结：
基数排序的性能，取决于内部排序算法的选择。如果使用桶排序，时间复杂度为 O(k*n)，其中 k 为最大元素的位数。

我创建了一个集合 jest 可以测试算法的靶场项目：
https://github.com/Llane00/algorithm-range-tests
将同步文章中的代码到这个项目下

使用 vscode 的读者可以安装拓展插件 jest，这个插件可以自动检测 test 文件自动运行，非常方便。

菜鸟学算法-9-基数排序

基数排序

相关内容