程式扎記: [ 資料結構 小學堂 ] 排序 : 快速排序法

標籤

2010年11月24日 星期三

[ 資料結構 小學堂 ] 排序 : 快速排序法

前言 : 
快速排序法又稱分割交換排序法, 是目前公認最佳的排序法. 它的原理和氣泡排序法一樣都是用交換的方式. 不過它會先在資料中找到一個虛擬的中間值, 把小於中間值的資料放在左邊而大於中間值的資料放在右邊, 再以同樣的方式分別處理左右兩邊的資料, 直到完成為止. 

演算法說明 : 
假設有 n 筆紀錄 R1, R2...Rn, 其鍵值為 k1, k2...kn. 快速排序法的步驟如下 : 

1. 取 K1 為第一鍵值.
2. 由左向右找出一個鍵值Ki 使得 Ki > K1.
3. 由右向左找出一個鍵值Kj 使得 Kj < K1.
4. 若i < j, 則 Ki 與 Kj 交換並繼續步驟2到4的執行.
5. 若i >= j, 則將 K 與 Kj 交換, 並以 j 為基準點將資料分為左右兩部分, 並以遞迴方式分別為左右兩半進行排序, 直到完成排序.

下面示範快速排序過程, 考慮有資料如右 : 28 6 40 2 63 9 58 16 47 20 
第一次比較 : K0=28 

> 找到 40>28 (i=2), 20<28(j=9) 交換得 : 28 6 20 2 63 9 58 16 47 40 (i=3, j=8)
> 找到 63>28 (i=4), 16<28(j=7) 交換得 : 28 6 20 2 16 9 58 63 47 40 (i=5, j=6)
> 最後得到 i=6, j=6, 交換 K0 與 K5 得第一次比較結果 : [9 6 20 2 16] 28 [58 63 47 40]
> 再對 [9 6 20 2 16] 與 [58 63 47 40] 進行第二次比較

第二次比較(1) : K0=9 for [9 6 20 2 16] 

> 找到 20>9 (i=2), 2<9(j=3) 交換得 : 9 6 2 20 16 (i=3>j=2)
> 交換 K2(2) 與 K0(9) 得第二次(1)比較結果 : [2 6] 9 [20 16]

第二次比較(2) : K6=58 for [58 63 47 40] 

> 找到 63>58 (i=7), 40<58 (j=9) 交換得 : 58 40 47 63 (i=8, j=8)
> 交換 K6(58) 與 K8(47) 得第二次(2)比較結果 : [47 40] 58 [63]

再進行第三次比較可得最後排序結果為 : 2 6 9 16 20 28 40 47 58 63 

演算法分析 : 

1. 最快速及平均情況下, 時間複雜度為 O(nlog2n). 最壞情況就是每次挑中的中間值不是最大就是最小, 期時間複雜度為 O(n^2).
2. 快速排序法不是穩定排序法.
3. 在最差情況下, 空間複雜度為 O(n), 而最佳情況為 O(log2n).
4. 快速排序法是平均執行時間最快的排序法.

範例代碼 : 

  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. void _swapValue(int *a, int *b) {  
  12.     int tmp = *a;  
  13.     *a = *b;  
  14.     *b = tmp;  
  15. }  
  16. BenchMark quickSort(int data[], int n, int i, int j) {  
  17.     BenchMark bm;  
  18.     bm.swapTime = 0;  
  19.     bm.verifyTime = 0;  
  20.     if(i >= j)  
  21.         return bm;  
  22.     int m=0, left=i+1, right=j;  
  23.     int cnt=0, vt=0;  
  24.     while(left
  25.         vt++;  
  26.         if(data[left]<=data[i]) {  
  27.             left++;           
  28.             continue;  
  29.         }  
  30.         vt++;  
  31.         if(data[right]>=data[i]) {  
  32.             right--;              
  33.             continue;  
  34.         }         
  35.         _swapValue(&data[left], &data[right]);  
  36.         cnt++;  
  37.         left++;  
  38.         right--;  
  39.     }  
  40.     if(data[i]
  41.         right--;  
  42.     }  
  43.     _swapValue(&data[i], &data[right]);  
  44.     bm.swapTime = cnt+1;  
  45.     bm.verifyTime = vt;   
  46.     for(int k=0; k
  47.         printf("%2d ", data[k]);  
  48.     }  
  49.     printf(" (k=%d: left=%d, right=%d)\n",right, i, j);  
  50.     BenchMark tmp = quickSort(data, n, i, right-1);  
  51.     bm.swapTime+=tmp.swapTime;  
  52.     bm.verifyTime+=tmp.verifyTime;  
  53.     tmp = quickSort(data, n, right+1, j);  
  54.     bm.swapTime+=tmp.swapTime;  
  55.     bm.verifyTime+=tmp.verifyTime;  
  56.     return bm;  
  57. }  
  58. void _showData(int data[], int size) {  
  59.     for(int i=0; i
  60.         printf("%2d ", data[i]);  
  61.     }  
  62.     printf("\n");  
  63. }  
  64.   
  65. #define QUICK_DATA_SIZE 10  
  66. void ch08_06(bool b) {  
  67.     if(b) {  
  68.         int data[QUICK_DATA_SIZE] = {28,6,40,2,63,9,58,16,47,20};  
  69.         printf("原始資料為: ");  
  70.         _showData(data, QUICK_DATA_SIZE);  
  71.         BenchMark bm = quickSort(data, QUICK_DATA_SIZE, 0, QUICK_DATA_SIZE-1);   
  72.         cout << "快速排序: " << endl;  
  73.         _showData(data, QUICK_DATA_SIZE);  
  74.         printf("Swap time: %d\n", bm.swapTime);  
  75.         printf("Verify time: %d\n", bm.verifyTime);  
  76.     }  
  77. }  
執行結果 : 

原始資料為: 28 6 40 2 63 9 58 16 47 20
9 6 20 2 16 28 58 63 47 40 (k=5: left=0, right=9)
2 6 9 20 16 28 58 63 47 40 (k=2: left=0, right=4)
2 6 9 20 16 28 58 63 47 40 (k=0: left=0, right=1)
2 6 9 16 20 28 58 63 47 40 (k=4: left=3, right=4)
2 6 9 16 20 28 47 40 58 63 (k=8: left=6, right=9)
2 6 9 16 20 28 40 47 58 63 (k=7: left=6, right=7)
快速排序:
2 6 9 16 20 28 40 47 58 63
Swap time: 10
Verify time: 16


Ruby Sample Code:
- alg/sort/SortMod.rb
  1. module SortMod    
  2.   @@des_cmp = lambda{ |a,b| return a <=> b}  
  3.   @@asc_cmp = lambda{ |a,b| return b <=> a}  
  4.     
  5.   def sort(ary, desc=true)  
  6.     nary = []  
  7.     ary.each{ |item|; nary << item; }  
  8.     csort(nary, desc ? @@des_cmp : @@asc_cmp)  
  9.     nary  
  10.   end  
  11.     
  12.   def csort(ary, cmp)  
  13.     raise RuntimeError, "Muse implement method!"  
  14.   end  
  15.     
  16.   def swap(ary, i, j)  
  17.     ary[i], ary[j] = ary[j], ary[i]  
  18.   end  
  19.     
  20.   def sort?(cmp, desc=true)      
  21.     csort(cmp, desc ? @@des_cmp : @@asc_cmp)  
  22.     cmp  
  23.   end  
  24. end  
- alg/sort/QuickSort.rb
  1. require "alg/sort/SortMod"  
  2.   
  3. class QuickSort  
  4.   # http://localhost/jforum/posts/list/962.page  
  5.   include SortMod  
  6.     
  7.   def qsort(ary, cmp, h, t)  
  8.     if(h+1==t)  
  9.       swap(ary, h, t) if cmp.call(ary[h], ary[t])==1  
  10.     elsif h
  11.       m=0; left=h+1; right=t  
  12.       while left
  13.         if cmp.call(ary[h], ary[left])==1            
  14.           left+=1  
  15.           next      
  16.         end        
  17.         if cmp.call(ary[h], ary[right])==-1            
  18.           right-=1  
  19.           next  
  20.         end                      
  21.                  
  22.         swap(ary, left, right)  
  23.         left+=1  
  24.         right-=1                         
  25.       end # while  
  26.              
  27.       right-=1 if cmp.call(ary[h], ary[right]) == -1  
  28.       swap(ary, h, right)  
  29.       qsort(ary, cmp, h, right-1)  
  30.       qsort(ary, cmp, right+1, t)  
  31.     end        
  32.     ary  
  33.   end  
  34.     
  35.   def csort(ary, cmp)  
  36.     return qsort(ary, cmp, 0, ary.size-1)  
  37.   end  
  38. end  
- Demo Code 
  1. printf("Quick Sorting Demo:\n")  
  2. qickSort = QuickSort.new  
  3. printf("Original ary: %s\n", a)  
  4. printf("After sort(desc): %s\n", qickSort.sort(a, false))  
  5. printf("After sort(asc) : %s\n", qickSort.sort(a, true))  
  6. printf("Original ary: %s\n\n", a)  
Execution result:
Quick Sorting Demo:
Original ary: [2, 5, 9, 7, 6, 4, 8, 1, 3]
After sort(desc): [9, 8, 7, 6, 5, 4, 3, 2, 1]
After sort(asc) : [1, 2, 3, 4, 5, 6, 7, 8, 9]
Original ary: [2, 5, 9, 7, 6, 4, 8, 1, 3]


沒有留言:

張貼留言

網誌存檔

關於我自己

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