[ 資料結構 小學堂 ] 排序 : 基數排序法

前言 : 
基數排序法 (Radix Sort) 和我們之前所討論過的排序法不太一樣, 它並不需要進行元素間的比較動作, 而是屬於一種分配模式排序方式. 基數排序法依比較的方向可分為最有效鍵優先 (Most Significant Digit First, MSD) 和最無效鍵優先 (Least Significant Digit First, LSD) 兩種. MSD 法是從最左邊的位數開始比較, 而 LSD 則是從最右邊的位數開始比較. 

LSD 排序說明 : 
底下範例我們以 LSD 將三位數的整數資料加以排序, 它是依個位數, 十位數, 百位數來進行排序. 考慮原始資料 : 
26 95 7 34 60 168 171 259 372 45 88 133 

步驟一 : 把每個整數依其個位數放到串列中 
 
合併後成為 : 60 171 372 133 34 95 45 7 168 88 59 259 

步驟二 : 再依其十位數字, 依序放到串列中 

0:[7]
1:[]
2:[]
3:[133, 34]
4:[45]
5:[59, 259]
6:[60, 168]
7:[171, 372]
8:[88]
9:[95]

合併後成為 : 7 133 34 45 59 259 60 168 171 372 88 95 

步驟三 : 再依其百位數, 依序放到串列中 
 
合併後即完成排序 : 7 34 45 59 60 88 95 133 168 171 259 372 

基數排序演算法分析 : 

1. 在所有情況下, 時間複雜度均為 O(nlogpk), k 是原始資料的最大值.
2. 基數排序法是穩定排序法.
3. 基數排序法會使用到很大的額外空間來存放串列資料, 其空間複雜度為 O(n*p), n 是原始資料的個數, p 是資料字元數 ; 如上例資料個數n=12, 字元數p=3.
4. 若n 很大, p 固定或很少, 此排序法將會很有效率.

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. #include   
3.   
4. using namespace std;  
5.   
6. struct BenchMark {  
7.     int swapTime;  // Swap Time  
8.     int verifyTime;  // Verify Time  
9.     double cTime;  // Consumed Time  
10. };  
11. BenchMark radixSort(int data[], int size) {  
12.     BenchMark bm;  
13.     bm.swapTime = 0;  
14.     bm.verifyTime = 0;    
15.     int vt=0, st=0;  
16.     for(int n=1; n<=100; n=n*10) {  
17.         int tmp[10][20] = {-1};  
18.         for(int i=0; i
19.             int m = (data[i]/n)%10;  
20.             tmp[m][i] = data[i];  
21.             vt++;  
22.         }  
23.         int k=0;  
24.         for(int i=0; i<10; i++) {  
25.             for(int j=0; j
26.                 vt++;  
27.                 if(tmp[i][j] >0) {                     
28.                     data[k] = tmp[i][j];  
29.                     k++;  
30.                 }  
31.             }  
32.         }  
33.     }  
34.     bm.verifyTime = vt;  
35.     bm.swapTime = st;  
36.     return bm;  
37. }  
38. #define RADIX_DATA_SIZE 20  
39. void main(bool b) {  
40.     if(b) {  
41.         int data[RADIX_DATA_SIZE] = {32, 17, 113, 24, 35, 87, 65, 4, 12, 129, 32, 166, 78, 231, 329, 53, 71, 98, 45, 24};  
42.         printf("原始資料為: ");  
43.         _showData(data, RADIX_DATA_SIZE);  
44.         BenchMark bm = radixSort(data, RADIX_DATA_SIZE);  
45.         cout << "基數排序: " << endl;  
46.         _showData(data, RADIX_DATA_SIZE);  
47.         printf("Swap time: %d\n", bm.swapTime);  
48.         printf("Verify time: %d\n", bm.verifyTime);  
49.     }  
50. }  

執行結果 : 

原始資料為: 32 17 113 24 35 87 65 4 12 129 32 166 78 231 329 53 71 98 45 24
基數排序:
4 12 17 24 24 32 32 35 45 53 65 71 78 87 98 113 129 166 231 329
Swap time: 0
Verify time: 660

Ruby Sample Code : 

- alg/sort/SortMod.rb

view plaincopy to clipboardprint?

1. module SortMod    
2.   @@des_cmp = lambda{ |a,b| return a <=> b}  
3.   @@asc_cmp = lambda{ |a,b| return b <=> a}  
4.     
5.   # Open API: Sorting given array.  
6.   def sort(ary, desc=true)  
7.     nary = []  
8.     ary.each{ |item|; nary << item; }  
9.     csort(nary, desc ? @@des_cmp : @@asc_cmp)      
10.   end  
11.     
12.   # Customized sorting algorithm.  
13.   def csort(ary, cmp)  
14.     raise RuntimeError, "Muse implement method!"  
15.   end  
16.     
17.   # Swap ary[i] with ary[j]  
18.   def swap(ary, i, j)  
19.     ary[i], ary[j] = ary[j], ary[i]  
20.   end  
21.     
22.   # Open API: In place sorting on given array  
23.   def sort?(ary, cmp, desc=true)      
24.     csort(ary, cmp, desc ? @@des_cmp : @@asc_cmp)  
25.     cmp  
26.   end  
27.     
28.   public :sort, :sort?  
29.   protected :csort, :swap    
30. end  

- alg/sort/RadixSort.rb

view plaincopy to clipboardprint?

1. require "alg/sort/SortMod"  
2.   
3. class RadixSort  
4.   # http://localhost/jforum/posts/list/969.page  
5.   include SortMod  
6.     
7.   def csort(ary, cmp)  
8.     lt=0 # loop time   
9.     ary.each do |i|  
10.       lt=i.to_s.size if i.to_s.size>lt  
11.     end  
12.     dm={}  
13.     (0..9).each do |j|;dm[j]=[];end  
14.     (0..lt-1).each do|i|        
15.       ary.each do |j|  
16.         if j.to_s.size < i+1  
17.           dm[0] << j  
18.         else  
19.           dm[j.to_s[-(1+i)].to_i] << j  
20.         end  
21.       end   
22.       tary=[]       
23.       (0..9).each do |j|  
24.         tary << dm[j].shift while dm[j].size > 0          
25.       end  
26.       #printf("[%d]: %s\n", i, tary)  
27.       ary = tary  
28.     end  
29.      
30.     ary.reverse! if cmp.equal?(@@asc_cmp)  
31.     ary  
32.   end  
33. end  

- Demo Code:

view plaincopy to clipboardprint?

1. require "alg/sort/RadixSort"  
2.   
3. a = [11, 2, 5, 9, 7, 6, 4, 8, 1, 3, 10]  
4. printf("Radix Sorting Demo:\n")  
5. radxSort = RadixSort.new  
6. printf("Original ary: %s\n", a)  
7. printf("After sort(desc): %s\n", radxSort.sort(a, false))  
8. printf("After sort(asc) : %s\n", radxSort.sort(a, true))  
9. printf("Original ary: %s\n\n", a)  

Execution result:

Radix Sorting Demo:
Original ary: [11, 2, 5, 9, 7, 6, 4, 8, 1, 3, 10]
After sort(desc): [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
After sort(asc) : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Original ary: [11, 2, 5, 9, 7, 6, 4, 8, 1, 3, 10]

補充說明 : 
* Wiki : Radix sort 

In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits, by comparing individual digits sharing the same significantposition. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.

* [C++ 演算法] 排序 : 基數排序法