排序之直接插入排序和折半插入排序

直接插入排序

直接插入排序時将一個記錄插入到一個已經有序的的表或者數組中，進而得到一個新的有序的表或者數組。

就像打牌一樣，拿到一張牌後，要往手中的牌裡插，使手中的牌還是有序的。假如手中有4,6,7三張牌，現在拿到的下一張牌是5，那麼肯定要插在4之後，直接插入排序也是這個道理。

假如現在有數組：{11,2,5,78,34,56,23}，直接插入排序的過程如下：

代碼實作如下：

void InsertSort(int a[], int n) {
    int i, j, temp;
    for (i = ; i < n; i++) {
        temp = a[i];    // 待插關鍵字為a[i]
        for (j = i - ; a[j] > temp && j >= ; j--) {   // 查找a[i]的位置
            a[j + ] = a[j];
        }
        a[j + ] = temp;
    }
}
           

分析發現上圖中當待插關鍵字為78時，78比前面的一個大，就沒有必要進行這一趟排序，是以可以在進行每一趟排序之前，判斷是否需要進行。

代碼實作如下：

void InsertSort(int a[], int n) {
    int i, j, temp;
    for (i = ; i < n; i++) {
        if (a[i] < a[i - ]) { // 如果需要進行排序，也就是說a[i]比它的前一個小，a[i]和前面的不能構成一個有序序列
            temp = a[i];
            for (j = i - ; a[j] > temp && j >= ; j--) { 
                a[j + ] = a[j];
            }
            a[j + ] = temp;
        }
    }
}
           

直接插入排序的時間複雜度

直接插入排序的最好的情況是原本需要排序的數組就是有序的，那麼它隻需要比較即可，但是如果是最壞情況，即數組是反序的，那麼他的時間複雜度就會比較大，是以最後他的平均時間複雜度為 O(n2) 。直接插入排序是簡單排序中時間複雜度比較穩定的排序算法。

直接插入排序時一種穩定的排序。

折半插入排序

我們知道對于數組折半查找要比順序查找快，通過這個點可以對直接插入排序進行優化。之前在找待插關鍵字位置的時候使用的是順序查找比較，現在将之前的順序查找改為折半查找。

void BiInsertSort(int a[], int n) {
    int i, j, temp;
    int low, high, mid;
    for (i = ; i < n; i++) {
        if (a[i] < a[i - ]) {
            temp = a[i];    // a[i]是待插關鍵字
            low = ;
            high = i - ;   // 從0到i是一段有序序列，在這段序列中找一個合适的位置插入a[i]
            while (low < high) {
                mid = (low + high) / ;
                if (a[mid] > temp)  // a[i]在mid之前
                    high = mid - ;
                else
                    low = mid + ;  // a[i]在mid之後
            }
            for (j = i - ; j >= low; j--) 
                a[j + ] = a[j];        // 記錄後移
            a[low] = temp;
        }  
    }
}
           

源碼連結