javascript桶排序

in 算法 with 0 comment

桶排序的时间复杂度也是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)
评论已关闭.