插入排序算法详解

插入排序是一种相对较简单的排序算法，它可以实现在不断输入元素的同时对数据进行排序，即所有元素输入完毕后，就可以立刻得到由输入数据组成的有序序列。

插入排序属于稳定的排序算法，即当待排序序列中有相同的元素时，它们的相对位置在排序前后不会发生改变。

插入排序的基本原理是从前往后扫描待排序序列，并依次将扫描到的元素插入到已排序序列中的适当位置。如图 1 所示，假设现在扫描到了 X，X 前面的为已排序序列，后面的为未排序序列。

图 1 待排序元素 X

通过执行一次插入排序操作，元素 X 会被插入到已排序序列中的适当位置，如图 2 所示。

图 2 插入到适当位置的元素 X

由此，通过不断重复执行图 1 到图 2 的过程，直到最后一个元素，即可实现对整个序列的排序。

举个例子，接下来使用插入排序算法对 (5,1,4,2,8) 这个序列进行排序，其初始状态如图 3 所示。

图 3 未排序之前的序列状态

注意，既然是要做插入排序，那么序列中第一个元素本身是不需要移动的，换句话说，在做插入排序操作之前，序列中第一个元素就默认是已经排序好的，它位于已排序序列中。

第一次扫描待排序序列，得到元素 1，做插入排序操作，其结果如图 4 所示。

图 4  插入元素 1 之后的状态

继续扫描待排序序列，得到元素 4，做插入排序操作，其结果如图 5 所示。

图 5 插入元素 4 之后的状态

继续扫描待排序序列，得到元素 2，做插入排序操作，其结果如图 6 所示。

图 6 插入元素 2 之后的状态

继续扫描待排序序列，得到元素 8，做插入排序操作，其结果如图 7 所示。

图 7 插入元素 8 之后的状态

由此，插入排序算法结束，得到排序好的序列 (1,2,4,5,8)。

实现代码如下（C 语言）：

#include <stdio.h>
#define N 5
int a[N] = { 5,1,4,2,8 };
//插入排序函数
void InsertSort(int a[])
{
    for (int i = 1; i < N; i++) {
        //若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入
        if (a[i] < a[i - 1]) {
            int j = i - 1;
            int x = a[i];
            //采用顺序查找方式找到插入的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
            while (j > -1 && x < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = x;      //插入到正确位置
        }
        //输出插入排序后的序列
        printf("第 %d 次:", i);
        for (int i = 0; i < N; i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
    }
}
int main() {
    InsertSort(a);
    return 0;
}

运行结果为：

通过分析实现代码可以得知，插入排序算法的最差时间复杂度为O(n²)，最优时间复杂度为O(n)（即当待排序序列已经有序的情况下），平均时间复杂度为O(n²)。