简单来说，插入排序的思想是将待排序数列（这里用数组表示）分为已排好序和未排好序的两部分，一般将前面先排有序，例如：a[0]...a[i]已经有序，剩下的任务就是将a[i+1]...依次插入到前面有序的数列中，并同时使前面的序列仍然有序。
插入排序的开销主要在：找待插入的位置。最坏的情况是原序列是逆序的，每次都要找到最前，开销是 1+2+3+...n-1=n*(n-1)/2,故时间复杂度是O(n*n).
在插入的过程中还需要平移前面的数列。但是这个时间开销是伴随寻找插入位置同时进行的。下面是一段代码，包含测试代码，可直接运行。
#include "stdafx.h"
#include"iostream"
using namespace std;
int* insertsort(int a[],int m);
int _tmain(int argc, _TCHAR* argv[])
{
int a[5]={1,3,4,2,0};
cout<<"Please input five numbers:"<<endl;
for(int i=0;i<5;i++)
{
cin>>a[i];
}
int *c=insertsort(a,5);
for(int i=0;i<5;i++)
cout<<*(c+i)<<endl;
cout<<"finished input";
return 0;
}
int* insertsort(int a[],int m)
{
for(int i=0;i<m-1;i++) // i从0开始到i-1,j从i+1开始，到m
{
int j=i+1; //从i后面的第一个元素开始一次向前进行比较
int temp=a[j];//这一步是为了保存a[j]的值以便之后进行交换，否则有可能会被a[i]覆盖
while(i>=0&&temp<a[i])
{
a[i+1]=a[i]; //否的话因为需要将a[i]往后移位
i--;//继续往前比较
}
///退出循环要么是找到了比a[j]小的a[i],那么从这个i+1到j-1的位置均后移了，所以要将temp赋值给a[i+1];
//第二种情况是i已经减小到-1,所以将temp直接插到a[0]
a[i+1]=temp;
}
return a;
}