基數排序(radix sort）是屬於“分配式排序”（distribution sort），基數排序又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的比較性排序法。
時間效率：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值范圍為radix，則進行鏈式基數排序的時間復雜度為O(d(n+radix))，其中，一趟分配時間復雜度為O(n)，一趟收集時間復雜度為O(radix)，共進行d趟分配和收集。
空間效率：需要2*radix個指向隊列的輔助空間，以及用於靜態鏈表的n個指針。
實現方法：最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後。再將各組連接起來，便得到一個有序序列。最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。
java代碼示例：
package com.sort.pattern;
import java.util.ArrayList;
import java.util.Arrays;
/**
* LSD基數排序
*
* @author louxuezheng 2014年4月2日
*/
public class RadixSortDemo {
public void radixSort(int[] a) {
// 1 找最大數
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
// 2 計算最大數的位數
int time = 0;
while (max > 0) {
max /= 10;
time++;
}
// 3 創建10個用於排序的桶， 每個桶中用於存放制定位數相等的數
ArrayList<ArrayList<Integer>> queue = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> subqueue = new ArrayList<Integer>();
queue.add(subqueue);
}
// 4 把數組中的數進行分配和收集
for (int i = 0; i < time; i++) {
// 根據計算的位數值放入相應的桶中
for (int j = 0; j < a.length; j++) {
int x = a[j] % (int) Math.pow(10, i + 1)
/ (int) Math.pow(10, i);
queue.get(x).add(a[j]);
}
// 對桶中數據收集排序
int count = 0;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
a[count] = queue.get(k).get(0);
queue.get(k).remove(0);
count++;
}
}
}
}
public static void main(String[] args) {
RadixSortDemo rsd = new RadixSortDemo();
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
99, 98, 54, 101, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51, 1021,
2105, 2222 };
rsd.radixSort(a);
System.out.println(Arrays.toString(a));
}
}
Java編程思想(第4版) 中文清晰PDF完整版 http://www.linuxidc.com/Linux/2014-08/105403.htm
編寫高質量代碼 改善Java程序的151個建議 PDF高清完整版 http://www.linuxidc.com/Linux/2014-06/103388.htm
Java 8簡明教程 http://www.linuxidc.com/Linux/2014-03/98754.htm
Java對象初始化順序的簡單驗證 http://www.linuxidc.com/Linux/2014-02/96220.htm
Java對象值傳遞和對象傳遞的總結 http://www.linuxidc.com/Linux/2012-12/76692.htm
