桶排序

桶排序的工作原理是将数组分到有限数量的桶子里。每个桶子再个别排序 (有可能再使用别的排序算法或以递归方式继续使用桶排序进行排序)。桶排序利用了函数的映射关系，高效与否的关键在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到以下两点：

1. 在额外空间充足的情况下，尽量增大桶的数量；
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；

什么时候最快

当输入的数据可以均匀的分配到每一个桶中，桶排序的时间复杂度是 O(n)。

什么时候最慢

当输入的数据被分到了同一个桶中。

示意图

元素分布在桶中：

然后，元素在每个桶中排序：

JavaScript代码实现

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) return arr;
  let i;
  let minValue = arr[0]; // 将最小值初始化为数组的第一个元素
  let maxValue = arr[0]; // 将最大值初始化为数组的第一个元素
  for (i = 1; i < arr.length: i++) {
      if (arr[i] < minValue) {
        minValue = arr[i];                                // 找出数据中的最小值
    } else if (arr[i] > maxValue) {
        maxValue = arr[i];                                // 找出数据中的最大值
    }
  }
  // 桶的初始化
  const DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为 5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
      buckets[i] = [];
  }
  // 利用映射关系将数据分配到各个桶中
  for (i = 0; i < arr.length; i++) {
       buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); 
  }
  arr.length = 0;
  for (i = 0; i < buckets.length; i++) {
      insertionSort(buckets[i]);
    for (let j = 0; j < buckets[i].length; j++) {
        arr.push(buckets[i][j]);
    }
  }
  return arr;
}