排序系列一：直接插入排序

一、基本思想

直接插入排序即是在要排序的数组中，假设前n-1（n>=2）个数已经是排好序的，现在要把第n个数插入到前n个已经排好序的数组中，使得这n个数也变成有序的，如此反复循环，使得要排序的数组中的最后一个元素也排好序。

直接插入排序.png

二、代码实现

void insertsort(int a[],int n)
{
    int i,j,temp;
    for (i = 1 ;i < n ; i++) {
        temp = a[I];//把待排序元素赋给temp，
        j = i - 1;
        while (j >= 0 && (temp < a[j])) {//循环的作用是将比当前元素大的元素都往后移动一个位置
            a[j + 1] = a[j];
            j--;
        }
        a[j+1]=temp;//元素后移后要插入的位置就空出了，找到该位置插入
    }
}

时间复杂度为：O（n^2）
注明：本文参考自 [翡翠森林Z的博客]（http://www.jianshu.com/p/1f952b77c6a00B0920080）