折半插入排序算法

全栈程序员-站长 • 2026年3月19日上午11:48 • 未分类 • 阅读 1

折半插入排序算法折半插入排序 BinaryInsert 是对插入排序算法的一种改进所谓插入排序就是不断的依次将元素插入前面已排好序的序列中由于前半部分为已排好序的数列这样我们不用按顺序依次寻找插入点可以采用折半查找的方法来加快寻找插入点的速度具体操作在将一个新元素插入已排好序的数组的过程中寻找插入点时将待插入区域的首元素设置为 a low 末元素设置为 a high 将待插入元素与 a mid 其中 mid low high low 2 相比较如果比参考元素小则选择 a

折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

具体操作： 在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]。将待插入元素与a[mid]（其中mid=low+(high-low)/2）相比较，如果比参考元素小，则选择a[low]到a[mid-1]为新的插入区域(即high=mid-1)，否则选择a[mid+1]到a[high]为新的插入区域（即low=mid+1），如此直至low<=high不成立，即将high+1位置及之后所有元素后移一位，并将新元素插入a[high+1]。

例如： 使用折半插入排序算法将数组 { 4,2,8,0,5,7,1,3,6,9 } 进行升序排序。

在这里插入图片描述
实现代码如下所示。

#include 
     using namespace std; template<class T> void BinaryInsertionSort(T *a, int n) { 
    int i, j, low, high, mid; for (i = 2; i < n; i++) //依次将a[2]~a[n]插入到前面已经排好序的列表 { 
    a[0] = a[i]; //将a[i]暂存到a[0] low = 1; high = i - 1; while (low <= high) { 
    mid = low + (high - low) / 2; //取中间位置(利用low + (high - low) / 2求mid是为了防止整数溢出问题) if (a[mid] > a[0]) //查找左子表 { 
    high = mid - 1; } else //查找右子表 { 
    low = mid + 1; } } for (j = i - 1; j >= high + 1; --j) //i - 1指待插入元素的前一个元素，即有序列表中所有大于待插入元素的最后一个元素；high + 1指有序列表中所有大于待插入元素的第一个元素 { 
    a[j + 1] = a[j]; //统一后移元素 } a[high + 1] = a[0]; //插入操作 } } int main() { 
    int a[] = { 
    0,4,2,8,0,5,7,1,3,6,9 }; cout << "排序前：" << endl; for (int i = 1; i < 11; i++) { 
    cout << a[i] << " "; } cout << endl; BinaryInsertionSort(a, 11); cout << "排序后：" << endl; for (int i = 1; i < 11; i++) { 
    cout << a[i] << " "; } cout << endl; double b[] = { 
    0,4.1,2.2,8.3,0.4,5.5,7.6,1.7,3.8,6.9,9.0 }; cout << "排序前：" << endl; for (int i = 1; i < 11; i++) { 
    cout << b[i] << " "; } cout << endl; BinaryInsertionSort(b, 11); cout << "排序后：" << endl; for (int i = 1; i < 11; i++) { 
    cout << b[i] << " "; } cout << endl; system("pause"); return 0; }

需要注意的是，在上述代码中，为防止整数溢出问题的出现，在求中间的下标mid时，使用mid = low + (high - low) / 2;，而不是mid = (high + low) / 2，详细原因见→为防止整数溢出问题，使用low + (high – low) / 2而不是(high + low) / 2。

原始数组的第一轮排序代码运行的中间过程如下图所示。

在这里插入图片描述
时间复杂度： 折半插入排序算法比直接插入排序算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为 $O(n^2)$ ，与直接插入排序算法相同。

稳定性： 由于在比较的时候，对于两个相等的元素，不会进行移动，排序完成后，相同元素之间的先后顺序不变，所以折半插入排序算法是一种稳定的排序算法，如下图所示。

在这里插入图片描述

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208342.html原文链接：https://javaforall.net

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

RMQ 区间最值问题

上一篇 2026年3月19日上午11:48

linux 格式化磁盘失败,linux格式化磁盘出错

下一篇 2026年3月19日上午11:48

怎样使用cookie登录自己的账号

在这之前，不管是做测试还是挖漏洞总会遇到这种问题做测试的时候测试项里面有一个会话标识未更新，这种漏洞说白了就是在退出个人账户的时候没有及时的清除cookie，从而让别人利用你的cookie再次登录你的账户，然后测试的时候客户就让测试如何使用cookie登录在挖漏洞的时候一般xss都需要打cookie然后伪造别人的身份登录，其实也是使用打到的cookie登录在这之前我没深入的理解这块，现…

全栈程序员-站长
2022年4月8日
82
项目管理-5大过程组-10大知识领域-47过程

项目管理五大过程组：1、启动过程组：获得授权，定义一个新项目或现有项目的一个新阶段，正式开始该项目或阶段的一组过程。2、规划过程组：明确项目范围，优化目标，为实现目标而制定行动方案的一组过程。3、执行过程组：完成项目管理计划中确定的工作以实现项目目标的一组过程。4、监控过程组：跟踪、审查和调整项目进展与绩效，识别必要的计划变更并启动相应变更的一组过程。5、收尾过程组：为完结所有过程组的…

全栈程序员-站长
2022年4月13日
53
Git、Gitlab与Github区别

Git、Gitlab与Github区别Git 是一种版本控制系统是一个命令是一种工具 Github Gitlab 等产品都是第三方基于 git 这项技术开发的 Github 是一个基于 git 实现的在线代码仓库包含一个网站界面向互联网开放 Gitlab 是一个基于 git 实现的在线代码仓库软件你可以用 gitlab 自己搭建一个类似于 github 一样的系统一般用于在企业学校等内部网络搭建 git 私服作者 w0916 链接

全栈程序员-站长
2026年3月18日
2
SpringBoot异步调用

SpringBoot异步调用除了异步请求，一般上我们用的比较多的应该是异步调用。通常在开发过程中，会遇到一个方法是和实际业务无关的，没有紧密性的。比如记录日志信息等业务。这个时候正常就是启一个新线程去做一些业务处理，让主线程异步的执行其他业务。何为异步调用说异步调用前，我们说说它对应的同步调用。通常开发过程中，一般上我们都是同步调用，即：程序按定义的顺序依次执行的过程，每一行代码执行过程必须等待上一行代码执行完毕后才…

全栈程序员-站长
2022年7月11日
24
sourceinsight4.0序列号_source insight 4

sourceinsight4.0序列号_source insight 4先关闭Souceinsight。打开C:\ProgramData\SourceInsight\4.0\si4.lic将Date和Expiration都加一年（比今年多一年即可），保存。重新打开Souceinsight，会提示重新输入用户名和邮箱，继续试用30days。

全栈程序员-站长
2022年10月3日
5
视频录制软件哪个好,推荐几款简单实用的视频课件录制软件「建议收藏」

视频录制软件哪个好,推荐几款简单实用的视频课件录制软件「建议收藏」　　日常生活中，我们有时候会因为工作或学习的原因，会使用到一些视频录制软件，通过视频录制软件，我们可以记录一些错过的细节，提高学习或工作效率。当然，现在网上的视频录制软件那么多，到底视频录制软件哪个好用？下面，小编给大家几款视频录制软件，感兴趣的朋友就一起来看看吧。　　一、微软录屏软件(MicrosoftSnip)　　1、软件介绍：　　MicrosoftSnip是微软最新…

全栈程序员-站长
2022年6月16日
38

折半插入排序算法

关于作者

全栈程序员-站长

相关推荐

怎样使用cookie登录自己的账号

项目管理-5大过程组-10大知识领域-47过程

Git、Gitlab与Github区别

SpringBoot异步调用

sourceinsight4.0序列号_source insight 4

视频录制软件哪个好,推荐几款简单实用的视频课件录制软件「建议收藏」

发表回复