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

轉載自 這裡 (Gossip@Caterpillar)
前言 :
在 快速排序法（一） 中，每次將最左邊的元素設為軸，而之前曾經說過，快速排序法的加速在於軸的選擇，在這個例子中，只將軸設定為中間的元素，依這個元素作基準進行比較，這可以增加快速排序法的效率.

解法 :
在這個例子中，取中間的元素s作比較，同樣的先得右找比s大的索引 i，然後找比s小的索引 j，只要兩邊的索引還沒有交會，就交換 i 與 j 的元素值，這次不用再進行軸的交換了，因為在尋找交換的過程中，軸位置的元素也會參與交換的動作，例如：
41　24　76　11　45　64　21　69　19　36

首先left為0，right為9，(left+right)/2 = 4（取整數的商），所以軸為索引4的位置，比較的元素是45，您往右找比45大的，往左找比45小的進行交換：

* 41　24　76*　11　[45]　64　21　69　19　*36
* 41　24　36　11　45*　64　21　69　19*　76
* 41　24　36　11　19　64*　21*　69　45　76
* [41　24　36　11　19　21]　[64　69　45　76]

完成以上之後，再初別對左邊括號與右邊括號的部份進行遞迴，如此就可以完成排序的目的

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

view plaincopy to clipboardprint?

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

* SortQuick2.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "SortQuick2.h"  
2.   
3.   
4. void quickSort2(int num[], int len) {  
5.      _quickSort2(num, 0, len-1, len);  
6. }  
7. void _quickSort2(int num[], int left, int right, int len){  
8.     if(left < right) {  
9.         int i=left-1;  
10.         int j=right+1;  
11.         int s = num[(left+right)/2];  
12.         while(1) {  
13.             while(num[++i]
14.             while(num[--j]>s);  
15.             if(i>=j)  
16.                 break;  
17.             SWAP(num[i],num[j]);              
18.         }  
19.         _quickSort2(num, left, i-1, len);  
20.         _quickSort2(num, j+1,right, len);  
21.     }  
22. }  

* 呼叫Sorting 代碼 :

view plaincopy to clipboardprint?

1. int num[MAX_SORT_QUICK2_LEN];  
2. getRandomArray(num, MAX_SORT_QUICK2_LEN);  
3. cout << "Original Array: " << endl;  
4. printArray(num, MAX_SORT_QUICK2_LEN);  
5. quickSort2(num, MAX_SORT_QUICK2_LEN);  
6. cout << "After Quick2 Sorting: " << endl;  
7. printArray(num, MAX_SORT_QUICK2_LEN);  

執行結果 :

Generate random Int array:
12 17 89 25 65 4 20 49 13 19 50
Original Array:
12 17 89 25 65 4 20 49 13 19 50
After Quick2 Sorting:
4 12 13 17 19 20 25 49 50 65 89

This message was edited 2 times. Last update was at 17/02/2010 00:55:35