2020-01-29 桶排序

document.write("<script src='./插入排序.js'> </script>")

function bucketSort(arr, bucketSize = 5) {
  const len = arr.length
  if (len <= 1) return arr

  const buckets = createBuckets(arr, bucketSize)
  return sortBuckets(buckets)
}

function createBuckets(arr, bucketSize) {
  const len = arr.length
  let minVal = arr[0]
  let maxVal = arr[0]
  // 遍历数组，找到数组最小值与数组最大值
  for (let i = 1; i < len; i++) {
    if (arr[i] < minVal)
      minVal = arr[i]
    if (arr[i] > maxVal)
      maxVal = arr[i]
  }
  // 根据最小值、最大值、桶的大小，计算得到桶的个数
  const bucketCount = ~~((maxVal - minVal) / bucketSize) + 1
  // 建立一个二维数组，将桶放入buckets中
  const buckets = []
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = []
  }
  // 计算每一个值应该放在哪一个桶中
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = ~~((arr[i] - minVal) / bucketSize)
    buckets[bucketIndex].push(arr[i])
  }
  return buckets
}

function sortBuckets(buckets) {
  const sortedArray = []
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] != null) {
      insertionSort(buckets[i]) // 每个桶里排序，这里用了插入排序
      sortedArray.push(...buckets[i])
    }
  }
  return sortedArray
}