[C++ 演算法] 排序 : 快速排序法 (三)

轉載自 這裡 (Gossip@Caterpillar)
前言 :
之前說過軸的選擇是快速排序法的效率關鍵之一，在這邊的快速排序法的軸選擇方式更加快了快速排序法的效率，它是來自演算法名書 Introduction to Algorithms 之中.

解法 :
先說明這個快速排序法的概念，它以最右邊（或最左邊）的值s作比較的標準，將整個數列分為三個部份，一個是小於s的部份，一個是大於s的部份，一個是未處理的部份，如下所示 ：


在排序的過程中，i 與 j 都會不斷的往右進行比較與交換，最後數列會變為以下的狀態：


然後將s的值置於中間，接下來就以相同的步驟會左右兩邊的數列進行排序的動作，如下所示：


整個演算的過程，直接摘錄書中的虛擬碼來作說明：

view plaincopy to clipboardprint?

1. QUICKSORT(A, p, r)       
2.     if p < r           
3.         then q <- PARTITION(A, p, r)                    
4.                         QUICKSORT(A, p, q-1)                    
5.                         QUICKSORT(A, q+1, r)   
6. end QUICKSORT   
7. PARTITION(A, p, r)       
8.     x <- A[r]       
9.     i <- p-1       
10.     for j <- p to r-1           
11.         do if A[j] <= x                    
12.             then  i <- i+1                            
13.                 exchange A[i]<->A[j]       
14.     exchange A[i+1]<->A[r]       
15.     return i+1   
16. end PARTITION  

一個實際例子的演算如下所示：


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

view plaincopy to clipboardprint?

1. #include "main.h"  
2. #include "Basic.h"  
3.   
4. #define MAX_SORT_QUICK3_LEN 11  
5.   
6. /* 
7. * Source : http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/QuickSort3.htm 
8. */  
9. void quickSort3(int num[], int len);  
10. void _quickSort3(int num[], int left, int right, int len);  
11. int _partition(int num[], int left, int right, int len);  

* SortQuick3.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "SortQuick3.h"  
2.   
3. void quickSort3(int num[], int len) {  
4.      _quickSort3(num, 0, len-1, len);  
5. }  
6. void _quickSort3(int num[], int left, int right, int len){  
7.     if(left < right) {  
8.         int q = _partition(num, left, right, len);  
9.         _quickSort3(num, left, q-1, len);  
10.         _quickSort3(num, q+1, right, len);  
11.     }  
12. }  
13. int _partition(int num[], int left, int right, int len){  
14.     int i = left -1;  
15.     for(int j=left ; j
16.         if(num[j] < num[right]) {  
17.             i++;  
18.             SWAP(num[i], num[j]);  
19.         }         
20.     }  
21.     SWAP(num[i+1],num[right]);  
22.     return i+1;  
23. }  

* 呼叫演算法代碼 :

view plaincopy to clipboardprint?

1. void sortQuick3(bool b) {  
2.     if(b) {  
3.         int num[MAX_SORT_QUICK3_LEN];  
4.         getRandomArray(num, MAX_SORT_QUICK3_LEN);  
5.         cout << "Original Array: " << endl;  
6.         printArray(num, MAX_SORT_QUICK3_LEN);  
7.         quickSort3(num, MAX_SORT_QUICK3_LEN);  
8.         cout << "After Quick3 Sorting: " << endl;  
9.         printArray(num, MAX_SORT_QUICK3_LEN);  
10.     }  
11. }  

執行結果 :

Generate random Int array:
81 95 44 43 28 50 43 2 46 85 31
Original Array:
81 95 44 43 28 50 43 2 46 85 31
After Quick3 Sorting:
2 28 31 43 43 44 46 50 81 85 95

This message was edited 5 times. Last update was at 06/08/2010 18:15:46