排序算法系列：插入排序算法

概述

直接插入排序（Straight Insertion Sort）的基本操作是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增1的有序表。

　　　　　　　　　　　　　　　　　　　　　　　　　　　– 《大話數據結構》

算法原理分析

從上面的概述中我們也就可以知道了，這裡對數組進行排序的過程需要兩個序列才能完成。
一個待排序的亂序序列，一個是已排序的有序序列。我們現在要要做的就是把亂序的元素一個一個地從亂序列中插入到有序序列中去。就像下面這樣：

可是，這裡還是有一些不太好的地方，比較明顯地方就是我們需要額外添加一個輔助數組。如果這個待排序數據比較大，那麼可能添加輔助數組的策略就不能使用了。
這裡我們不難想到，在原始數組中，有這樣的一個等式：整體序列 = 有序序列 + 亂序序列
也就是說我們可以把當前序列數組一分為二，左邊為有序，右邊為亂序。

這樣每次從亂序序列中取出第一個元素，從有序列中插入。直到序列整體有序為止。具體的步驟請參見下面的算法步驟。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxociAvPg0KPGgxIGlkPQ=="算法步驟">算法步驟 默認序列中的第0個元素是有序的（因為只有一個元素a[0]嘛，自然是有序的）； 從下標為1（下標從0開始）的元素開始，取當前下標i位置處的元素a[i]保存到一個臨時變量waitInsert裡； 對前半部分有序序列的循環遍歷，並與waitInsert比較，直到遇到一個比waitInsert小的元素（這裡默認是從小到大排序），此時的下標為j，那麼現在只要對a[j+1]進行賦值waitInsert即可； 將待插入元素的下標 i 向後推移一個位置； 重復進行第2步到第4步，直到亂序序列中的元素被全部插入到有序序列中； 經過以上5個步驟之後，整體序列必然有序，排序完成。

邏輯實現

/*
     * 排序算法的核心模塊
     * 
     * @param array
     *      待排序數組
     */
    private void sortCore(int[] array) {
        int arraySize = array.length;

        for (int i = 1; i < arraySize; i++) {
            int j = i;

            int waitInsert = array[i];
            while(j > 0 && waitInsert < array[j - 1]) {
                array[j] = array[j - 1];
                j--;
            }

            array[j] = waitInsert;
        }
    }

復雜度分析

這裡的最壞的情況和平均情況從代碼中就可以看出來，因為有兩嵌套的for循環嘛。那麼其最好的情況呢？這個就是對於一個有序的序列來說，不需要進行交換，只是比較了n次，所以這裡最好的時間復雜度就是O(n)。

Ref