参考资料：
[1]https://www.cnblogs.com/jingmoxukong/p/4303270.html
[2]http://www.cnblogs.com/skywang12345/p/3596881.html

//直接插入排序
#include<iostream>

using namespace std;

void insertSort(int* a,int n )
{
    //思想：
    //分为有序区和无序区
    //刚开始第一个数为有序区的第一个数
    //取出无序区的第一个数，要放入无序区，需要腾出空间
    //如何腾出空间呢

    for(i=1;i<n;i++)
    {
        //刚开始，第一个数肯定位于有序区
        //步骤1：从无序区中取出第一个数
        int tmp = a[i];
        //步骤2：把数插入到有序区中，得在有序区中腾出一个空间
        //有序区是按从小到大进行排序的，比如有序区目前是：1 4 5 7 我要插入的数是6
        //刚开始 6小于7 则把7复制给后面一位
        for(j=i-1;j>=0 && tmp<a[j];j--)//int的范围是从负的很大到正的很大
        {
            a[j+1]=a[j];
        }
        a[j+1]= tmp;
    }
}


int main()
{

    int a[]={20,40,30,10,60,50};
    //数组的长度
    int ilen=sizeof(a)/sizeof(a[0]);
    cout<<"before insert sort"<<endl;
    for(int i=0;i<ilen;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    insertSort(a,ilen);

    cout<<"after insert sort"<<endl;
    for(int i=0;i<ilen;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

时间复杂度：
直接插入排序的时间复杂度是O(N^2)。