Insertion Sort 插入排序法

插入排序法的概念為，
將array分成「已排序」與「未排序」兩邊，
再依序把未排序的array中的的每一筆資料插入已排序的array中的適當位置。

要sort一個 [A1..An] 的array，
把array分成已排序array [A1..Ak] 以及未排序array [Ak+1..An]，
之後把未排序array的 Ak+1 插入已排序array中的適當位置，
使得 [A1..Ak+1] 成為已排序的array。
之後重複以上同樣動作，
把未排序array [Ak+2..An] 的第一個元素，
插入已排序array [A1..Ak+1] 中的適當位置。

Introduction to Algorithms

如上圖，
首先我們把array分成已排序（1）、未排序（2~6）。
黑格代表要插入已排序array的點，（也就是插入黑格左方的array）
灰格代表黑格在未排序array中需要比較的點。


以下為用java來實現插入排序法。

class InsertionSort {
    static void sort(int[] array) {
        int i, j;
        int key;
        for (i=1; i<array.length; ++i) {
            key = array[i];
            for (j=i-1; (j>=0)&&(array[j]>key); --j) {
                array[j+1] = array[j];
            }
            array[j+1] = key;
        }
    }
}

內層for(j)迴圈控制已排序array [A1..Ak]，
外層for(i)迴圈控制已排序array [Ak+1..An]，
初始值會令k=1，表示令第一個元素為已排序的array。
因此i的初始值為1，表示從未排序array中的第2個元素開始排。
接下來要把key(Ak+1) 插入 [A1..Ak]，
內層for(j)迴圈把比key大的值都往右搬，最後把key插入空出來的那格。

最好的情形是，array本來就排好的，
也就是Ak+1永遠比Ak大，那就永遠不會進入內層迴圈。
ex: [1, 2, 3, 4, 5, 6] => O(n)

而最壞的情形，就是array為由大到小的狀況，
或是array的第一個元素是最大的，而剩下的都已經排好了，
因此Ak+1永遠比Ak小，那就會一直進入內層迴圈做計算。
ex: [6, 1, 2, 3, 4, 5] => O(n²)