基数排序

概述

基数排序，一般是从右到左，对进制位上的数字进行比较，存入[0, 9]的10个桶中，进行排序。
从低位开始比较，逐位进行比较，让每个进制位（个、十、百、千、万）上的数字，都能放入对应的桶中，形成局部有序。

为什么10个桶？

因为十进制数，是由0-9数字组成，对应的进制位上的数字，都会落在这个区间内，所以是10个桶。

基数排序有两种方式：

MSD 从高位开始进行排序
LSD 从低位开始进行排序

效果图

解法

caution

当前解法，只适用正整数的场景。
负数场景，需要加上偏移量解决。可参考计数排序的解法。

function radixSort(arr){
    let maxNum = arr[0];

    // 求出最大的数字，用于确定最大进制位
    arr.forEach(num => {
        if(num > maxNum){
            maxNum = num;
        }
    });

    // 获取最大数字有几位
    let maxDigitNum = 0;
    while(maxNum > 0){
        maxNum = Math.floor(maxNum / 10);
        maxDigitNum++;
    }

    // 对每个进制位上的数进行排序
    for(let i = 0; i < maxDigitNum; i++){
        let buckets = new Array(10).fill(0).map(() => []); // 初始化10个桶
        for(let k = 0; k < arr.length; k++){
            const bucketIndex = getDigitNum(arr[k], i); // 获取当前进制位上的数字
            buckets[bucketIndex].push(arr[k]); // 排序的数字放入对应桶中
        }
        // 所有数字放入桶中后，现从0-9的顺序将桶中的数字取出
        const res = [];
        buckets.forEach(store => {
            store.forEach(num => {
                res.push(num); // 注意这里，先存入桶中的数字，先取出，这样才能保持局部有序
            })
        });
        
        arr = res;
    }


    return arr;


    /** 
        求出数字每个进制位上的数字，只支持正整数
        @param num 整数
        @param digit 位数，从0开始
    */
    function getDigitNum(num, digit){
        return Math.floor(num / Math.pow(10, digit) % 10)
    }
}

参考

JAVA十大排序算法之基数排序详解

概述​

效果图​

解法​

caution

参考​

概述

效果图

解法

参考