一. 算法描述
插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。
例如有一个长度为n的无序数组，进行n-1次的插入即能完成排序；
第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；
第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......
第n-1次，数组前n-1个元素组成有序的数组，将数组的第n个元素插入由n-1个元素构成的有序数组中，则完成了整个插入排序。
关键问题：在前面已经排好序的序列中找到合适的插入位置。
为方便理解我还准备了动图：
二. 算法分析
平均时间复杂度：o(n2)
空间复杂度：o(1) (用于记录需要插入的数据)
稳定性：稳定
三. 算法实现
从前向后查找的插入排序：
/********************************************************
*函数名称：insertsort
*参数说明：pdataarray 无序数组；
* idatanum为无序数据个数
*说明： 插入排序
*********************************************************/
void insertsort(int* pdataarray, int idatanum)
{
for (int i = 1; i < idatanum; i ) //从第2个数据开始插入
{
int j = 0;
while (j < i && pdataarray[j] <= pdataarray[i]) //寻找插入的位置
j ;
if (j < i) //i位置之前，有比pdataarray[i]大的数，则进行挪动和插入
{
int k = i;
int temp = pdataarray[i];
while (k > j) //挪动位置
{
pdataarray[k] = pdataarray[k-1];
k--;
}
pdataarray[k] = temp; //插入
}
}
}
从后面查找插入的方式，代码复杂程度较低
/********************************************************
*函数名称：insertsort
*参数说明：pdataarray 无序数组；
* idatanum为无序数据个数
*说明： 插入排序
*********************************************************/
void insertsort(int* pdataarray, int idatanum)
{
for (int i = 1; i < idatanum; i ) //从第2个数据开始插入
{
int j = i - 1;
int temp = pdataarray[i]; //记录要插入的数据
while (j >= 0 && pdataarray[j] > temp) //从后向前，找到比其小的数的位置
{
pdataarray[j 1] = pdataarray[j]; //向后挪动
j--;
}
if (j != i - 1) //存在比其小的数
pdataarray[j 1] = temp;
}
}
四. 算法优化
插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为o(n2)。
//查找数值idata在长度为ilen的pdataarray数组中的插入位置
int findinsertindex(int *pdataarray, int ilen, int idata)
{
int ibegin = 0;
int iend = ilen - 1;
int index = -1; //记录插入位置
while (ibegin <= iend)
{
index = (ibegin iend) / 2;
if (pdataarray[index] > idata)
iend = index - 1;
else
ibegin = index 1;
}
if (pdataarray[index] <= idata)
index ;
return index;
}
/********************************************************
*函数名称：binaryinsertsort
*参数说明：pdataarray 无序数组；
* idatanum为无序数据个数
*说明： 二分查找插入排序
*********************************************************/
void binaryinsertsort(int* pdataarray, int idatanum)
{
for (int i = 1; i < idatanum; i ) //从第2个数据开始插入
{
int index = findinsertindex(pdataarray, i, pdataarray[i]); //二分寻找插入的位置
if (i != index) //插入位置不为i，才挪动、插入
{
int j = i;
int temp = pdataarray[i];
while (j > index) //挪动位置
{
pdataarray[j] = pdataarray[j-1];
j--;
}
pdataarray[j] = temp; //插入
}
}
}