程式扎記: [C++ 演算法] 排序 : 快速排序法 (三)

標籤

2010年8月6日 星期五

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


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

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


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


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


整個演算的過程,直接摘錄書中的虛擬碼來作說明:
  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 代碼 :
  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 代碼 :
  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. }  
* 呼叫演算法代碼 :
  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

沒有留言:

張貼留言

網誌存檔

關於我自己

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