[ Algorithm in Java ] 排序 : 基數排序法

轉載自 這裡
前言 :
在之前所介紹過的排序方法，都是屬於「比較性」的排序法，也就是每次排序時 ，都是比較整個鍵值的大小以進行排序. 這邊所要介紹的「基數排序法」（radix sort）則是屬於「分配式排序」（distribution sort），基數排序法會使用到「桶子」（bucket），顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為 O(nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的比較性排序法!

解法 :
基數排序的方式可以採用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始. 以LSD為例，假設原來有一串數值如下所示 :

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中 :


接下來將這些桶子中的數值重新串接起來，成為以下的數列 :

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接著再進行一次分配，這次是根據十位數來分配 :


接下來將這些桶子中的數值重新串接起來，成為以下的數列 :

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止. LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式恰與LSD相反，是由高位數為基底開始進行分配，其他的演 算方式則都相同.

實作 :

- RadixSort.java :

view plaincopy to clipboardprint?

1. package alg.sort;  
2.   
3. public class RadixSort {  
4.     private static int[][] bucks;  
5.     private static int[] index = new int[10];  
6.       
7.     /** 
8.      * BD : Sort number with radix sort algorithm. 
9.      * @param number  
10.      *      The matrix to be sorted 
11.      * @param n 
12.      *      The max figure of all elements in matrix number.  
13.      */  
14.     public static void sort(int[] number, int n)  
15.     {  
16.         bucks = new int[10][number.length];  
17.           
18.         int rdx = 0;  
19.         int rst = 0;  
20.         for(int i=0; i
21.         {  
22.             /*Put into bucks*/  
23.             for(int j=0; j
24.             {  
25.                 if(i==0) rst = number[j]%10;  
26.                 else  
27.                 {  
28.                     rdx = (int)Math.pow(10, i);  
29.                     rst = (number[j]/rdx)%10;  
30.                 }  
31.                 bucks[rst][index[rst]++] = number[j];  
32.             }  
33.             /*Restore from bucks*/  
34.             int p=0;  
35.             for(int j=0; j<10; j++)  
36.             {  
37.                 for(int k=0; k
38.                 {  
39.                     System.out.printf("\t[Restore from bucks] number[%d]=%d...\n", p, bucks[j][k]);  
40.                     number[p++]=bucks[j][k];  
41.                 }  
42.                 index[j]=0;  
43.             }  
44.             System.out.println();  
45.         }  
46.     }  
47.       
48.     public static void main(String args[])  
49.     {  
50.         int numbers[] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};  
51.         RadixSort.sort(numbers, 2);  
52.         for(int i=0; i" ");  
53.     }  
54. }  

補充說明 :
* [ Data Structures with Java ] Section 15.2 : The Radix Sort

The method, called the radix sort, is a linear algorithm that uses successive digits in the elements to partially sort the array. The technique is two-stage process refereed to as transform-and-conquer...

This message was edited 6 times. Last update was at 27/10/2011 10:27:31