[ 資料結構 小學堂 ] 排序 : 插入排序法

前言 : 
插入排序法 (Insert Sort) 是將陣列中的元素, 逐一與已排序好的資料做比較, 再將該陣列元素插入適當的位置. 

範例說明 : 
現有一資料群 : 6 4 9 8 3 下面將使用插入排序法由小到大排序 : 
步驟1 : 將資料群第一個元素6 加入已排序資料群 
6 4 9 8 3 
步驟2 : 將第二個元素4 與已排序資料群比較 : 因為4沒有比已排序資料群任何一個元素大, 故將4放在第一個元素, 所以已排序資料依序往後移動. 所以已排序資料群為 4 6. 
4 6 9 8 3 
步驟3 : 將第三個元素9 與已排序資料群比較 : 因為已排序資料群沒有比9 大, 所以9保留原來位置, 所以已排序資料群為 4 6 9. 
4 6 9 8 3 
步驟4 : 將第四個元素8 與已排序資料群比較 : 因為8 比9 小, 故將8 放在9 位置, 9 則往後移動, 所以已排序資料群為 4 6 8 9. 
4 6 9 8 3 
步驟5 : 將第五個元素3 與已排序資料群比較 : 因為3沒有比已排序資料群任何一個元素大, 故將3放在第一個元素, 所有已排序資料依序往後移動, 所以已排序資料群為 3 4 6 8 9. -> 完成排序. 

插入法分析 : 

1. 最壞及平均情況需比較 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 次 ; 時間複雜度為 O(n^2), 最好情況時間複雜度為 : O(n)
2. 插入排序是穩定排序法.
3. 只需要一個額外空間, 所以空間複雜度為最佳.
4. 此排序適用於大部分資料已經經過排序或已排序資料庫新增資料後進行排序.
5. 插入排序法會造成資料大量搬移, 所以建議在鏈結串列上使用.

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. struct BenchMark {  
6.     int swapTime;  // Swap Time  
7.     int verifyTime;  // Verify Time  
8. };  
9. BenchMark insertSort(int data[], int n) {  
10.     int cnt=0, vt=0, tmp, j;  
11.     BenchMark bm;  
12.     for(int i=1; i
13.         vt++;  
14.         j = i-1;  
15.         while(j>=0 && data[j+1]< data[j]) {  
16.             cnt++;  
17.             vt++;  
18.             tmp = data[j+1];  
19.             data[j+1] = data[j];  
20.             data[j] = tmp;  
21.             j--;  
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[7] = {2,5,9,7,6,8,1};  
31.         cout<< "原始資料: " << endl;  
32.         for(int i=0; i<7; i++) {  
33.             printf("%2d ",data[i]);  
34.         }  
35.         printf("\n");  
36.         BenchMark bm = insertSort(data, 7);  
37.         cout << "插入排序: " << endl;  
38.         for(int i=0; i<7; 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 1
插入排序:
1 2 5 6 7 8 9
Swap time: 10
Verify time: 16