[演算法] 插入排序法 Insertion Sort

　　插入排序法是經典的三大 O(n^2) 排序演算法之一。與其叫他「插入演算法」，不如叫他「插隊演算法」更能表達其運作原理，可以想像做一個未排序的物件(人?)隊伍，從頭開始，每個物件都有一次機會向前插隊到它該去的位置。

　　插入排序法最佳狀況下(已排序好數列)，只需要掃描一遍就可以結束，故 O(n) ，但最差狀況需要做 n*(n-1)/2 - (n-1) 次的賦值，。但是，插入排序法在處理少量數據的能力平均來說是三大O(n^2)排序演算法中最佳的，部分快速排序法到最後也是用插入排序法排少量的數據，是一定要當常識記得的演算法之一 (XD)。

複雜度：

• 時間：最佳 O(n) 最差 O(n^2)
• 空間：O(n), O(1) 輔助用

步驟：

1. 第一個物件當作已經排序好。
2. 向後逐一取出物件，並從該物件開始向前掃描其他物件。
3. 若前一個物件大於(小於)此物件，兩者對調位置。 (在實作上使用賦值而不對調)
4. 重複步驟3. 一直交換到前一個物件不再大於(小於)此物件。
5. 重複步驟2. 從原位置繼續看下一個物件。 

Java 簡單實現：

public class InsertionSort {
    public void sort(int[] array) {
        // 一個一個看
        for(int i=0; i < array.length; ++i) {
            int target = array[i];
            int j = i;
            // 向前檢查 (插隊)
            while((j > 0) && (array[j - 1] > target)) { 
                array[j] = array[j - 1];
                j--;
            }
            array[j] = target;
        }
    }
}

範例影片：

 參考資料：

1. Wiki 選擇排序法