算法为王。
想学好前端，先练好内功，只有内功深厚者，前端之路才会走得更远。
笔者写的 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); return index - 1; }; const swap = (arr, i, j) => { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; };测试
const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]; console.log('原始array:', array); const newArr = bucketSort(array); console.log('newArr:', newArr); // 原始 array: [4, 6, 8, 5, 9, 1, 2, 5, 3, 2] // 堆排序耗时: 0.133056640625ms // newArr: [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]分析
第一，桶排序是原地排序算法吗 ？
因为桶排序的空间复杂度，也即内存消耗为 O(n)，所以不是原地排序算法。
第二，桶排序是稳定的排序算法吗 ？
取决于每个桶的排序方式，比如：快排就不稳定，归并就稳定。
第三，桶排序的时间复杂度是多少 ？
因为桶内部的排序可以有多种方法，是会对桶排序的时间复杂度产生很重大的影响。所以，桶排序的时间复杂度可以是多种情况的。
总的来说
最佳情况：当输入的数据可以均匀的分配到每一个桶中。
最差情况：当输入的数据被分配到了同一个桶中。
以下是桶的内部排序为快速排序的情况：