一、定义
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
二、算法思想
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异。
三、具体实现
按照优先从高位或低位来排序有两种实现方案:
MSD：由高位为基底，先按k1排序分组，同一组中记录键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后，再将各组连接起来，得到一个有序序列。MSD方式适用于位数多的序列。
LSD：由低位为基底，先从kd排序，再对kd-1进行排序，依次重复，直到对k1排序后，得到一个有序序列。LSD方式适用于位数少的序列。
function radixSort(arr) {var buckets = [];var max = Math.max.apply(null, arr); // 数组中的最大值var maxLength = String(max).length; // 最大数字的长度var base = 1;var unit = 10;for (var i = 0; i < maxLength; i++, base *= 10, unit *= 10) {for (var j = 0; j < arr.length; j++) {var index = parseInt((arr[j] % unit) / base);//依次过滤出个位,十位等等数字if(buckets[index] == null) {buckets[index] = [];}buckets[index].push(arr[j]);}var pos = 0;//这次循环是依次取出上面分类好的数组存放到原数组中for(var j = 0; j < buckets.length; j++) {var value = null;if(buckets[j] != null) {while ((value = buckets[j].shift()) != null) {arr[pos++] = value; //将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞 }}}}return arr; } console.log(radixSort([53,115,9,72,11,6,3,19]));
四、效率分析
基数排序更适合用于对时间，字符串等这些整体权值未知的数据进行排序。基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。
1、时间复杂度
最坏的情况：时间复杂度为O(n*k)；
最佳的情况：时间复杂度为O(n*k)；
平均来讲，时间复杂度为O(n*k)。
2、空间复杂度
空间复杂度为常量O(n+k)。
