程式扎記: [ 資料結構 小學堂 ] 排序 : 選擇排序法

標籤

2010年11月21日 星期日

[ 資料結構 小學堂 ] 排序 : 選擇排序法

前言 : 
選擇排序法可使用兩種方式排序, 一為在所有資料中, 當由大至小排序, 則將最大值放入第一個位置 ; 若由小至大排列, 則將最大值放入位置的末端. 例如當 N 筆資料需要由小至大排列時, 首先以第一個位置的資料, 依序向 2,3,4...N 個位置做比較. 如果資料大於或等於其中一個位置, 則繼續比較 ; 若小於其中某一個位置, 則將兩個位置的資料互換. 互換後則繼續比下一筆資料直到末端. 此時第一個位置可以得到資料堆的最小值. 接下來選擇第二個位置資料依序向 3,4,5...N 個位置做比較. 依序就上述方法直到 (N-1) 個位置都比較完後, 就完成了由小到大的排列. 

選擇排序範例 : 
以下排序我們利用 6,4,9,8,3 由小到大排序過程來解釋選擇排序法的演算流程 : 
第一次掃描 : 
6 4 9 8 3 : 比較 6 > 4 : 交換 6 與 4 
4 6 9 8 3 : 比較 4 < 9 : 不交換 
4 6 9 8 3 : 比較 4 < 8 : 不交換 
4 6 9 8 3 : 比較 4 > 3 : 交換 4 與 3, 得第一次掃描結果 3 6 9 8 4 
第二次掃描 : 
3 6 9 8 4 : 比較 6 < 9 : 不交換 
3 6 9 8 4 : 比較 6 < 8 : 不交換 
3 6 9 8 4 : 比較 6 < 4 : 交換 6 與 4, 得第二次掃描結果 3 4 9 8 6 
第三次掃描 : 
3 4 9 8 6 : 比較 9 > 8 : 交換 9 與 8 
3 4 8 9 6 : 比較 8 > 6 : 交換 8 與 6, 得第三次掃描結果 3 4 6 9 8 
第四次掃描 : 
3 4 6 9 8 : 比較 9 > 8 : 交換 9 與 8, 得第四次掃描結果 3 4 6 8 9 

選擇法分析 : 

1. 無論是最壞或是最佳及平均情況都需要找到最大值 (或最小值), 因此其比較次數為 : (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 次 ; 時間複雜度為 O(n^2).
2. 由於選擇排序是以最大或是最小值直接與最前方未排序的鍵值交換, 資料排列順序很有可能被改變, 故為不穩定排序法.
3. 只需要一個額外空間, 所以空間複雜度為最佳.
4. 此排序法適用於資料小或有部分資料已排序過.

範例代碼 : 

  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. struct BenchMark {  
  6.     int swapTime;  
  7.     int verifyTime;  
  8. };  
  9. BenchMark selectSort(int data[], int n) {  
  10.     int cnt=0, vt=0;  
  11.     BenchMark bm;  
  12.     for(int i=0; i<(n-1); i++) {  
  13.         for(int j=(i+1); j
  14.             vt++;  
  15.             //printf("%d with %d\n", i, j);  
  16.             if(data[i]>data[j]) {  
  17.                 int tmp = data[i];  
  18.                 data[i] = data[j];  
  19.                 data[j] = tmp;  
  20.                 cnt++;  
  21.             }  
  22.         }  
  23.     }  
  24.     bm.swapTime = cnt;  
  25.     bm.verifyTime = vt;  
  26.     return bm;  
  27. }  
  28. void main(bool b) {  
  29.     if(b) {  
  30.         int data[6] = {2,5,9,7,6,8};  
  31.         cout<< "原始資料: " << endl;  
  32.         for(int i=0; i<6; i++) {  
  33.             printf("%2d ",data[i]);  
  34.         }  
  35.         printf("\n");  
  36.         BenchMark bm = selectSort(data, 6);  
  37.         cout << "選擇排序: " << endl;  
  38.         for(int i=0; i<6; i++) {  
  39.             printf("%2d ",data[i]);  
  40.         }  
  41.         printf("\n");  
  42.         printf("Swap time: %d\n", bm.swapTime);  
  43.         printf("Verify time: %d\n", bm.verifyTime);  
  44.     }  
  45. }  
執行結果 : 

原始資料:
2 5 9 7 6 8
選擇排序:
2 5 6 7 8 9
Swap time: 4
Verify time: 15 

沒有留言:

張貼留言

網誌存檔

關於我自己

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