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

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

演算法說明 : 
假設有 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. 快速排序法是平均執行時間最快的排序法.

範例代碼 : 

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. 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

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.   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

view plaincopy to clipboardprint?

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 

view plaincopy to clipboardprint?

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]