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

標籤

2010年8月6日 星期五

[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 代碼 :
  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 代碼 :
  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 代碼 :
  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

沒有留言:

張貼留言

網誌存檔

關於我自己

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