Java排序算法總結（八）：基數排序
基數排序(radix sort）則是屬于“分配式排序”（distribution sort），基數排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的比較性排序法。
效率分析：
時間效率：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值范圍為radix，則進行鏈式基數排序的時間復雜度為O(d(n+radix))，其中，一趟分配時間復雜度為O(n)，一趟收集時間復雜度為O(n)，共進行d趟分配和收集。 空間效率：需要2*radix個指向隊列的輔助空間，以及用于靜態鏈表的n個指針。
實現方法：
最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。 最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序后便得到一個有序序列。
代碼實現：
- public class RadixSort {
- public static void sort(int[] number, int d) {
- int k=0;
- int n=1;
- int m=1;
- int[][] temp = new int[number.length][number.length];
- int[] order = new int[number.length];
- while(m <= d) {
- for(int i = 0; i < number.length; i++) {
- int lsd = ((number[i] / n) % 10);
- temp[lsd][order[lsd]] = number[i];
- order[lsd]++;
- }
- for(int i = 0; i < d; i++) {
- if(order[i] != 0)
- for(int j = 0; j < order[i]; j++) {
- number[k] = temp[i][j];
- k++;
- }
- order[i] = 0;
- }
- n *= 10;
- k = 0;
- m++;
- }
- }
- public static void main(String[] args) {
- int[] data =
- {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
- RadixSort.sort(data, 10);
- for(int i = 0; i < data.length; i++) {
- System.out.print(data[i] + " ");
- }
- }
基數排序一般僅是用于記錄的關鍵字為整數類型的情況。
在已介紹的各種內部排序方法中，就所需要的計算時間來看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個棧。除了快速排序、堆排序、選擇排序、希爾排序不穩定外，其它排序方法都是穩定的。
評價一個排序算法性能好壞的主要標準是它所需的計算時間和存儲空間。影響計算時間的兩個重要因素是比較關鍵字的次數和記錄的移動次數。在實際應用中，究竟應該選用何種排序方法，取決于具體的應用和機器條件。
【編輯推薦】
