基数排序详解

基数排序是一种非比较整数的排序算法，其排序原理是将整数按照位数切割成不同数字，然后按照每个位数分别插入k(0-9)个的新数组中，重复着行这个操作直到位数执行完。（基数排序不仅仅只用于整数数组，也可以用于浮点数、字符串、日期等）。

1.算法步骤

• 取出数组中最大的数，得到位数MaxV;
• 对数组的所有数据取最小位，分别把数组元素分别根据最小位的键值插入对应的数组中，根据键值的大小依次把数据重新插入到原来数组中。
• 重复执行步骤2的操作，直到最高位。（其中如果没有最高位的元素：补0）

2.算法演示流程

3.算法代码

var counter = [];

function baseSort(arr, maxDigit){
    var mod = 10;
    var dev = 1;

    for(var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10){
        for(var j = 0; j < arr.length; j++){
            var bucket = parse((arr[j] % mod) / dev);
            if(counter[bucket] == null){
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }

        var pos = 0;
        for(var k = 0; counter.length; j++){
            var value = null;
            if(counter[k] != null){
                while((value = counter[k].shift()) != null){
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

}