插入排序法

發表於   |   分類於   |  

插入排序(insertion sort)是一種排序演算法，它將一個數列分成已排序與未排序兩個部分，透過不斷將未排序數列插入至已排序數列的正確位置達成，嗯…這個定義唸起來實在有些饒口，不如讓我們看個實例：

假設我們要由小到大排序數列：

1
25 49 22 33 47

依據先前說的，我們必須要將數列分割為已排序與未排序兩類，為了方便就用|隔開吧：

1
2
3
NULL | 25 49 22 33 47

目前什麼都沒做，所以已排序的部分為空，未排序的部分為整個數列。

接下來開始遍歷數列，首先遇到值25，如前所述，我們要將未排序數插入至已排序數的正確位置，不過目前未排序區段是空的，所以也沒什麼值能跟25相比，便直接將25放入已排序數列的首位吧：

1
2
3
25 | 49 22 33 47

已排序前 1 個數

第二個遇到的是49，重申最後一次，我們將它插至已排序數列的正確位置。目前已排序的有25，因為是由小排到大，我們便把49放到25的後頭：

1
2
3
25 49 | 22 33 47

已排序前 2 個數

第三個遇到的是22，直觀來排的話，我們會直接把22放在25前頭，不過遍歷陣列是循序的，實際上插入排序做的是不斷從22的索引值往前找，直到找到一個數比22小或至陣列盡頭，再將22放於該數後，所以我們會先遇到49：

1
2
3
25 49 22 | 33 47

排序中

因為49比22大，那我們應該22走到前面，這有兩種做法，目前先介紹第一種方法：透過交換兩者的位置，來把22往前推：

1
2
3
25 22 49 | 33 47

排序中

再來遇到25，顯然25還是比22大，再換一次位置：

1
2
3
22 25 49 | 33 47

排序中

再往前找，沒了，已經到已排序陣列的尾端，22也已經放在正確位置：

1
2
3
22 25 49 | 33 47

已排序前 3 個數

接下來是33，首先遇到49：

1
2
3
22 25 49 33 | 47

排序中

因為，49>33，讓33走到前面：

1
2
3
22 25 33 49 | 47

排序中

再來33碰上了25，它比25大，所以就不用動了，直接擺在25後頭：

1
2
3
22 25 33 49 | 47

已排序前 4 個數

終於到最後了，47：

1
2
3
22 25 33 49 47 |

排序中

49>47，往前站：

1
2
3
22 25 33 47 49 |

排序中

47>33，放在33後頭，排序完成：

1
2
3
22 25 33 47 49 |

已排序前 5 個數，排序完成 :)

以上就是插入排序法，演練有點繁瑣，但流程其實能簡要成幾個步驟，假設我們想由小排到大的話：

  1. 挑選未排序數列的一個值為 Key
  2. 將 Key 與已排序數 N 比較
  3. 若 Key >= N，則將 Key 至於 N 後
  4. 若 Key < N，則將 N 與 Key 位置互換
  5. 終止條件為找到小於Key的N或遍歷至已排序數列的盡頭

依照這個原則，我們能完成如下的虛擬碼(取自wiki)：

1
2
3
4
5
6
7
8
9
//A 為欲排序數列

for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

出乎意料的簡單，對吧？附上C語言的簡單實作：

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(int arr[],int length){

    int i=0,j=0;
    for(i=0;i<length;i++){
    	//已排序陣列|key|未排序陣列
        int key = arr[i];
        //從已排序陣列(0~i-1)去找適合的位置
        for(j=i-1;j>=0 && arr[j]>key;j--){
            SWAP(arr[j],arr[j+1]);
        }
    }
}

熟悉之後，將key拿掉會更為簡潔：

1
2
3
4
5
6
7
8
9
void insertionSort(int arr[],int length){

    int i=0,j=0;
    for(i=0;i<length;i++){
        for(j=i;j>0 && arr[j]<arr[j-1];j--){
            SWAP(arr[j],arr[j-1]);
        }
    }
}

減少賦值的次數

先前的做法是透過不斷交換來把Key的位置往前推動，但若交換後Key的位置並不正確，其實我們也不一定要把Key塞進去，因為即便塞進了錯誤的位置，再往前查找仍還要做交換，導致要往前N個單位，勢必要進行2N次的賦值。

為了減少賦值的次數，不妨只動Key一次，而這一次恰巧位在已排序陣列的正確位置，實作方法是以一個變數儲存Key的值，看看老例子：

1
2
3
我們的目標是把22放到正確位置

25 49 22 | 33 47

22為Key，我們用變數Key來儲存22

1
2
3
int Key = 22

25 49 22 | 33 47

先講結論，同樣的我們會持續往前找，直至陣列盡頭找到一個數小於22，不同點在於我們是對已排序陣列做平移，為Key提供一個合適的插槽，這樣的思維其實更適合插入(insert)的涵意：

我們能透過將前項的值賦與後項達成平移，首先把49後推：

1
2
3
4
5
int Key = 22

25 49 49 | 33 47
	^
	我們查找到這個位置(A[1])

再來把25往後推：

1
2
3
4
5
int Key = 22

25 25 49 | 33 47
^
我們查找到這個位置(A[0])

查找到陣列盡頭了，接下來把Key的值放入合適地點：

1
2
3
4
5
int Key = 22

22 25 49 | 33 47
^
A[0] = Key

這麼一來就完成排序了，由於Key一次就放對了，省去了一些不必要的賦值，這也是目前較常用的插入排序方式。附上對應的程式碼：

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int arr[],int length){

    int i=0,j=0,key=0;
    for(i=0;i<length;i++){
        key = arr[i];//保存當前選擇
        for(j=i;j>0 && key<arr[j-1];j--){
            arr[j] = arr[j-1];//平移陣列
        }
        arr[j] = key;//插入
    }
}

插入排序的一些特性：

  1. 插入排序是穩定的，因為我們總是有方向性的比對值
  2. 插入排序的時間複雜度：

輸入的大小為N，要遍歷整個陣列需要 O(n)，從Key往前找也需要 O(n)，所以平均而言是 O(n2)。

最佳時間複雜度為 O(n) -> 如已完成排序的情形
平均時間複雜度為 O(n2)
最糟時間複雜度為 O(n2) -> 如完全相反的情形

  1. 插入排序的空間複雜度：

這要看需不需要輔助空間來存放已排序陣列，上頭兩個方法都是不需要輔助陣列的(in-place)，所以為 O(1)，如果需要的話就為 O(n)。