4.1.9.1 基数排序
将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。
然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
分类 排序算法
数据结构 数组
最坏时间复杂度 O(kN)
最坏空间复杂度 O(k+N)
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
1.基数排序：根据键值的每位数字来分配桶
2.计数排序：每个桶只存储单一键值
3.桶排序：每个桶存储一定范围的数值
Array.prototype.radixSort = function() {
let arr = this.slice(0)
const max = Math.max(...arr)
let digit = `${max}`.length
let start = 1
let buckets = []
while(digit > 0) {
start *= 10
for(let i = 0; i < arr.length; i++) {
const index = arr[i] % start
!buckets[index] && (buckets[index] = [])
buckets[index].push(arr[i])
}
arr = []
for(let i = 0; i < buckets.length; i++) {
buckets[i] && (arr = arr.concat(buckets[i]))
}
buckets = []
digit --
}
return arr
}
const arr = [1, 10, 100, 1000, 98, 67, 3, 28, 67, 888, 777]
console.log(arr.radixSort())
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
- 实现思想
/ LSD Radix Sort
// 比较整型
var counter = [];
// 定义一个函数 arr待排序数组 maxDigit数组中最大数的位数，例如[1,10,100]的maxDigit为3
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 把待排序的数组 arr 中的每一位整数，插入对应的容器
for(var j = 0; j < arr.length; j++) {
// 从个位开始，得到数组中每个数的每一位并保存在 bucket 变量中
// bucket 变量的值可能为 0 1 2 3 4 5 6 7 8 9
// 与之对应的 counter[bucket] 容器为 0 1 2 3 4 5 6 7 8 9
var bucket = parseInt((arr[j] % mod) / dev);
// 如果目前 bucket 变量的值对应的 counter[bucket] 容器还不存在（未初始化），则创建（初始化）一个新的空容器
if(counter[bucket]==null) {
counter[bucket] = [];
}
// 现在把这个 bucket 变量的值插入对应的 counter[bucket] 容器的尾部
counter[bucket].push(arr[j]);
}
// 把 counter[bucket] 容器里的数依次取出
var pos = 0;
for(var j = 0; j < counter.length; j++) {
// 定义一个变量 value 用于保存conter[j].shift
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
console.log(radixSort([99,15,48,75,46,37,90,100],3));
// 第一步
0 90 100
1
2
3
4
5 15 75
6 46
7 37
8 48
9 99
=> 90 100 15 75 46 37 48 99
--------------------------------------
1.取末尾 按照对应的末尾数字排序 |
100 75 |
90 15 46 37 48 99 |
0 1 2 3 4 5 6 7 8 9 |
--------------------------------------
// 第二步
0 100
1 15
2
3 37
4 46 48
5
6
7 75
8
9 90 99
=> 100 15 37 46 48 75 90 99
--------------------------------------------------------------------
2.原排序进一位，原来开始最低位是个位，进一位就是十位， 按照对应的十位数字排序 |
48 99 |
100 15 37 46 75 90 |
0 1 2 3 4 5 6 7 8 9 |
-------------------------------------------------------------------
// 第三步
0 15 37 46 48 75 90 99
1 100
2
3
4
5
6
7
8
9
=> 15 37 46 48 75 90 99 100
--------------------------------------------------------------------
3.排序再进一位，上一次是十位，进一位就是百位，原来的两位数字补0，如 15--> 015 按照对应的百位数字排序 |
99
90
75
48
46
37 |
15 100 |
0 1 2 3 4 5 6 7 8 9 |
-------------------------------------------------------------------
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119