個人主頁：https://chengang.plus/

文章將會同步到個人微信公眾號：Android部落格

1.1 描述

• 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
• arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；
• 對radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；

基數(shù)排序的主要思路是,將所有待比較數(shù)值(注意,必須是正整數(shù))統(tǒng)一為同樣的數(shù)位長度,數(shù)位較短的數(shù)前面補(bǔ)零. 然后, 從最低位開始, 依次進(jìn)行一次穩(wěn)定排序(我們常用上一篇blog介紹的計(jì)數(shù)排序算法, 因?yàn)槊總€位可能的取值范圍是固定的從0到9).這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列.

1.2 代碼

public static int getBite(int value,int mod){
    return (value / mod) % 10;
}

public static void radixSort(){
    int max = numbers[0];
    for(int index = 0;index < size;index++){
        if(numbers[index] > max){
            max = numbers[index];
        }
    }
    int bucketSize = 10;
    List<List<Integer>> radixList = new ArrayList<List<Integer>>();
    for(int x = 0; x < bucketSize;x++){
        radixList.add(new ArrayList<Integer>());
    }
    int maxBite = String.valueOf(max).length();
    int curMod = 1;
    for(int i = 0;i < maxBite;i++){
        for(int j = 0; j < size;j++){
            int valueIndex = getBite(numbers[j],curMod);
            List<Integer> tempList = radixList.get(valueIndex);
            tempList.add(numbers[j]);
        }
        int originIndex = 0;
        System.out.println("--------------------");
        for(int y = 0; y < bucketSize;y++){
            List<Integer> itemRadixList = radixList.get(y);
            int itemSize = itemRadixList.size();
            if(itemSize == 0){
                continue;
            }
            System.out.println("itemSize:" + itemSize);
            for(int z = 0; z < itemSize;z++){
                numbers[originIndex++] = itemRadixList.get(z);
            }
            if(i != maxBite - 1){
                itemRadixList.clear();
            }
        }
        curMod *= 10;
    }
}

public static void main(String []args) {
    radixSort();
    for(int value : numbers){
        System.out.println("count value is:" + value);
    }
}

1.3 總結(jié)

• 先選出最大值；
• 按照最大值的位數(shù)逐個遍歷數(shù)組中的元素，從低位到高位取位數(shù)上的數(shù)字，按照位數(shù)的數(shù)字放到對應(yīng)的數(shù)組序號中；
• 重復(fù)上一步一直到最高位，待遍歷完成，基本上有序，對每個數(shù)組內(nèi)的元素再做一次排序就整體有序了。

示意圖如下：

image