图解插入排序——直接插入排序算法(straight insertion sort)

算法图解

直接插入排序，Straight Insertion Sort，是一种最简单的排序方法，它的基本思想就是把一个记录插入到一个有序的序列中，其基本步骤可以概括为两步：一是取出一个元素，留出空位；二是符合条件的元素右移，把取出的元素插入。那么这样的话，我们就需要一个辅助的变量来临时缓存这个被取出的变量，一般我们把这个辅助变量称之为“哨兵”。

第一趟插入排序：

因为是取出一个元素和前一个元素对比，根据大小关系决定插入到第一个元素的左边或者右边，所以第一趟排序应该从第二个元素开始，即i初始值为2。

假设给定一个序列{22， 11， 33， 10， 22}，首先取出第二个元素11，用11和22比较，22大于11则22右移一位，然后把11插入到22的位置，即0号下标处。

在第一趟排序中，进行了一次比较，一次元素移动。通过第一趟排序形成了一个包含两元素的有序子序列。

**第二趟插入排序： **

取出第三个元素，第三个元素array[2]与第二个元素array[1]对比，若array[2]>array[1]，那么就把array[2]插入到原处，即不进行任何操作，结束本趟插入排序；如果array[2]<array[1]，那么array[1]右移一位，array[2]继续和array[0]比较；如果array[2]>array[0]，那么array[2]插入到1号位置，结束本趟插入排序；如果array[2]<array[0]，那么array[0]右移一位，array[2]插入到0号位置。

第二趟排序进行了一次比较，0次元素移动（这是最好的情况，即本来子序列就已经从小到大了）。经过第二趟排序，有序子序列加一，这也是插入法之所以称为插入的原因：把一个记录插入到一个有序的序列中。

第三趟插入排序：

取出第四个元素，执行比较-移动-插入三部曲操作。

第三趟排序，进行了三次比较，三次移动，这是最坏的情况，即每次比较都要移动。经过第三趟排序，有序序列再次加1，无序序列减一。

第n-1趟插入排序：

第n-1趟插入排序，将进行最少1次比较，0次移动；最多n-1次比较，n-1次移动。

且通过示意图可以看到，红色22本来就在黑色22前面，经过插入排序后，红色22依然在黑色22前面，所以插入排序是稳定排序。

算法实现（C语言）

/*交换 i j 位置的元素*/
void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/*插入排序*/
void insert_sort(int array[], int num)
{
    int i = 0, j = 0, Sentry = 0; /*Sentry 哨兵*/
    for (i = 1; i < num; i++)
    {
        Sentry = array[i]; /*取出一个元素*/
        j = i - 1;
        while ((j >= 0) && (Sentry < array[j]))
        {
            array[j + 1] = array[j]; /*符合条件右移*/
            j--;
        }
        array[j + 1] = Sentry;
    }
}

复杂度分析

拆入排序在最好的情况下，即数组本身就是按要求顺序排列好的，那么每趟插入排序都要进行一次比较，不需要移动元素，因为要n-1趟排序，所以共需要n-1次比较。在最坏的情况下，每趟排序都要进行比较，每次比较都要移动元素，比较次数为，移动次数也是如此，所以时间复杂度为。

插入排序是一种，稳定的，时间复杂度为的，简单的内排序。