插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
void insertSort(int array[], int length)
{
int key;
for(int i=1; i<length; i++)
{
key = array[i];
for(int j=i-1; j>=0 && array[j] > key; j--)
{
array[j+1] = array[j];
}
array[j+1] = key;
}
}
原文：http://www.cnblogs.com/ye1031/p/4806042.html