參考資料：
[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 )
{
//思想：
//分為有序區(qū)和無序區(qū)
//剛開始第一個數(shù)為有序區(qū)的第一個數(shù)
//取出無序區(qū)的第一個數(shù)扳埂，要放入無序區(qū)，需要騰出空間
//如何騰出空間呢
for(i=1;i<n;i++)
{
//剛開始瘤礁，第一個數(shù)肯定位于有序區(qū)
//步驟1：從無序區(qū)中取出第一個數(shù)
int tmp = a[i];
//步驟2：把數(shù)插入到有序區(qū)中阳懂，得在有序區(qū)中騰出一個空間
//有序區(qū)是按從小到大進(jìn)行排序的，比如有序區(qū)目前是：1 4 5 7 我要插入的數(shù)是6
//剛開始 6小于7 則把7復(fù)制給后面一位
for(j=i-1;j>=0 && tmp<a[j];j--)//int的范圍是從負(fù)的很大到正的很大
{
a[j+1]=a[j];
}
a[j+1]= tmp;
}
}
int main()
{
int a[]={20,40,30,10,60,50};
//數(shù)組的長度
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;
}
時間復(fù)雜度：
直接插入排序的時間復(fù)雜度是O(N^2)。
