桶排序的时间复杂度也是O(n), 空间复杂度也为O(n), 是线性排序,它是一种稳定排序(前提:每个桶内使用稳定的排序算法) ,它是为了解决计数排序的问题而出现的,计数排序当最大值与最小值差距太大时, 还有待排列的数是小数时都是无能为力的
桶排序分为以下步骤
1:确定这个序列要分为几个桶
2:把每个元素放到对应的桶里面(关键)
3:对每个桶进行排序
4:对所有的桶进行整合
桶排序实现
function bucketSort(arr) {
//找出数组的最大值与最小值
let maxVal = Math.max(...arr)
let minVal = Math.min(...arr)
//构造的桶的数量
let bucketNum = arr.length - 1
//数组中每个元素放的位置
let bucket = []
//构造桶(数组表示)
for(let i = 0; i < bucketNum; i++) {
bucket[i] = []
}
//遍历arr把每个元素放到对应的桶内
for(let i = 0; i < arr.length; i++) {
//关键点:算出当前元素要放到哪个桶内,(当前值 - 最小值)*(桶的数量 - 1) / (maxVal - minVal)
let index = Math.floor((arr[i] - minVal)*(bucketNum - 1) / (maxVal - minVal))
bucket[index].push(arr[i])
}
for(let i = 0; i < bucketNum; i++) {
//对每个桶进行排序,这里要使用稳定排序算法才行
bucket[i].sort(function(num1, num2){
if(num1 > num2) {
return 1
}else if(num1 < num2){
return -1
}else{
return 0
}
})
//console.log(bucket[i])
}
//把桶内排序好的元素都放result里
let result = []
for(let j = 0; j < bucketNum; j++) {
for(let k = 0; k < bucket[j].length; k++) {
result.push(bucket[j][k])
}
}
return result
}
const bucketSortArr = [4.5, 0.84, 3.25, 2.18, 0.5, 0.3]
let res = bucketSort(bucketSortArr)
console.log(res)
本文由 dealdot <dealdot#163.com> 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 22, 2021 at 17:16 pm
转载请注明来源