基數排序(Radix Sort)是在桶排序的基礎上發展而來的，兩種排序都是配置設定排序的進階實作。
配置設定排序(Distributive Sort)的基本思想：排序過程無須比較關鍵字，而是通過“配置設定”和“收集”過程來實作排序。它們的時間複雜度可達到線性階：O(n)。
基數排序代碼：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
//static int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,-3};
static int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0,32,7,159,2,83,123,321,36};
public static void main(String[] args) throws InterruptedException {
System.out.println(Arrays.toString(array));
radixSort(array);
System.out.println(Arrays.toString(array));
}
public static void radixSort(int[] array){
int max = array[0];
for(int i=0;i<array.length;i++){ //找到數組中的最大值
if(array[i]>max){
max = array[i];
}
}
int keysNum = 0; //關鍵字的個數，我們使用個位、十位、百位...當做關鍵字，是以關鍵字的個數就是最大值的位數
while(max>0){
max /= 10;
keysNum++;
}
List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<10;i++){ //每位可能的數字為0~9，是以設定10個桶
buckets.add(new ArrayList<Integer>()); //桶由ArrayList<Integer>構成
}
for(int i=0;i<keysNum;i++){ //由最次關鍵字開始，依次按照關鍵字進行配置設定
for(int j=0;j<array.length;j++){ //掃描所有數組元素，将元素配置設定到對應的桶中
//取出該元素對應第i+1位上的數字，比如258，現在要取出十位上的數字，258%100=58,58/10=5
int key =array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
buckets.get(key).add(array[j]); //将該元素放入關鍵字為key的桶中
}
//buckets内有10子bucket,根據第i+1位上的數字分别存儲在不同的bucket内
//配置設定完之後，将桶中的元素依次複制回數組
int counter = 0; //元素計數器
for(int j=0;j<10;j++){
ArrayList<Integer> bucket =buckets.get(j); //關鍵字為j的桶
while(bucket.size()>0){
array[counter++] = bucket.remove(0); //将桶中的第一個元素複制到數組，并移除
}
}
System.out.print("第"+(i+1)+"輪排序：");
display(array);
}
}
public static void display(int[] array){
for(int i=0;i<array.length;i++){
System.out.print(array[i]+"\t");
}
System.out.println();
}
} 
[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, 32, 7, 159, 2, 83, 123, 321, 36]
第1輪排序：0 1 321 2 32 2 3 83 123 4 5 6 36 7 7 8 9 159
第2輪排序：0 1 2 2 3 4 5 6 7 7 8 9 321 123 32 36 159 83
第3輪排序：0 1 2 2 3 4 5 6 7 7 8 9 32 36 83 123 159 321
[0, 1, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, 32, 36, 83, 123, 159, 321] View Code
數組中不可以有負數。
第一步判斷關鍵字的個數，這裡的關鍵字就是個，十，百，擷取最大值，就可以知道關鍵字的個數
第二步建立List數組buckets，有10個元素，每一個都是一個ArrayList類型的bucket
第三步根據關鍵字進行周遊，先根據數組array中元素的個位數的值，分别存儲到buckets中對應的bucket
第四步将buckets中的值全部指派給array,清空buckets中的每一個bucket，并根據關鍵字中的百進行下一步
第三步，第四步不停循環，直到關鍵字全部循環結束
最後即可發現數組array已經排好序。
複制的次數和資料項的個數與關鍵字長度成正比，關鍵字的長度越長，效率越低。