簡單來說，插入排序的思想是將待排序數列（這裡用數組表示）分為已排好序和未排好序的兩部分，一般將前面先排有序，例如：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;
}
