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

前言 : 
選擇排序法可使用兩種方式排序, 一為在所有資料中, 當由大至小排序, 則將最大值放入第一個位置 ; 若由小至大排列, 則將最大值放入位置的末端. 例如當 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. 此排序法適用於資料小或有部分資料已排序過.

範例代碼 : 

view plaincopy to clipboardprint?

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