29 lines
994 B
JavaScript
29 lines
994 B
JavaScript
function bucketSort(arr, bucketSize = 5) {
|
|
const maxVal = Math.max(...arr);
|
|
const minVal = Math.min(...arr);
|
|
|
|
const bucketCount = Math.floor((maxVal - minVal) / bucketSize) + 1; // 通过最大值和最小值计算桶子的个数
|
|
const buckets = new Array(bucketCount).fill().map(() => []);
|
|
|
|
// 将元素放入桶中
|
|
for (let i = 0; i < arr.length; i++) {
|
|
const bucketIndex = Math.floor((arr[i] - minVal) / bucketSize); // 通过当前桶判断该值应该放在哪个桶里面
|
|
buckets[bucketIndex].push(arr[i]);
|
|
}
|
|
|
|
// 在每个桶内部进行排序
|
|
for (let i = 0; i < buckets.length; i++) {
|
|
buckets[i].sort((a, b) => a - b); // 此处可以使用对小数组排序快的数组，优先选择插入排序
|
|
}
|
|
|
|
// 合并所有桶的元素
|
|
let result = [];
|
|
for (let i = 0; i < buckets.length; i++) { // 遍历所有的桶，把每个桶里面的数据放到新数组
|
|
result = result.concat(buckets[i]);
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
export default bucketSort;
|