1. 前言

算法为王。

想学好前端，先练好内功，只有内功深厚者，前端之路才会走得更远。

笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。

之所以把 计数排序、桶排序、基数排序 放在一起比较，是因为它们的平均时间复杂度都为 O(n)。

因为这三个排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作 线性排序（Linear sort）。

之所以能做到线性的时间复杂度，主要原因是，这三个算法不是基于比较的排序算法，都不涉及元素之间的比较操作。

另外，请大家带着问题来阅读下文，问题：如何根据年龄给 100 万用户排序 ？

2. 桶排序（Bucket Sort）

桶排序是计数排序的升级版，也采用了分治思想。

思想

• 将要排序的数据分到有限数量的几个有序的桶里。
• 每个桶里的数据再单独进行排序（一般用插入排序或者快速排序）。
• 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

比如：

桶排序利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效，我们需要做到这两点：

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

桶排序的核心：就在于怎么把元素平均分配到每个桶里，合理的分配将大大提高排序的效率。

实现

// 桶排序 const bucketSort = (array, bucketSize) => {   if (array.length === 0) {     return array;   }    console.time('桶排序耗时');   let i = 0;   let minValue = array[0];   let maxValue = array[0];   for (i = 1; i < array.length; i++) {     if (array[i] < minValue) {       minValue = array[i]; //输入数据的最小值     } else if (array[i] > maxValue) {       maxValue = array[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 < array.length; i++) {     buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);   }    array.length = 0;   for (i = 0; i < buckets.length; i++) {     quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序     for (var j = 0; j < buckets[i].length; j++) {       array.push(buckets[i][j]);     }   }   console.timeEnd('桶排序耗时');    return array; };  // 快速排序 const quickSort = (arr, left, right) => {     let len = arr.length,         partitionIndex;     left = typeof left != 'number' ? 0 : left;     right = typeof right != 'number' ? len - 1 : right;      if (left < right) {         partitionIndex = partition(arr, left, right);         quickSort(arr, left, partitionIndex - 1);         quickSort(arr, partitionIndex + 1, right);     }     return arr; };  const partition = (arr, left, right) => {     //分区操作     let pivot = left, //设定基准值（pivot）         index = pivot + 1;     for (let i = index; i <= right; i++) {         if (arr[i] < arr[pivot]) {             swap(arr, i, index);             index++;         }     }     swap(arr, pivot, index - 1