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

轉載自 這裡 (Gossip@Caterpillar) 
前言 : 
在之前所介紹過的排序方法，都是屬於「比較性」的排序法，也就是每次排序時 ，都是比較整個鍵值的大小以進行排序。 
這邊所要介紹的「基數排序法」（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相反，是由高位數為基底開始進行分配，其他的演算方式則都相同. 

演算法範例代碼 : 
* SortRadix.h 代碼 : 

view plaincopy to clipboardprint?

1. #include "Basic.h"  
2.   
3. #define MAX_RADIXNUM_SIZE 12  
4.   
5. /*  
6. * Source : http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/RadixSort.htm 
7. */  
8. void radixSort(int num[], int len);  

* SortRadix.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "SortRadix.h"  
2.   
3. void radixSort(int num[], int len) {  
4.     int tmp[10][10] = {0};  
5.     int order[10] = {0};  
6.     int n=1;  
7.     while(n<=10) {  
8.         for(int i=0; i
9.             int lsd = ((num[i]/n) % 10);  
10.             tmp[lsd][order[lsd]] = num[i];  
11.             order[lsd]++;  
12.         }  
13.         //Rearrange array.  
14.         int k=0;  
15.         for(int i=0; i<10; i++){           
16.             if(order[i]!=0) {  
17.                 for(int j=0; j
18.                     num[k] = tmp[i][j];                   
19.                 }                                         
20.             }  
21.             order[i] = 0;  
22.         }  
23.         n *= 10;  
24.     }  
25. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void radixSortTest(bool b) {  
2.     if(b) {  
3.         int num[MAX_RADIXNUM_SIZE] = {0};  
4.         getRandomArray(num, MAX_RADIXNUM_SIZE);  
5.         radixSort(num, MAX_RADIXNUM_SIZE);  
6.         cout << "After radix sorting: " << endl;  
7.         printArray(num, MAX_RADIXNUM_SIZE);  
8.     }  
9. }  

執行結果 : 

Generate random Int array:
10 41 82 70 88 24 98 92 86 37 36 31
After radix sorting:
10 24 31 36 37 41 70 82 86 88 92 98