# 解题思路 or 实现原理
桶排序是计数排序的升级版。它利用了函数的映射关系, 高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效, 我们需要做到这两点:
- 在额外空间充足的情况下, 尽量增大桶的数量
- 使用的映射函数能够将输入的
N个数据均匀的分配到K个桶中
同时, 对于桶中元素的排序, 选择何种比较排序算法对于性能的影响至关重要。
- 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。
- 什么时候最慢 当输入的数据被分配到了同一个桶中。
# 算法步骤
# 实现代码
/*
* @Author: Rainy
* @Date: 2019-11-14 19:25:01
* @LastEditors: Rainy
* @LastEditTime: 2019-12-01 11:59:42
*/
import { NumberArrayMap } from 'types';
export function radixSort(
arr: NumberArrayMap,
maxDigit: number
): NumberArrayMap {
let counter: any = [];
let mod = 10;
let dev = 1;
for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for (let j = 0; j < arr.length; j++) {
let bucket = parseInt(((arr[j] % mod) / dev) + '', 10);
if (counter[bucket] == null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
let pos = 0;
for (let j = 0; j < counter.length; j++) {
let value = null;
if (counter[j] != null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = +value;
}
}
}
}
return arr;
}
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
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
# 参考
Data Structure Visualizations: BucketSort (opens new window)