O(n)的排序算法-基数排序

2019-08-30

基数排序(Radix Sort)

适用范围：将整数按位数切割成不同的数字，按每位分别比较。不只是适用整数，也适用于字符串和特定格式的浮点数等
- 最高位优先(MSD),最低位优先(LSD)
核心：(以整数为例)
- 基：被排序的元素的’个、十、百位’等
- 桶：“基”的每一位都有取值范围，一般数字是0-9共10中，10个桶

步骤：

for(每一个基) {
    // 循环内，以某一个’基‘为依据
    遍历array，将元素放入对应的桶bucket
    遍历桶bucket，将元素放回数据集
}

补充：
- 稳定排序，时间复杂度可以认为是线性的O(n)
- 更准确点讲O(d(n+radix)),radix取值范围，d表示基个数
以下写法带排序数组有负数是有问题的，如果需要排序带负数的，需要设置偏移量offset，使得最小数为0

function radixSort(arr, maxDigit) {
    let mod = 10;
    let dev = 1;
    let counter = [];
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (let j = 0; j < arr.length; j++) {
            let bucketIdx = parseInt((arr[j] % mod) / dev);
            if (counter[bucketIdx] == null) {
                counter[bucketIdx] = [];
            }

            counter[bucketIdx].push(arr[j]);
        }

        let idx = 0;
        for (let j = 0; j < counter.length; j++) {
            let bucket = counter[j];
            if (bucket != null) {
                for (let k = 0; k < bucket.length; k++) {
                    arr[idx++] = bucket[k];
                }
            }
        }

        counter = []; //清空
    }
}