// 桶排序
// 公式
// 桶的数量 = ((最大值 - 最小值)/ 数组长度) + 1
// 元素所属桶的位置 =( 元素大小 - 最小值)/ 数组长度
function bucketSort(arr) {
let min = Math.min(...arr);
let max = Math.max(...arr);
// 代表桶的数量
let bucketSize = Math.floor((max - min) / arr.length) + 1;
// 初始化这么多个桶为一个数组
let bucketArray = new Array(bucketSize);
for (let i = 0; i < arr.length; i++) {
// 获取元素应该放置的桶的位置
const index = parseInt((arr[i] - min) / arr.length);
// 将对应元素塞入桶内
if (Array.isArray(bucketArray[index])) {
bucketArray[index].push(arr[i]);
} else {
// 初始化每个桶为一个数组
bucketArray[index] = [];
bucketArray[index].push(arr[i]);
}
}
// 对每个桶中的元素进行排序
for (let i = 0; i < bucketSize; i++) {
bucketArray.sort();
}
// 将桶数组打平(是个二维数组)
return bucketArray.flat();
}
console.log(bucketSort([1, 20, 31, 58, 46, 5, 6, 7, 21, 32, 44, 59]));
Original: https://www.cnblogs.com/beileixinqing/p/16540635.html
Author: 蓓蕾心晴
Title: 桶排序JavaScript
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/536533/
转载文章受原作者版权保护。转载请注明原作者出处!