001什么是基數排序？

1）基數排序是對桶排序的一種改進，這種改進是讓“桶排序”適合于更大的元素值集合的情況，而不是提高性能。它的基本思想是：將整數按位數切割成不同的數字，然后按每個位數分別比較。

2）算法圖解

第一步，將所有待比較數值根據個位數的數值分別分配至編號0到9的桶中；

第二步，桶中數據根據先進先出的原則出來，收集完整的序列；

第三步，十位、百位....周而復始

002基數排序的代碼實現？

//digit代表最大的數有幾個十進制位
public static void radixSort(int[] arr, int L, int R, int digit) {
    //十進制數
    final int radix = 10;
    int i = 0, j = 0;
    // 有多少個數準備多少個輔助空間
    int[] bucket = new int[R - L + 1];
    for (int d = 1; d <= digit; d++) { // 有多少位就循環幾次
        //十進制的數，創建長度為10的數組
        int[] count = new int[radix]; // count[0..9]
        for (i = L; i <= R; i++) {
            j = getDigit(arr[i], d);//獲取該數的個位、十位、百位......上的數
            count[j]++;//獲取數組中每個數每位分別是1、2、3....9數分別總共有幾個
        }
        for (i = 1; i < radix; i++) {
            //獲取數組中每個數每位分別是<=1、<=2、<=3....<=9數分別總共有幾個
            count[i] = count[i] + count[i - 1];
        }
        for (i = R; i >= L; i--) {
            j = getDigit(arr[i], d);//獲取該數的個位、十位、百位......上的數
            bucket[count[j] - 1] = arr[i];//將數放回到輔助空間
            count[j]--;
        }
        for (i = L, j = 0; i <= R; i++, j++) {
            arr[i] = bucket[j];
        }
    }
}
//獲取該數的個位、十位、百位......上的數	
public static int getDigit(int x, int d) {		
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}