一、算法描述

    插入排序是一种比较直观的排序算法，其思想是：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，直到找到一个合适和位置并插入。具体算法描述如下（升序排列）：

    1. 从第一个元素开始，该元素可以认为已经是排好序的了

    2.取出下一个元素，在已经排序的元素序列中从后向前扫描

    3.如果该元素（已排序）大于新元素，将该元素移到下一个位置

   4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

   5. 如果找到小于或者等于新元素的位置，则将新元素插入到该位置后面；如果没有找到，则放在第一个位置

   6.重复步骤2~5

  如下图所示：

二、算法实现

代码如下所示：

#include <stdio.h>
#include <errno.h>

int insertsort(int *source, int n)
{
    int i, j;
    int key;

    if (!source || n <=0) {
        fprintf(stderr, "Invalid argument.n");
        return -EINVAL;
    }

    for (i = 1; i < n; ++i) {
        key = source[i];
        j = i - 1;

        while ((j >= 0) && (source[j] > key)) {
            source[j + 1] = source[j];
            --j;
        }
        source[j + 1] = key;
    }

    return 0;
}

#define ARRAY_SIZE(__s) (sizeof(__s) / sizeof(__s[0]))

int main(void)
{
    int source[] = { 7, 5, 2, 4, 6, 1, 3};
    int i;

    printf("Before sort: ");
    for (i = 0; i < ARRAY_SIZE(source); ++i) {
        printf("%d ", source[i]);
    }
    printf("n");

    insertsort(source, ARRAY_SIZE(source));

    printf("After sort: ");
    for (i = 0; i < ARRAY_SIZE(source); ++i) {
        printf("%d ", source[i]);
    }
    printf("n");

    return 0;
}

三、算法分析

  如果输入的数组已经是排好序的，则插入排序不需要移动任何元素，这种情况是插入排序的最好情况，时间复杂度为O(n)；若输入数组已反向排序，即按递减顺序排好序，则导致最坏情况，时间复杂度为O(n^2）。“平均情况”往往和最坏情况大致一样差，时间复杂度是O(n^2)。插入排序是就地排序，除了一个临时变量来存储当前要插入的元素外，不需要额外的空间，因此空间复杂度为O(1)。