二分(折半)插入排序基本思想:设在数据表中有一个元素序列v[0],v[1],v[2]......v[n].其中v[0],v[1],v[2]......v[i-1]是已经排好序的元素。在插入v[i]。利用折半搜索寻找v[i]的插入位置。
二分插入排序是一种稳定的排序。当n较大时,总排序码比较次数比直接插入排序的最差情况好得多,但比最好情况要差,所元素初始序列已经按排序码接近有序时,直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同,依赖于元素初始序列。
#include<iostream>
#include<cstring>
using namespace std;
int const ic_limit = 100002;
void vInputData(int &iNum,int iArr[]);
void BinaryInsertSort(int iArr[],int iLeft,int iRight);
void vPrintAns(int iNum,int iArr[]);
int main()
{
int iNum;
int iArr[ic_limit];
memset(iArr,0,sizeof(iArr));
vInputData(iNum,iArr);
BinaryInsertSort(iArr,1,iNum);
vPrintAns(iNum,iArr);
return 0;
}
void vInputData(int &iNum,int iArr[])
{
cin >> iNum;
for(int i=1; i<=iNum; i++)
{
cin >> iArr[i];
}
}
void BinaryInsertSort(int iArr[],int iLeft,int iRight)
{
int iFo;
int iTo;
int iMid;
int iTemp;
for(int i=2; i<=iRight; i++)
{
iFo = 1;
iTo = i-1;
iTemp = iArr[i];
while(iFo <= iTo)//确定插入位置
{
iMid = (iFo + iTo) / 2;
if(iArr[i] < iArr[iMid])
{
iTo = iMid - 1;
}
else
{
iFo = iMid + 1;
}
}
for(int j=i-1; j>=iFo; j--)//iFo == iTo == iMid
{
iArr[j+1] = iArr[j];
}
iArr[iFo] = iTemp;
}
}
void vPrintAns(int iNum,int iArr[])
{
for(int i=1; i<iNum; i++)
{
cout << iArr[i] << " ";
}
cout << iArr[iNum] << endl;
}
分享到:
相关推荐
易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar
使用二分方法实现插入排序
易语言二分插入排序源码,二分插入排序,二分直接插入排序
易语言二分插入排序.rar 易语言二分插入排序.rar 易语言二分插入排序.rar 易语言二分插入排序.rar 易语言二分插入排序.rar 易语言二分插入排序.rar
内部排序之二分插入排序 C经典算法之一,值得学习。
JS实现二分插入排序
易语言源码二分插入排序.7z
二分插入排序-易语言.zip
主要为大家详细介绍了Java经典排序算法之二分插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
程序模拟实验所用到的所有源码,包括冒泡排序,插入排序,代码运行时长统计等。
二分插入排序
经过上几篇对排序算法的了解,我们发现,所谓的排序也是确定一... 与上篇中的插入排序类似分已排序和未排序部分,然后将未排序部分元素逐个插入,但是插入的过程不同,需要每次求一个中间位置,和中间位置元素比较大
Delphi直接插入法排序示例..rar
系统应具备的功能: (1)从键盘上输入五个学生的考研成绩; (2)实现直接插入排序、二分插入排序、对各科成绩,以及平均成绩从小到大排序; (3)比较各种插入排序的优劣
常用算法,2分法插入排序的c语言实现。对初学者很有用。
该程序包含严蔚敏数据结构课程中的各种排序算法(各种排序算法以独立函数的方式给出,可自行调用),包括直接插入排序、二分插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序。
/* * --插入排序-- * 假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大, * 则将这个数的位置往后挪,直到当前外层元素的... * 该算法可以认为是插入排序的一个变种,称为二分查找排序。 */