程式扎記: [C++ 演算法] 排序 : 基數排序法

標籤

2010年11月27日 星期六

[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 代碼 : 

  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 代碼 : 

  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. }  
* 呼叫演算法代碼 : 

  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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!