0322.md

桶排序

取 n 个桶，根据数组的最大值和最小值确认每个桶存放的数的区间，将数组元素插入到相应的桶里，最后再合并各个桶。

• 最好： O(n)，每个数都在分布在一个桶里，这样就不用将数插入排序到桶里了(类似于计数排序以空间换时间)。
• 最坏： O(n²)，所有的数都分布在一个桶里。
• 平均： O(n + k)，k表示桶的个数。

function bucketSort(nums) {
  if (!Array.isArray(nums)) {
    return new TypeError('not a array');
  }
  if (nums.length < 2) {
    return nums;
  }
  // 桶的个数，只要是正数即可
  let num = 5;
  let max = Math.max(...nums);
  let min = Math.min(...nums);
  // 计算每个桶存放的数值范围，至少为1，
  let range = Math.ceil((max - min) / num) || 1;
  // 创建二维数组，第一维表示第几个桶，第二维表示该桶里存放的数
  let array = Array.from(Array(num)).map(() => Array().fill(0));
  nums.forEach(val => {
    // 计算元素应该分布在哪个桶
    let index = parseInt((val - min) / range);
    // 防止index越界，例如当[5,1,1,2,0,0]时index会出现5
    index = index >= num ? num - 1 : index;
    let temp = array[index];
    // 防止index越界，例如当[5,1,1,2,0,0]时index会出现5
    let j = temp.length - 1;
    while (j > 0 && val < temp[j]) {
      temp[j + 1] = temp[j];
      j--;
    }
    temp[j + 1] = val;
  });
  // 修改回原数组
  let res = [].concat.apply([], array);
  nums.forEach((val, i) => {
    nums[i] = res[i];
  });
}