基本思想：

將一個記錄插入到已排序好的有序表中，從而得到一個新的記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。

第一趟比較前兩個數(shù)，然后把第二個數(shù)按大小插入到有序表中； 第二趟把第三個數(shù)據(jù)與前兩個數(shù)從后向前掃描，把第三個數(shù)按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。

直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序是將待比較的數(shù)值與它的前一個數(shù)值進行比較，所以外層循環(huán)是從第二個數(shù)值開始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。

待排序記錄 R1，R2，… ，Rn–1, Rn
第一步：R1
第二步：(R1 ), R2
第三步：(R1 , R2), R3
……
第 j 步：(R1，R2，… ，Rj–1), Rj
……
第 n 步: (R1，R2，… ，Rn–1), Rn．

要點：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。

算法的實現(xiàn)：

// 輸出數(shù)組內(nèi)容
void print(int array[], int length, int i) {
    printf("i=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

// 直接插入排序（Straight Insertion Sort）
void InsertSort(int array[], int length) {
    for (int i = 1; i < length; i++) {
        if (array[i] < array[i-1]) { // 若第i個元素大于i-1元素，直接插入；小于的話，移動有序表后插入
            int j = i - 1;
            int sentry = array[i]; // 復(fù)制為哨兵，即存儲待排序元素
            array[i] = array[i-1]; // 首先后移一個元素
            while (j >= 0 && sentry < array[j]) { // 查找在有序表的插入位置
                array[j+1] = array[j];
                j--; // 元素后移
            }
            array[j+1] = sentry; // 插入到正確位置
        }
        print(array, length, i); // 打印每趟排序的結(jié)果
    }
}

int main(int argc, const char * argv[]) {
    int arrayInsertSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    InsertSort(arrayInsertSort, 8);
    printf("\n");
    
    return 0;
}

精簡代碼：

將 array[j] 插入到前面a[0…j-1]的有序區(qū)間所用的方法進行改寫，用數(shù)據(jù)交換代替數(shù)據(jù)后移。如果 array[j] 前一個數(shù)據(jù) array[j-1] > array[j]，就交換 array[j] 和 array[j-1]，再 j-- 直到 array[j-1] <= array[j]。這樣也可以實現(xiàn)將一個新數(shù)據(jù)并入到有序區(qū)間。

// 直接插入排序（Straight Insertion Sort）
void InsertSort(int array[], int length) {
    for (int i = 1; i < length; i++) {
        for (int j = i - 1; j >= 0 && array[j] > array[j+1] ; j --) {
            int temp = array[j+1];
            array[j+1] = array[j];
            array[j] = temp;
        }
        print(array, length, i); // 打印每趟排序的結(jié)果
    }
}

總結(jié)

時間復(fù)雜度：O（n^2）。其他的插入排序有二分插入排序，2-路插入排序。