迭代归并:归并排序非递归实现解析


在这里插入图片描述

🎬 鸽芷咕:个人主页

 🔥 个人专栏: 《数据结构&算法》《粉丝福利》

⛺️生活的理想,就是为了理想的生活!

📋 前言

归并排序的思想上我们已经全部介绍完了,但是同时也面临和快速排序一样的问题那就是递归消耗的栈帧空间太大了,所以对此我们必须掌握非递归的排序思想。

文章目录

  • 📋 前言
  • 一、非递归实现的思想
  • 二、非递归实现的过程
    • 2.1 非递归实现的调整
    • 2.2 调整思路讲解
    • 2.3 归并非递归完整代码
  • 三、归并排序的总结
  • 📝文章结语:

一、非递归实现的思想

归并实现的思想无非就是先将 每个数都递归 分割为一个小区间然后再进行排序,之后递归 回溯 上一个区间 这时 上一个区间都排好了所以可以在进行排序就这样循环上去。

在这里插入图片描述

在这里插入图片描述

既然要用非递归那么我们是不是可以这样想 直接吧每个区间定义为 1 进行归并然后再来进行循环到上一组归并排序:
-在这里插入图片描述
这样就可以利用循环来吧归并排序非递归化了

二、非递归实现的过程

好了具体思想那么我们懂了,既然要进行从最小区间 1 开始那么我们肯定需要需要定义 一个 gap = 1 开始循环

  • 然后每次 gap * = 2; 来进行调整我们的归并区间的间距进行归并
  • 而排序的时候则又需要一个循环了来进行进行对每个区间进行归并排序
  • int i = 0; i < n; i += (gap*2)
  • 为什么每次 i += (gap*2)因为 每次当这个区间排完了之后就需要跳到下一个区间开始

🍸 代码演示:

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc file");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += (gap*2)){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + (2 * gap) - 1;int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (2*gap));}printf("\n");gap *= 2;}free(tmp);
}

2.1 非递归实现的调整

以上就是非递归实现的代码了,但你真的以为非递归就这样结束了?哈哈哈其实没有我们前面举例的是2的倍数来进行排序的但是当我们排序10之类的不是2的倍数就会出现越界的情况:

🔥 注:是上面我们每次 第二个区间都是 i + (2 * gap) - 1 但是当不是2的整数倍来实现的话不就越界了

2.2 调整思路讲解

在这里插入图片描述
哦豁大家是不是看到了当第二次排序的时候 begin2end2 都越界了,第三次归并的时候甚至 end2 都 越界了

这其实非常简单既然第二个区间都越界的话那么是不是就不需要进行归并了,你想啊连第二个区间都不存在的话第一个区间和谁归并?

  • 而只有 end2 越界的话咱们修正一下不就好了,只让它归并一个数
    在这里插入图片描述

🔥 注:这里还要注意memcpy 的时候的copy大小。

以前我们进行 copy 的时候都是 2倍的gap 但是当才不是整数倍的时候就需要调整了
在这里插入图片描述

i 每次都是要归并的区间开头, 而 end2 倍修正了之后就是区间尾了他们一相减就好了
🔥 注:相减了之后要加1,因为是闭区间。(3-0)虽然是相减了但是我们实际复制的是4个数

在这里插入图片描述

2.3 归并非递归完整代码


// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc file");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += (gap*2)){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + (2 * gap) - 1;if (begin2 >= n)break;if (end2 >= n)end2 = n-1;printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));}printf("\n");gap *= 2;}free(tmp);
}

三、归并排序的总结

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

📝文章结语:

看到这里了还不给博主扣个:
⛳️ 点赞🍹收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/227871.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Python】requests库在CTFWeb题中的应用

目录 ①Bugku-GET ②Bugku-POST ③实验吧-天下武功唯快不破 ④Bugku-速度要快 ⑤Bugku-秋名山车神 ⑥Bugku-cookies ①Bugku-GET import requestsresprequests.get(urlhttp://114.67.175.224:12922/,params{what:flag}) print(resp.text)//或者 //resprequests.get(urlht…

Quartus的Signal Tap II的使用技巧

概述&#xff1a; Signal Tap II全称Signal Tap II Logic Analyzer&#xff0c;是第二代系统级调试工具&#xff0c;它集成在Quartus II软件中&#xff0c;可以捕获和显示实时信号&#xff0c;是一款功能强大、极具实用性的FPGA片上调试工具软件。 传统的FPGA板级调试是由外接…

鸿蒙操作系统:从手机到物联网,打造全场景智能体验

随着科技的不断发展&#xff0c;人们对于操作系统的需求也在不断升级。鸿蒙操作系统&#xff0c;作为华为推出的新一代智能终端操作系统&#xff0c;凭借其强大的分布式能力、流畅的用户体验以及丰富的应用生态&#xff0c;正逐渐成为人们关注的焦点。 一、鸿蒙操作系统概述 …

Redisson依赖冲突记录

前言&#xff1a;项目使用的springboot项目为2.7.X 依赖冲突一&#xff1a;springboot 与 redisson版本冲突 项目中依赖了 Lock4j&#xff0c;此为苞米豆开源的分布式锁组件 <dependency><groupId>com.baomidou</groupId><artifactId>lock4j-redisso…

IP地址的四大类型:动态IP、固定IP、实体IP、虚拟IP的区别与应用

在网络通信中&#xff0c;IP地址是设备在互联网上唯一标识的关键元素。动态IP、固定IP、实体IP和虚拟IP是四种不同类型的IP地址&#xff0c;它们各自具有独特的特点和应用场景。 1. 动态IP地址&#xff1a; 动态IP地址是由Internet Service Provider&#xff08;ISP&#xff…

详解Keras3.0 Layer API: LSTM layer

LSTM layer 用于实现长短时记忆网络&#xff0c;它的主要作用是对序列数据进行建模和预测。 遗忘门&#xff08;Forget Gate&#xff09;&#xff1a;根据当前输入和上一个时间步的隐藏状态&#xff0c;计算遗忘门的值。遗忘门的作用是控制哪些信息应该被遗忘&#xff0c;哪些…

Pycharm2023版本:Python远程调试配置详解

工欲善其事&#xff0c;必先利其器 首先你需要选择一个专业版本的pycharm&#xff0c;社区版本不支持远程配置功能&#xff0c;专业版下载地址&#xff1a;Pycharm 2023 双击程序进行安装&#xff0c;30天内免费试用&#xff0c;如果想要永久使用&#xff0c;办法你懂的&…

中职网络安全Server2002——Web隐藏信息获取

B-2&#xff1a;Web隐藏信息获取 任务环境说明&#xff1a; 服务器场景名&#xff1a;Server2002&#xff08;关闭链接&#xff09;服务器场景用户名&#xff1a;未知 有问题需要环境加q 通过本地PC中渗透测试平台Kali使用Nmap扫描目标靶机HTTP服务子目录&#xff0c;将扫描子…

电脑忘记开机密码很着急?一招搞定

前言 本教程适合没有登录微软账号的电脑哦&#xff5e; 随着手机越智能&#xff0c;人们花在电脑上的时间越来越少了。你家的电脑多久没开机了&#xff1f; 小伙伴有没有这样的经历&#xff1a;很久没有打开过电脑的你&#xff0c;突然有一天打开了电脑&#xff0c;却想不起…

阿里云OpenSearch-LLM智能问答故障的一天

上周五使用阿里云开放搜索问答版时&#xff0c;故障了一整天&#xff0c;可能这个服务使用的人比较少&#xff0c;没有什么消息爆出来&#xff0c;特此记录下这几天的阿里云处理过程&#xff0c;不免让人怀疑阿里云整体都外包出去了&#xff0c;反应迟钝&#xff0c;水平业余&a…

Postman接口测试工具使用

一、前言 在前后端分离开发时&#xff0c;后端工作人员完成系统接口开发后&#xff0c;需要与前端人员对接&#xff0c;测试调试接口&#xff0c;验证接口的正确性可用性。而这要求前端开发进度和后端进度保持基本一致&#xff0c;任何一方的进度跟不上&#xff0c;都无法及…

LV.13 D7 交叉编译工具链 学习笔记

一、交叉编译 1.1 编译原理 机器码&#xff08;二进制&#xff09;是处理器能直接识别的语言&#xff0c;不同的机器码代表不同的运算指令&#xff0c;处理器能够识别哪些机器码是由处理器的硬件设计所决定的&#xff0c;不同的处理器机器码不同&#xff0c;所以机器码不可移植…

设计模式——适配器模式(Adapter Pattern)

概述 适配器模式可以将一个类的接口和另一个类的接口匹配起来&#xff0c;而无须修改原来的适配者接口和抽象目标类接口。适配器模式(Adapter Pattern)&#xff1a;将一个接口转换成客户希望的另一个接口&#xff0c;使接口不兼容的那些类可以一起工作&#xff0c;其别名为包装…

【VRTK】【VR开发】【Unity】18-VRTK与Unity UI控制的融合使用

课程配套学习项目源码资源下载 https://download.csdn.net/download/weixin_41697242/88485426?spm=1001.2014.3001.5503 【背景】 VRTK和Unity自身的UI控制包可以配合使用发挥效果。本篇就讨论这方面的实战内容。 之前可以互动的立体UI并不是传统的2D UI对象,在实际使用中…

iS-RPM2023.2.0.0新版本发布

引言 经过不断努力和精心打磨,我们带着全新版本的RPM产品与大家见面啦!本次更新将为广大流程分析师和质量管理员们提供更深入、更准确的洞察力,以帮助大家在数据驱动的决策中取得更卓越的成果。然而,让海量数据转化为可用的见解并不是一项容易的任务。我们理解数据分析师们…

竞赛保研 基于大数据的股票量化分析与股价预测系统

文章目录 0 前言1 课题背景2 实现效果3 设计原理QTChartsarma模型预测K-means聚类算法算法实现关键问题说明 4 部分核心代码5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于大数据的股票量化分析与股价预测系统 该项目较为新颖…

【逗老师的无线电】ICOM IC-705终端模式Terminal Mode直连反射器配置-内置网关IP直连篇

各位友台大家好呀&#xff0c;逗老师最近整了一台IC-705&#xff0c;最吸引人的莫过于这玩意可以IP直连反射器。下面简单介绍一下这个功能和其配置方法 目录 一、功能二、依赖条件三、配置3.1、IC-705连接WIFI3.2、配置Terminal Mode3.2.1、点击MENU进入菜单&#xff0c;翻到第…

Linux:apache优化(4)—— 隐藏版本号

运行环境 yum -y install apr apr-devel cyrus-sasl-devel expat-devel libdb-devel openldap-devel apr-util-devel apr-util pcre-devel pcre gcc make zlib-devel 源码包配置 ./configure --prefix/usr/local/httpd --enable-cgi --enable-rewrite --enable-so --enabl…

【哈希数组】697. 数组的度

697. 数组的度 解题思路 首先创建一个IndexMap 键表示元素 值表示一个列表List list存储该元素在数组的所有索引之后再次创建一个map1 针对上面的List 键表示列表的长度 值表示索引的差值遍历indexmap 将所有的list的长度 和 索引的差值存储遍历map1 找到最大的key 那么这个Ke…

QString设置小数点精度位数

QString设置小数点精度位数 Chapter1 QString设置小数点精度位数Chapter2 Qt中QString.toDouble有效位数6位问题以及数据小数点有效位数的处理问题一&#xff1a;QString.toDouble有效位只有6位问题二:小数点有效位数的问题 Chapter3 qt QString转Double只显示6位数字的问题(精…