当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
我们都经历过高考，高考查分数系统你还记得吗？我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？
考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。
根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。
我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。
因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。
分析
第一，计数排序是原地排序算法吗 ？
因为计数排序的空间复杂度为 O(k)，k 是桶的个数，所以不是原地排序算法。
第二，计数排序是稳定的排序算法吗 ？
计数排序不改变相同元素之间原本相对的顺序，因此它是稳定的排序算法。
第三，计数排序的时间复杂度是多少 ？
最佳情况：T(n) = O(n + k)
最差情况：T(n) = O(n + k)
平均情况：T(n) = O(k)
k：桶的个数。
动画
思想
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
例子
假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢 ？
这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。所以是基于位来比较的。
桶排序、计数排序能派上用场吗 ？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢 ？ 有，就是基数排序。
使用条件
要求数据可以分割独立的位来比较；
位之间由递进关系，如果 a 数据的高位比 b 数据大，那么剩下的地位就不用比较了；
每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到 O(n)。
方案
按照优先从高位或低位来排序有两种实现方案:
MSD：由高位为基底，先按 k1 排序分组，同一组中记录, 关键码 k1 相等，再对各组按 k2 排序分成子组, 之后，对后面的关键码继续这样的排序分组，直到按最次位关键码 kd 对各子组排序后，再将各组连接起来，便得到一个有序序列。MSD 方式适用于位数多的序列。
LSD：由低位为基底，先从 kd 开始排序，再对 kd - 1 进行排序，依次重复，直到对 k1 排序后便得到一个有序序列。LSD 方式适用于位数少的序列。
实现
/** * name: 基数排序 * @param array 待排序数组 * @param max 最大位数 */ const radixSort = (array, max) => { console.time('计数排序耗时'); const buckets = []; let unit = 10, base = 1; for (let i = 0; i < max; i++, base *= 10, unit *= 10) { for (let j = 0; j < array.length; j++) { let index = ~~((array[j] % unit) / base); //依次过滤出个位，十位等等数字 if (buckets[index] == null) { buckets[index] = []; //初始化桶 } buckets[index].push(array[j]); //往不同桶里添加数据 } let pos = 0, value; for (let j = 0, length = buckets.length; j < length; j++) { if (buckets[j] != null) { while ((value = buckets[j].shift()) != null) { array[pos++] = value; //将不同桶里数据挨个捞出来，为下一轮高位排序做准备，由于靠近桶底的元素排名靠前，因此从桶底先捞 } } } } console.timeEnd('计数排序耗时'); return array; };测试
const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]; console.log('原始array:', array); const newArr = radixSort(array, 2); console.log('newArr:', newArr); // 原始 array: [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] // 堆排序耗时: 0.064208984375ms // newArr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]分析
第一，基数排序是原地排序算法吗 ？
因为计数排序的空间复杂度为 O(n + k)，所以不是原地排序算法。
第二，基数排序是稳定的排序算法吗 ？
基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。