思想
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展
实现方法：将整数按位数切割成不同的数字，然后按每个位数分别比较。
image-20200324202645388.png
image-20200324202656072.png
image-20200324202703113.png
实现
function radix(array) {
let max = array[0]
for (let i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i]
}
}
let maxLength = (max + '').length //求位数, 负数要-1
let bucket = new Array(10) //定义10个桶
for (let i = 0; i < 10; i++) {
bucket[i] = [] //每个桶的长度最少要是array.length, 在js中可以不说明
}
//为了记录每个桶中实际存放了多少个数据, 我们定义一个一维数组来记录每个桶的数据个数
let bucketElementCounts = []
for (let i = 0; i < array.length; i++) {
bucketElementCounts[i] = 0
}
//存放
for (let i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (let j = 0; j < array.length; j++) {
let digitOfElement = Math.floor(array[j] / n) % 10 //取出元素的个位数
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[j]
bucketElementCounts[digitOfElement]++
}
//取出
let index = 0
for (let k = 0; k < bucketElementCounts.length; k++) {
//如果桶中有数据, 我们才放入原数组
if (bucketElementCounts[k] != 0) {
//循环第k个桶
for (let l = 0; l < bucketElementCounts[k]; l++) {
array[index++] = bucket[k][l]
}
bucketElementCounts[k] = 0 //清零供下次使用
}
}
}
}
let array = [53, 3, 542, 748, 14, 214]
radix(array)
console.log(array);
