插入排序算法详解

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

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

插入排序的基本原理是从前往后扫描待排序序列,并依次将扫描到的元素插入到已排序序列中的适当位置。如图 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;
}
运行结果为:

第 1 次:1 5 4 2 8
第 2 次:1 4 5 2 8
第 3 次:1 2 4 5 8
第 4 次:1 2 4 5 8

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