程式扎記

前言 :
基數排序法 (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?
#include   
#include   
  
using namespace std;  
  
struct BenchMark {  
    int swapTime;  // Swap Time  
    int verifyTime;  // Verify Time  
    double cTime;  // Consumed Time  
};  
BenchMark radixSort(int data[], int size) {  
    BenchMark bm;  
    bm.swapTime = 0;  
    bm.verifyTime = 0;    
    int vt=0, st=0;  
    for(int n=1; n<=100; n=n*10) {  
        int tmp[10][20] = {-1};  
        for(int i=0; i
            int m = (data[i]/n)%10;  
            tmp[m][i] = data[i];  
            vt++;  
        }  
        int k=0;  
        for(int i=0; i<10; i++) {  
            for(int j=0; j
                vt++;  
                if(tmp[i][j] >0) {                     
                    data[k] = tmp[i][j];  
                    k++;  
                }  
            }  
        }  
    }  
    bm.verifyTime = vt;  
    bm.swapTime = st;  
    return bm;  
}  
#define RADIX_DATA_SIZE 20  
void main(bool b) {  
    if(b) {  
        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};  
        printf("原始資料為: ");  
        _showData(data, RADIX_DATA_SIZE);  
        BenchMark bm = radixSort(data, RADIX_DATA_SIZE);  
        cout << "基數排序: " << endl;  
        _showData(data, RADIX_DATA_SIZE);  
        printf("Swap time: %d\n", bm.swapTime);  
        printf("Verify time: %d\n", bm.verifyTime);  
    }  
}  

執行結果 :

原始資料為: 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?
module SortMod    
  @@des_cmp = lambda{ |a,b| return a <=> b}  
  @@asc_cmp = lambda{ |a,b| return b <=> a}  
    
  # Open API: Sorting given array.  
  def sort(ary, desc=true)  
    nary = []  
    ary.each{ |item|; nary << item; }  
    csort(nary, desc ? @@des_cmp : @@asc_cmp)      
  end  
    
  # Customized sorting algorithm.  
  def csort(ary, cmp)  
    raise RuntimeError, "Muse implement  method!"  
  end  
    
  # Swap ary[i] with ary[j]  
  def swap(ary, i, j)  
    ary[i], ary[j] = ary[j], ary[i]  
  end  
    
  # Open API: In place sorting on given array  
  def sort?(ary, cmp, desc=true)      
    csort(ary, cmp, desc ? @@des_cmp : @@asc_cmp)  
    cmp  
  end  
    
  public :sort, :sort?  
  protected :csort, :swap    
end  

- alg/sort/RadixSort.rb

view plaincopy to clipboardprint?
require "alg/sort/SortMod"  
  
class RadixSort  
  # http://localhost/jforum/posts/list/969.page  
  include SortMod  
    
  def csort(ary, cmp)  
    lt=0 # loop time   
    ary.each do |i|  
      lt=i.to_s.size if i.to_s.size>lt  
    end  
    dm={}  
    (0..9).each do |j|;dm[j]=[];end  
    (0..lt-1).each do|i|        
      ary.each do |j|  
        if j.to_s.size < i+1  
          dm[0] << j  
        else  
          dm[j.to_s[-(1+i)].to_i] << j  
        end  
      end   
      tary=[]       
      (0..9).each do |j|  
        tary << dm[j].shift while dm[j].size > 0          
      end  
      #printf("[%d]: %s\n", i, tary)  
      ary = tary  
    end  
     
    ary.reverse! if cmp.equal?(@@asc_cmp)  
    ary  
  end  
end  

- Demo Code:

view plaincopy to clipboardprint?
require "alg/sort/RadixSort"  
  
a = [11, 2, 5, 9, 7, 6, 4, 8, 1, 3, 10]  
printf("Radix Sorting Demo:\n")  
radxSort = RadixSort.new  
printf("Original ary: %s\n", a)  
printf("After sort(desc): %s\n", radxSort.sort(a, false))  
printf("After sort(asc) : %s\n", radxSort.sort(a, true))  
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++ 演算法] 排序 : 基數排序法

程式扎記

標籤

2010年11月27日星期六

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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2010年11月27日 星期六

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