桶排序 （Bucket sort）
核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
比如对 9,10,20,45,40,27,32,35,31,50,53,63进行桶排序：
桶1（0-9）: 9
桶2（10-19）: 19
桶3（20-29）: 20,27
桶4（30-39）: 32,35,31
桶5（40-49）: 45,40,
桶6（50-59）: 50,53
桶6（60-69）: 63
桶排序的时间复杂度为什么是 O(n) 呢?
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。 每个桶内部使用快速排序，时间复杂度为 O(k * logk)。 m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。
当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。
计数排序 （Counting sort）
当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
题目：数组里有20个随机数，取值范围为从0到10，要求用最快的速度把这20个整数从小到大进行排序。
1、整数的取值范围是从0到10，那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为11的数组，数组下标从0到10，元素初始值全为0
先假设20个随机整数的值是： 9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9
2、我们先遍历这个无序的随机数组，每一个整数按照其值对号入座，对应数组下标的元素进行 加1 操作。
比如第一个整数是 9，那么数组下标为 9 的元素加 1；
第二个整数是3，那么数组下标为 3 的元素加 1；
最终，数列遍历完毕时，数组的状态如下：
数值：1，2，1，3，2，2，1，2，1，4，1
下标：0，1，2，3，4，5，6，7，8，9，10，
数组中的每一个值，代表了数列中对应整数的出现次数。
3、有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
这就是计数排序的基本过程，它适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(nlogn)的排序，例如快速排序、归并排序。
局限性：
-
- 当数列最大最小值差距过大时，并不适用于计数排序；
-
- 当数列元素不是整数时，并不适用于计数排序；
JS实现
var countingSort = (arr) => {
// 数组长度
var arrLen = arr.length;
if (arrLen <= 1) {
return;
}
// 查找数组中数据的范围
let max = arr[0];
for (let i = 0; i < arrLen; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 申请一个计数数组bucket，下标大小[0,max]
var bucket = new Array(max + 1);
// 已排序的数组下标索引
var sortedIndex = 0;
var bucketLen = max + 1;
// 计算每个元素的次数，放入bucket中
for (let i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (let j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
};
More
计数排序就是这么容易
https://zhuanlan.zhihu.com/p/149725090