排序算法(九)--桶排序

桶排序的思想：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
  元素分布在桶中：
  
  元素在每个桶中排序
  

  //  默认bucketSize = 5，默认分5个桶
  var bucketSort = (arr, bucketSize = 5) => {
      if (!arr.length) return
      let min = arr[0]
      let max = arr[0]
      //  用来装桶的桶
      let list = []
      //  返回的结果
      let result = []
      //  获取数组中的最小值和最大值
      for (let i = 1; i < arr.length - 1; i++) {
          max = arr[i] <= max ? max : arr[i]
          min = arr[i] >= min ? min : arr[i]
      }
      //  桶的数量为bucketCount
      let bucketCount = (max - min)/bucketSize
      for (let a = 0; a < arr.length; a++) {
          //  获取桶的编号
          let index = Math.floor((arr[a] - min)/bucketCount)
          if (list[index]) {
              let k = list[index].length - 1
              //  对桶进行排序
              while (k >= 0 && list[index][k] > arr[a]) {
                  //  桶前面的数字放到后面去
                  list[index][k + 1] = list[index][k]
                  k--
              }
              //  不用排序的，直接加在桶的最后面
              list[index][k+1] = arr[a]
          } else {
              //  没有值则生成桶，并把值放到对应的桶中
              list[index]=[];
              list[index][0]=arr[a]
          }
      }
      let n = 0
      while (n <= bucketSize) {
          if (list[n]) {
              result = result.concat(list[n])
          }
          n++
      }
      return result
  }
  arr = [43, 25, 9, 3, 37, 25, 21, 29, 49]
  console.log(bucketSort(arr))
  //  [3, 9, 21, 25, 25, 29, 37, 43, 49]

  注：桶排序是一种思想，实际中并不常用。