【数据结构初阶】一文带你学会归并排序(递归非递归)
目录
前言
递归实现
代码实现
非递归实现
代码实现
总结
前言
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的迭代;
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
递归实现
在我们前边的学习过程中,例如合并两个有序数组等问题,我们就使用过归并的思想,本质上来说归并排序还是分治的思想,将大问题化为小问题,然后解决小问题,最终是实现大问题的解决。
动图演示

归并排序的递归实现并不复杂,有以下几个步骤:
1.首先申请一段空间tmp,用来保存以及排好序的部分数据,当所有数据都排序完后,重新拷贝回原数组。
2.对数组数据进行分割,例如二叉树分为左右子树一样,也将数组分割为左右数组,知道左指针left大于等于右指针right时,返回。
3.对以及递归好的数据进行排序,两个区域内的数据进行比较,小的数据插入到tmp数组中,直至到数组的最后一个数据,如果当一个数组提前结束,直接将另外一个数组数据直接拷贝即可。
4.将排序好的tmp数组拷贝回原数组。


代码实现
由于原函数不适合递归,所以我们定义子函数,并且求出left和right进行递归,将数组分为[left,mid]和[mid+1,right]两个部分,切记free我们申请的空间,其余按照思路实现即可。
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int mid = left + (right - left) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int i = left;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}
}
void MergeSort(int* a, int n)
{int left = 0;int right = n - 1;int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, left, right, tmp);free(tmp);tmp = NULL;
}
非递归实现
归并的非递归实现起来比递归实现较难一点,但是还是分治的思想,只不过非递归有点类似于二叉树的后序遍历,我们使用gap来控制每次归并时数组内数据个数,例如第一次就是一个一个数据归并成两个数据的有序数组,第二次使用两个数据的有序数组归并成四个数据的有序数组,所以gap是由1开始,并且每次乘2。
非递归实现就是在gap等于1时,将整个数组元素排序成两个两个有序,这个递归实现是不同的。
但是当我们每次将gap乘2时,我们发现数组元素个数不一定是2的次方倍,所以不进行处理时,我们的数组一定会造成越界访问。
我们对每次要归并的数组,第一个数组起始为begin1,结束为end1,第二个数组起始为begin2,结束为end2,所以就会有以下三种情况越界:
1.end1越界,即end1>=n。
2.begin2越界,即begin2>n。
3.end2越界,即end2>=n。
所以我们要对边界进行修正,当边界>=n时,我们将其赋值为n-1,修正如下:
if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}
我们注意到当begin1>=n时,我们将begin2 赋值为n,end2赋值为n-1,我们发现这样的话这段区间就不存在了,这是为什么呢,我们来探究一下。


我们对程序进行以上的处理,发现程序崩溃了,通过调试发现是tmp数组越界了,那么tmp数组为什么会越界呢?

通过测试发现,本来只有十个数据,所以下标最多到9,但是tmp数组的下标10的位置插入元素,导致越界,这是因为当[begin2,end2]原本不存在,但是我们修正让其存在[9,9],多插入一个数据,所以导致越界,所以我们做一下修改。

处理过后就没有下标的越界了。
代码实现
当我们解决这个问题之后,其余代码按照思路实现就好了。
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("maolloc fail");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2*gap - 1;int InDex = i;if (end1 >= n){end1 = n - 1;}if (begin2 >= n){begin2 = n;end2 = n - 1;}if (end2 >= n){end2 = n - 1;}/*printf("[%d,%d] ", begin1, end1);printf("[%d,%d] ", begin2, end2);*/while (begin1 <= end1 && begin2 <= end2){//printf("%d ", InDex);if (a[begin1] < a[begin2]){tmp[InDex++] = a[begin1++];}else{tmp[InDex++] = a[begin2++];}}while (begin1 <= end1){//printf("%d ", InDex);tmp[InDex++] = a[begin1++];}while (begin2 <= end2){//printf("%d ", InDex);tmp[InDex++] = a[begin2++];}}for (int j = 0; j < n; j++){a[j] = tmp[j];}gap *= 2;}free(tmp);tmp = NULL;
}
总结
我们今天讲解了归并排序的递归和非递归的实现方法,码文不易,希望可以对大家有所帮助。
相关文章:
【数据结构初阶】一文带你学会归并排序(递归非递归)
目录 前言 递归实现 代码实现 非递归实现 代码实现 总结 前言 归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 作为一种典型的分而治之思想…...
Simulink壁咚(一)——What and How
目录 一、前言 二、Simulink 知多少 三、滤波算法 四、Model Verification 五、Model Coverage 六、Simulink测试实例 七、Simulink Test 八、Test Manager 九、Test Harness 十、 学习 一、前言 Simulink从2017b以后更加工程化和实用化,基于MBD的功能日趋…...
【PyTorch】Pytorch基础第0章
本文参加新星计划人工智能(Pytorch)赛道:https://bbs.csdn.net/topics/613989052 这是目录PyTorch的简介PyTorch 构建深度学习模型的步骤搭建pytorch使用环境PyTorch的简介 PyTorch 是一个开源的机器学习框架,由 Facebook 的人工智能研究院(…...
Android学习总结
积累熟练掌握 Java 语言,面向对象分析设计能力,反射原理,自定义注解及泛型,多次采用设计模式重构公司项目;熟练掌握 IVM 原理,反射,动态代理以及对 ClassLoader 热修复有比较深的理解࿱…...
虚拟机ubuntu安装samba服务
安装samba apt-get install samba 新建一个共享目录 mkdir /home/l/work chmod 777 /home/l/work 配置服务 配置 /etc/samba/smb.confsudo smbpasswd -a l(添加用户名名称) 防火墙关闭 Ubuntu中 我们使用命令查看当前防火墙状态; sudo ufw status inactive状态是防火墙关闭…...
开发板中的内存压力测试,你了解多少?
1. 测试目的内存压力测试的目的是评估开发板中的内存子系统性能和稳定性,以确保它能够满足特定的应用需求。开发板通常用于嵌入式系统、物联网设备、嵌入式智能家居等场景,这些场景对内存的要求通常比较高。其内存压力测试的主要目的有:1.对确…...
MATLAB | 这些花里胡哨的热图怎么画
好早之前写过一个绘制相关系数矩阵的代码,但是会自动求相关系数,而且画出来的热图只能是方形,这里写一款允许nan值出现,任意形状的热图绘制代码,绘制效果如下: 如遇到bug请后台提出,并去gitee下…...
Java开发的一些编码建议
1、无论是类、方法、字段、变量,尽可能的限制他们的作用范围,可以避免出现不必要的错误;同时虚拟机也能有更大的优化空间。 2、错误越早发现越好,编译时发生错误比在运行时发生错误好。而且编译时错误能更好的定位问题所在。 这…...
【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.59】引入ASPP模块
前言作为当前先进的深度学习目标检测算法YOLOv8,已经集合了大量的trick,但是还是有提高和改进的空间,针对具体应用场景下的检测难点,可以不同的改进方法。此后的系列文章,将重点对YOLOv8的如何改进进行详细的介绍&…...
C++STL set/multiset容器 构造和赋值 大小和交换 插入和删除 查找和统计
文章目录set/multiset容器1 set容器 基本概念2 set容器 构造和赋值3 set容器 大小和交换4 set容器 插入和删除5 set容器 查找和统计set/multiset容器 1 set容器 基本概念 简介: 所有元素都会在插入时会被自动排序,例如,在set容器放入元素1、…...
产品研发项目进度管理软件工具有哪些推荐?整理10款最佳进度管理软件
项目进度管理是确保项目按时完成的关键过程,使用合适的项目进度管理工具能确保帮助项目管理者实时了解和控制项目的进展情况,及时发现和解决问题,减少项目风险,提高项目效率和管理水平。这里将整理出国内外最受欢迎的10款项目进度…...
「ML 实践篇」分类系统:图片数字识别
目的:使用 MNIST 数据集,建立数字图像识别模型,识别任意图像中的数字; 文章目录1. 数据准备(MNIST)2. 二元分类器(SGD)3. 性能测试1. 交叉验证2. 混淆矩阵3. 查准率与查全率4. P-R 曲…...
从大专到测开,上海某字母站大厂的面试题,岗位是测开(25K*16)
简单介绍一句,大专出身,三年经验。跳了四次槽,面试了无数次,现在把自己的面试经验整理出来分享给大家,堪称必杀技! 1,一切从实际出发,对实际工作进行适当修饰 2,不会的简…...
【面试题】Python软件工程师能力评估试题(一)
文章目录前言应试者需知(一)Python 语言基础能力评估1、理解问题并完成代码:2、阅读理解代码,并在空白处补充完整代码:3、编写一个装饰器:exposer4、阅读代码并在空白处补充完整代码:5、自行用P…...
Java八股文(Java多线程面试题)
并行和并发的区别?(1)并行是指两个或者多个事件在同一时刻发生;而并发是指两个或多个事件在同一时间间隔发生;(2)并行是在不同实体上的多个事件,并发是在同一实体上的多个事件&#…...
小程序当前页面如何分享别的页面内容呢?
需求分析 因为功能的需要分为两点 他需要调转转发,并且有首页转发点击button按钮进行转发邀请好友帮忙助力,如何做到一个页面多种转发 如何区分,是button转发还剩右上角三个点转发呢? 通过onShareAppMessage()这个函数的事件…...
编写Java哪个编译器好
现在能够编写Java代码的工具简直不要太多,各种各样五花八门,但目前效率最高的还是Intellij Idea。但这个工具对于完全零基础的小白来说,第一次用起来是比较复杂的,因为它的功能太多了。这就好比你要学开车,如果上来就给…...
第十六章 Java为什么使用序列化
为何要指定serialVersionUID的值如果不指定显示serialVersionUID的值,jvm在序列化时会自动生成一个serialVersionUID,跟属性一起序列化,再进行持久化或者网络传输,在反序列化时,jvm会根据属性自动生成一个新版的serial…...
28岁小公司程序员,无车无房不敢结婚,要不要转行?
大家好,这里是程序员晚枫,又来分享程序员的职场故事了~ 今天分享的这位朋友叫小青,我认识他2年多了。以前从事的是土木行业,2年前找我咨询转行程序员的学习路线和职业规划后,通过自学加入了一家创业公司,成…...
出道即封神的ChatGPT,现在怎么样了?
从互联网的普及到智能手机,都让广袤的世界触手而及,如今身在浪潮中的我们,已深知其力。前阵子爆火的ChatGPT,不少人保持观望态度。现如今,国内关于ChatGPT的各大社群讨论,似乎沉寂了不少,现在怎…...
GAN与密码学的真实接口:从概念纠偏到工程落地
1. 项目概述:这不是密码学,也不是GAN训练指南,而是一场概念误读的深度解剖 “Understanding GAN Cryptography”——这个标题一出现,我就在笔记本上划了三道横线。不是因为难,而是因为它根本不存在。过去三年里&#x…...
大模型时代的技术人:要么驾驭AI,要么被AI驾驭——致软件测试从业者
测试者的新分水岭当ChatGPT在2022年底横空出世时,很多人还只是把它当作一个更会聊天的玩具。然而,仅仅数月之后,当GitHub Copilot 开始自动补全测试脚本,当AI能够在几秒钟内生成数十条高覆盖率的测试用例,当一张手绘草…...
全栈开发的核心技能:掌握这4个技术,成为全栈工程师
对于很多深耕测试领域多年的软件测试从业者来说,“转全栈开发”早已不是一个陌生的方向——无论是为了突破职业瓶颈,还是为了打通测试到开发的链路,提升自己的端到端交付能力,抑或是拓展职业选择的边界,全栈工程师都是…...
专业的郑州苹果手机维修联系电话口碑佳的
在当今数字化时代,苹果手机已成为人们生活中不可或缺的一部分。然而,手机使用过程中难免会出现各种故障,这时候选择一家专业靠谱的维修店就显得尤为重要。在郑州,果速修凭借其卓越的服务和良好的口碑,成为众多苹果用户…...
赛场制胜参考 CTF 全套 50 个经典解题思路
CTF选手必藏的50个实战解题思路!一篇够用! CTF竞赛的核心逻辑 • 核心目标:快速拆解问题(Flag导向)、工具链协作、模式化思维。• 关键原则:先广度后深度(优先收集信息)、分治策略&…...
精准数字化管控赋能医养融合
随着医养结合成为养老行业发展核心趋势,传统医养管理模式存在数据割裂、健康监测滞后、服务台账杂乱、管控统筹困难等问题,难以适配现代化康养机构运营需求。智慧养老医养管理数据大屏,聚焦医养融合核心场景,整合医疗健康与养老服…...
从MySQL迁移到GaussDB:一个后端开发者的初体验与核心操作对比(含表、索引、视图、联表查询)
从MySQL迁移到GaussDB:一个后端开发者的初体验与核心操作对比 作为一名长期使用MySQL的后端开发者,第一次接触GaussDB时既兴奋又忐忑。兴奋的是有机会体验国产数据库的强大性能,忐忑的是不知道这个"新朋友"会不会带来意想不到的挑战…...
使用 Taotoken CLI 工具一键配置团队开发环境中的大模型端点
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 使用 Taotoken CLI 工具一键配置团队开发环境中的大模型端点 在团队协作开发中,统一管理大模型 API 的接入配置是一个常…...
c# while循环 do while循环
while循环//while循环 //while(){}:当小括号条件成立 执行{}里面的东西,条件不成立的时候,循环就结束了while (true) //true 就是永远成立 一直执行{} {Console.WriteLine("死循环");break; //跳出死循环 只会执行一次 }while (tru…...
ChanlunX:为通达信注入缠论智能分析引擎
ChanlunX:为通达信注入缠论智能分析引擎 【免费下载链接】ChanlunX 缠中说禅炒股缠论可视化插件 项目地址: https://gitcode.com/gh_mirrors/ch/ChanlunX 在技术分析领域,缠论以其严谨的逻辑体系和独特的市场结构认知而备受推崇。然而,…...
