桶排序

[myLightLin]

简介

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O（n²）	√
快排、归并、希尔、堆	O（nlogn）	√
桶、计数、基数	O（n）	×

顾名思义，将数据按照某种特征分到几个桶里，然后再对这几个桶的数据进行排序，最后取出来的数据，就是有序的。

代码

function bucketSort(arr, bucketSize = 5) {
  if (arr.length < 2) return arr
  
  const buckets = createBuckets(arr, bucketSize)
  return sortBuckets(buckets)
}

function createBuckets(arr, bucketSize) {
  let minValue = arr[0]
  let maxValue = arr[0]
  // 找最小值和最大值
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i]
    } else if (arr[i] > maxValue) {
      maxValue = arr[i]
    }
  }
  // 根据最小值，最大值，桶的大小计算桶的个数
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
  const buckets = Array.from({length: bucketCount}, _ => [])
  // 计算每个值应该放在哪个桶
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize)
    buckets[bucketIndex].push(arr[i])
  }
  return buckets
}

function sortBuckets(buckets) {
  const res = []
  for (let i = 0; i < buckets.length; i++) {
    buckets[i].sort((a, b) => a - b)
  }
  let index = 0
  for (let i = 0; i < buckets.length; i++) {
    for (let j = 0; j < buckets[i].length; j++) {
      res[index++] = buckets[i][j]
    }
  }
  return res
}
// 假设数据是 0 ~ 50 的订单金额
const arr = [22, 5, 11, 41, 45, 26, 29, 10, 7, 8, 30, 27, 42, 43, 40]
bucketSort(arr, 5)  // [5, 7, 8, 10, 11, 22, 26, 27, 29, 30, 40, 41, 42, 43, 45]

ES6 代码

function bucketSort(arr, size = 5) {
  const min = Math.min(...arr)
  const max = Math.max(...arr)
  const buckets = Array.from(
  	{length: Math.floor((max - min) / size) + 1},
    () => []
  )
  arr.forEach(val => {
    buckets[Math.floor((val - min) / size)].push(val)
  })
  return buckets.reduce((acc, b) => [...acc, ...b.sort((a, b) => a - b)], [])
}
// 假设数据是 0 ~ 50 的订单金额
const arr = [22, 5, 11, 41, 45, 26, 29, 10, 7, 8, 30, 27, 42, 43, 40]
bucketSort(arr, 5)  // [5, 7, 8, 10, 11, 22, 26, 27, 29, 30, 40, 41, 42, 43, 45]

总结

1. 时间复杂度 O（n）,空间复杂度 O（n + k）
2. 对数据要求比较苛刻，比较适合用在外部排序中，即磁盘外