/**
* 基数排序 O(d(n+radix))
* radix 基数 d为堆数
*
* @param {any} arr
* @param {any} radix 基数
* @returns
*
* @memberof sort
*/
sort8(arr, radix) {
let max = this.findMax(arr, radix); // 找出堆数
console.log(max);
for(let i = 1;i <= max;i++) {
this.buildBy(arr, i, radix);
}
return arr;
}
/**
* 找出堆数
*
* @param {any} arr
* @param {any} radix 基数
* @returns 堆数
*
* @memberof sort
*/
findMax(arr, radix) {
let max = 1;
let len = arr.length;
for (let i = 0; i < len;i++) {
while(Math.floor(arr[i] / (radix** (max- 1))) > 1) {
max++;
}
}
return max;
}
/**
* 分桶排序
*
* @param {any} arr
* @param {any} index 当前桶
* @param {any} radix 基数
*
* @memberof sort
*/
buildBy(arr, index, radix) {
let bockets = new Array(radix);
for (let i = 0;i < radix;i++) {
bockets[i] = [];
}
for (let i = 0;i < arr.length;i++) {
let remainder = Math.floor(arr[i] / (radix ** (index - 1))) % radix;
bockets[remainder].push(arr[i]);
}
var temp = 0;
for (let i = 0;i < bockets.length;i++) {
for (let j = 0;j< bockets[i].length;j++) {
arr[temp] = bockets[i][j];
temp++
}
}
}
