插入排序：直接插入排序（Straight Insertion S

基本思想：

将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

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

要点：设立哨兵，作为临时存储和判断数组边界之用。

算法的实现：

// 输出数组内容
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]; // 复制为哨兵，即存储待排序元素
            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); // 打印每趟排序的结果
    }
}

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]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果 array[j] 前一个数据 array[j-1] > array[j]，就交换 array[j] 和 array[j-1]，再 j-- 直到 array[j-1] <= array[j]。这样也可以实现将一个新数据并入到有序区间。

// 直接插入排序（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); // 打印每趟排序的结果
    }
}

总结

时间复杂度：O（n^2）。其他的插入排序有二分插入排序，2-路插入排序。