如果要排序的数据有 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)。
最佳情况：T(n) = O(n)。当输入的数据可以均匀的分配到每一个桶中。
最差情况：T(n) = O(nlogn)。当输入的数据被分配到了同一个桶中。
平均情况：T(n) = O(n)。
桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。
很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
适用场景
桶排序比较适合用在外部排序中。
外部排序就是数据存储在外部磁盘且数据量大，但内存有限，无法将整个数据全部加载到内存中。
动画
思想
找出待排序的数组中最大和最小的元素。
统计数组中每个值为 i 的元素出现的次数，存入新数组 countArr 的第 i 项。
对所有的计数累加（从 countArr 中的第一个元素开始，每一项和前一项相加）。
反向填充目标数组：将每个元素 i 放在新数组的第 countArr[i] 项，每放一个元素就将 countArr[i] 减去 1 。
关键在于理解最后反向填充时的操作。
使用条件
只能用在数据范围不大的场景中，若数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序。
计数排序只能给非负整数排序，其他类型需要在不改变相对大小情况下，转换为非负整数。
比如如果考试成绩精确到小数后一位，就需要将所有分数乘以 10，转换为整数。
实现
方法一：
const countingSort = array => { let len = array.length, result = [], countArr = [], min = (max = array[0]); console.time('计数排序耗时'); for (let i = 0; i < len; i++) { // 获取最小，最大 值 min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; countArr[array[i]] = countArr[array[i]] ? countArr[array[i]] + 1 : 1; } console.log('countArr :', countArr); // 从最小值 -> 最大值,将计数逐项相加 for (let j = min; j < max; j++) { countArr[j + 1] = (countArr[j + 1] || 0) + (countArr[j] || 0); } console.log('countArr 2:', countArr); // countArr 中,下标为 array 数值，数据为 array 数值出现次数；反向填充数据进入 result 数据 for (let k = len - 1; k >= 0; k--) { // result[位置] = array 数据 result[countArr[array[k]] - 1] = array[k]; // 减少 countArr 数组中保存的计数 countArr[array[k]]--; // console.log("array[k]:", array[k], 'countArr[array[k]] :', countArr[array[k]],) console.log('result:', result); } console.timeEnd('计数排序耗时'); return result; };测试
const array = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]; console.log('原始 array: ', array); const newArr = countingSort(array); console.log('newArr: ', newArr); // 原始 array: [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2] // 计数排序耗时: 5.6708984375ms // newArr: [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]方法二：
const countingSort2 = (arr, maxValue) => { console.time('计数排序耗时'); maxValue = maxValue || arr.length; let bucket = new Array(maxValue + 1), sortedIndex = 0; (arrLen = arr.length), (bucketLen = maxValue + 1); 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]--; } } console.timeEnd('计数排序耗时'); return arr; };测试
const array2 = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]; console.log('原始 array2: ', array2); const newArr2 = countingSort2(array2, 21); console.log('newArr2: ', newArr2); // 原始 array: [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2] // 计数排序耗时: 0.043212890625ms // newArr: [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]例子
可以认为，计数排序其实是桶排序的一种特殊情况。