插入排序
浏览数：22 /
时间：2015年06月08日
在冒泡排序、选择排序编写代码之后，楼主渐渐找到了coding的信心，熟能生巧，就像写词唱曲之前，都得先背诵大量的诗词，熟悉各路歌曲，才干走出自己的路线，有自己的杰作。好吧，来让楼主继续进行"社会主义0基础阶段"的任务，这次是插入排序。
一. 算法描写叙述
插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。比如有一个长度为N的无序数组，进行N-1次的插入即能完毕排序；第一次，数组第1个数觉得是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完毕了整个插入排序。
以以下5个无序的数据为例：
65 27 59 64 58 （文中仅细化了第四次插入过程）
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
二. 算法分析
平均时间复杂度：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; //插入
}
}
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
