桶排序

桶排序的思路与之前提到过的排序算法的思路都不同，之前提到的排序算法都是基于数值的大小比较进行排序的，而桶排序是基于基准进行排序，因此每个基准就可以看做一个桶。

桶排序的基准的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

排序过程

举个大家都经历过的例子，某些大学会限制大一参加英语四级考试的名额，假设现在需要对大一新生的英语成绩进行排序，选取英语成绩位于前50%的学生允许参加大一上学期的英语四级考试。

一般来说一个大学的新生一般都是一万人左右，如果直接用基于比较的排序算法也不会特别的耗时间，但是通过观察可以知道的是，这些学生的成绩有个显著的特点，它们都是在[0-150]之间，也就是说，我们可以申明151个数组，每个数组（即桶）保存对应分数学生的英语成绩。最后，我们再将排序之后的数据导回至原来的数据中则完成排序。可以看到的是，由于我们的桶是远远小于数组的量级的，在排序的时候我们会使用一轮循环遍历数据，最后将排序之后的数据导回去需要一轮循环。其时间复杂度是线性的，约为O(N)（需要注意的是此处把成绩插入到对应的桶中是不需要再进行排序的，所以时间复杂度可以表示为O(N)），可以看到这个例子的算法时间复杂度是已经超过了基于比较的排序算法的。

算法实现

/**
 * 桶排序
 * @param {number[]} arr
 */
function bucketSort(arr) {
  /* 申明桶 */
  const buckets = Array.from({
    length: 151,
  }).map(() => {
    return [];
  });
  /* 按分值划分桶 */
  for (let i = 0; i < arr.length; i++) {
    const score = arr[i];
    buckets[score].push(score);
  }
  /* 将桶中的数据导回至原数组 */
  let offset = 0;
  while (buckets.length) {
    const bucket = buckets.shift();
    while (bucket.length) {
      const score = bucket.shift();
      arr[offset++] = score;
    }
  }
}

复杂度与稳定性

假设数据有N项，排序过程中分配M个桶，桶排序的平均时间复杂度为线性的 O(N+C)，其中 C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。空间复杂度为O(N+M)。