数据结构——lesson12排序之归并排序

news/2024/6/20 21:16:27/文章来源:https://blog.csdn.net/Renswc/article/details/137140629

💞💞 前言

hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
在这里插入图片描述

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记 、排序算法合集
💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

前面我们学习过六种排序——直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序和快速排序,今天我们就来学习归并排序🥳🎉🎉🎉

1.归并排序

基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序核心步骤:
在这里插入图片描述
归并排序的步骤类似于二叉树的后序遍历,先一直分解到不能再分,然后对两个子序列合并排序,最终得到全部排序好的序列;在这里插入图片描述

1.1归并排序(递归版)

在上图中我们看到它把序列拿下来排好后再放回原序列,归并排序需要在内存中重新开辟一个数组来存放排好的子序列,然后再拷贝回原数组,这样可以防止在原数组中操作困难以及很多错误的发生;
步骤:
①使用malloc函数开辟一个大小为原数组的空间存放在tmp中;
②重新构造递归函数(因为如果在原来的函数中递归,那么每次都会malloc开辟一个数组,不合适)_mergesort();
③分解数列,进行递归,创建mid遍量,从中间开始分割;
④当只有一个数时就不再分割(也就是begin>=end时);
⑤对子序列进行归并排序;

void _mergesort(int* a,int begin,int end, int* tmp)
{//递归结束条件if (begin >= end)return;//分左右区间int mid = (begin + end) / 2;_mergesort(a, begin, mid,tmp);_mergesort(a, mid+1, end,tmp);//归并排序int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1];begin1++;}else{tmp[i++] = a[begin2];begin2++;}}//如果最后begin1的序列有剩余while (begin1 <= end1){tmp[i++] = a[begin1++];}//如果最后begin2的序列有剩余while (begin2 <= end2){tmp[i++] = a[begin2++];}//最后再拷贝回原数组memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));}// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);_mergesort(a,0,n-1,tmp);free(tmp);//释放内存空间
}

结果如下:
上面一排是排序前,下面一排是用归并排序排完序后
在这里插入图片描述

1.2归并排序(非递归版)

归并排序非递归版主要是通过循环来实现两两归并;
步骤如下:
①使用malloc开辟tmp数组来存放归并好的数;
②创建gap来设定每次归并的序列的范围
③利用while循环来实现整个序列的多次归并;
while循环内部与递归的归并对子序列排序类似,不同的是需要嵌套for循环来实现多个gap范围的序列归并(因为此时已经将整个序列分成每gap个为一组,所以需要for循环来控制,使得这些序列全部都两两归并);
⑤归并完了后要使用memcpy函数将数据拷贝回原数组;

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//开辟数组来归并if (tmp == NULL){perror("malloc fail");return;}int gap = 1;//定义每次归并范围while (gap < n)//gap不能==n,因为此时?{int j = 0;//记录tmp数组下标//每次距离为gap的两组归并for (int i = 0; i < n; i+=2*gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){end1 = n - 1;break;}if (end2 >= n){end2 = n - 1;}//归并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1];begin1++;}else{tmp[j++] = a[begin2];begin2++;}}//如果最后begin1的序列有剩余while (begin1 <= end1){tmp[j++] = a[begin1++];}//如果最后begin2的序列有剩余while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));}gap *= 2;}free(tmp);
}

结果如下:
在这里插入图片描述

✨✨这里要注意两点:
🥳🥳(1)将数组每gap为一组分完后进行两两归并时,可能出现三种情况:
💥 ①到最后可能第一个序列存在,下一个序列不存在也就是begin2>=n的情况;
💥②还可能出现第一个序列只有一部分也就是end1>=n的情况;
💥 ③第二个序列只有一部分存在也就是end2>=n的情况;
出现①②两种情况说明最后一组只有一组或半组,这时不需要再归并,将end2 = n -1,并break跳出循环即可;
情况③有两组可以归并,但是第二组不完整,所以此时需要将end2 = n-1,不跳出循环继续归并即可;
🥳🥳(2)memcpy将tmp中归并的数拷贝回原数组时;
💥①可以考虑在for循环内部每次归并完两个序列后拷贝回去(上述代码就是使用这种)此时:
memcpy(a + i, tmp + i, sizeof(int)*(end2 - begin1 + 1))
要注意拷贝的位置要+i,并且拷贝的个数也应该是归并的两个序列的长度,(但是不能使用2*gap因为会出现上面的(1)问题,有可能序列不存在或部分存在)所以序列长度应该是end2 - i;
💥②可以在每次完整归并完距离为gap的序列后再进行拷贝,此时:
memcpy(a, tmp, sizeof(int) * n);
如下图所示:
此时不需要考虑拷贝的位置,直接全部拷贝即可;
在这里插入图片描述
??真的以为这么简单吗???不可能,绝对不可能😭😭
刚刚将十个数据0,1,2,3,4,5,6,7,8,9改成九个数据1,2,3,4,5,6,7,8,9结果如下:
在这里插入图片描述
可恶又错了,得重新捋一遍:
现在我们是要等for循环一遍将间距为gap的组两两归并,直到全部归并完再进行拷贝,之前是for循环内部每两组归并完就拷贝,那为什么全部归并完再拷贝会出错呢???
捋一遍发现:
if (end1 >= n || begin2 >= n) { end1 = n - 1; break; }
这里有问题,在只有一个序列或半个序列时,我们直接跳出了循环,也就是此时原数组后面的数根本没有输入到tmp数组里面,此时tmp后面的数是不知道是什么的,然后你再全部一拷贝回原数组,这样不仅不能排序,还会将原数组的数给覆盖掉,所以如果要使用: memcpy(a, tmp, sizeof(int) * n);
我们不能再次使用上面的if语句,需要改一改:

if (end1 >= n || begin2 >= n)
{end1 = n - 1;//break//不能跳出循环,需要将序列1的数录入到tmp数组中,所以只要设置序列2不存在即可//要是序列2不存在,只需begin2 > end2 即可begin2 = i + 1;end2 = i;
}

结果如下:
在这里插入图片描述
此时就可以使用 memcpy(a, tmp, sizeof(int) * n);啦🥳🥳🥳

注意不可以在跳出break循环后再进行拷贝哦~因为这样没办法知道之前归并好的数据是什么,所以没办法进行归并排序💫💫

2.归并排序复杂度分析

2.1空间复杂度

无论递归还是非递归,我们都使用malloc函数开辟了tmp数组,大小是n,所以它的空间复杂度是O(n);🥳🥳🥳

2.2时间复杂度

我们可以利用非递归的来看归并排序的时间复杂度:
①首先,无论gap是什么,都需要借助for循环来遍历一遍数组进行归并排序每一遍都是n;
②所以只需要确定while循环多少次即可,有因为while循环条件是gap < n,每次gap*=2;
③所以while循环log(n)次所以归并排序非递归的时间复杂度是O(nlogn);
而非递归是利用while循环对递归的另一种表现形式,它们的原理逻辑都是一样的,所以递归版的时间复杂度也应该是O(n
logn);🥳🥳🥳

3.结语

我们学习了归并排序的两种实现——递归与非递归版;并分析了归并排序的时间和空间复杂度,以上就是归并排序的所有内容啦~ 完结撒花~🥳🎉🎉🎉

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

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

相关文章

【CANN训练营笔记】AscendCL图片分类应用(C++实现)

样例介绍 基于PyTorch框架的ResNet50模型&#xff0c;对*.jpg图片分类&#xff0c;输出各图片所属分类的编号、名称。 环境介绍 华为云AI1s CPU&#xff1a;Intel Xeon Gold 6278C CPU 2.60GHz 内存&#xff1a;8G NPU&#xff1a;Ascend 310 环境准备 下载驱动 wget ht…

小折叠手机无法使用车上的无线充电?车和手机都没问题

最近看到一个案例——一位新入手Pocket 2的机主&#xff0c;发现自己的手机无法在车上进行无线充电。检查了手机和汽车都没问题&#xff0c;折腾大半天结果发现是电磁线圈没对准无线充电的位置。 无线充电的原理是手机的无线充电电磁线圈对准电磁线圈&#xff0c;通过电磁波感…

Wireshark TS | HTTP 传输文件慢问题

问题背景 之前有几篇文章写过关于应用传输慢的问题&#xff0c;延用之前的老套话&#xff0c;应用传输慢是一种比较常见的问题&#xff0c;慢在哪&#xff0c;为什么慢&#xff0c;有时候光从网络数据包分析方面很难回答的一清二楚&#xff0c;毕竟应用的定义范围实在太广&…

汽车租赁(源码+文档)

汽车租赁&#xff08;小程序、ios、安卓都可部署&#xff09; 文件包含内容程序简要说明含有功能项目截图客户端登录界面首页订单个人信息我的界面新手指引注册界面车型选择支付界面修改信息 管理端用户管理订单管理分类管理 文件包含内容 1、搭建视频 2、流程图 3、开题报告 …

vue3+threejs新手从零开发卡牌游戏(二十四):添加p2战斗逻辑

用代码模拟p2战斗逻辑&#xff0c;按流程进行步骤拆分&#xff1a; 1.p2抽卡 2.p2召唤怪兽上场 3.p2战斗 其中战斗部分分为几种情况&#xff1a; 情况一&#xff1a;p2场上卡牌由大到小进行排序&#xff0c;按序轮询可以攻击的卡牌&#xff0c;然后攻击p1场上卡牌由大到小…

[蓝桥杯嵌入式]hal库 stm32 (DMA串口1收发,采用空闲中断方法)

前言&#xff1a; 本系列教程将 对应外设原理&#xff0c;HAL库与STM32CubeMX结合在一起讲解&#xff0c;使您可以更快速的学会各个模块的使用 所用工具&#xff1a; 1、芯片&#xff1a; STM32G431RBT6 2、STM32CubeMx软件 3、IDE&#xff1a; MDK-Keil软件 4、STM32G4xx…

supersqli-攻防世界

题目 加个报错 1 and 11 #没报错判断为单引号字符注入 爆显位 1 order by 2#回显正常 1 order by 3#报错 说明列数是2 尝试联合查询 -1 union select 1,2# 被过滤了 return preg_match("/select|update|delete|drop|insert|where|\./i",$inject); select|update|d…

SpringBoot+thymeleaf完成视频记忆播放功能

一、背景 1)客户要做一个视频播放功能,要求是系统能够记录观看人员在看视频时能够记录看到了哪个位置,在下次观看视频的时候能够从该位置进行播放。 2)同时,也要能够记录是谁看了视频,看了百分之多少。 说明:由于时间关系和篇幅原因,我们这里只先讨论第一个要求,第…

Lambda表达式,Stream流

文章目录 Lambda表达式作用前提函数式接口特点 语法省略模式和匿名对象类的区别 Stream流思想作用三类方法获取方法单列集合(Collection[List,Set双列集合Map(不能直接获取)数组同一类型元素(Stream中的静态方法) 常见的中间方法终结方法收集方法 Optional类 Lambda表达式 作用…

HarmonyOS 应用开发之通过标准化数据通路实现数据共享

场景介绍 在多对多跨应用数据共享的场景下&#xff0c;需要提供一条数据通路能够接入多个不同应用的数据并共享给其他应用进行读取。 UDMF针对多对多跨应用数据共享的不同业务场景提供了标准化的数据通路&#xff0c;提供了标准化的数据接入与读取接口。 标准化数据通路的定…

3.java openCV4.x 入门-数据类型(CvType)与Scalar

专栏简介 &#x1f492;个人主页 &#x1f4f0;专栏目录 点击上方查看更多内容 &#x1f4d6;心灵鸡汤&#x1f4d6;我们唯一拥有的就是今天&#xff0c;唯一能把握的也是今天 &#x1f9ed;文章导航&#x1f9ed; ⬆️ 2.hello openCV ⬇️ 4.待更新 数据类型&#xff…

Leaflet使用多面(MultiPolygon)进行遥感影像掩膜报错解决之道

目录 前言 一、问题初诊断 1、山重水复 2、柳暗花明 3、庖丁解牛 4、问题定位 二、解决多面掩膜问题 1、尝试数据修复 2、实际修复 3、最终效果 三、总结 前言 之前一篇讲解遥感影像掩膜实现&#xff1a;基于SpringBoot和Leaflet的行政区划地图掩膜效果实战&#xff0…

Shell脚本介绍及基本功能

目录 一、什么是Shell 二、什么是Shell脚本 三、echo 四、Hello World 五、Bash的基本功能 1.别名 2.常用快捷键 3.输入输出 4.输出重定向 5.多命令执行 6.管道符 7.通配符和特殊符合 一、什么是Shell Shell是一种命令行解释器&#xff0c;它是操作系统的一部分&a…

MySQL进阶-----SQL提示与覆盖索引

目录 前言 一、SQL提示 1.数据准备 2. SQL的自我选择 3.SQL提示 二、覆盖索引 前言 MySQL进阶篇的索引部分基本上要结束了&#xff0c;这里就剩下SQL提示、覆盖索引、前缀索引以及单例联合索引的内容。那本期的话我们就先讲解SQL提示和覆盖索引先&#xff0c;剩下的内容就…

nvme协议学习总结

一、nvme命令 1 nvme在pcie基础上的协议&#xff0c;与PCIE配合&#xff0c;实现高效传输。 2 nvme命令主要分IO命令和admin命令。 3 一个NVME CMD执行流程&#xff1a; step1&#xff1a;host把cmd写入SQ queue中&#xff1b; step2&#xff1a;host远端更新Device&#x…

【微服务】OpenFeign+Sentinel集中处理远程调用异常

文章目录 1.微服务基本环境调整1.对10004模块的application.yml调整2.启动nacos以及一个消费者两个提供者3.测试1.输入http://localhost:8848/nacos/index.html 来查看注册情况2.浏览器访问 http://localhost:81/member/nacos/consumer/get/13.结果 2.使用OpenFeign实现微服务模…

什么是nginx正向代理和反向代理?

什么是代理&#xff1f; 代理(Proxy), 简单理解就是自己做不了的事情或实现不了的功能&#xff0c;委托别人去做。 什么是正向代理&#xff1f; 在nginx中&#xff0c;正向代理指委托者是客户端&#xff0c;即被代理的对象是客户端 在这幅图中&#xff0c;由于左边内网中…

6.Python容器类型的数据

若我们想将多个数据打包并且统一管理&#xff0c;应该怎么办&#xff1f; Python内置的数据类型如序列&#xff08;列表、元组等&#xff09;、集合和字典等可 以容纳多项数据&#xff0c;我们称它们为容器类型的数据 1 序列 序列&#xff08;sequence&#xff09;是一种可迭…

MYSQL-6.日志

日志 undo-log回滚日志&#xff1a; 存储&#xff1a;InnoDB默认将undo-log日志存储在xx.ibdata共享表数据文件中&#xff08;Mysql5.5版本后支持单独存放&#xff09;&#xff0c;采用段形式存储&#xff1b;在xx.ibdata共享表数据文件中&#xff0c;有一块名为Rollback segm…

hcip综合实验2

目录 实验拓扑&#xff1a; 实验要求&#xff1a; 实验思路&#xff1a; 实验步骤&#xff1a; 1.配置设备接口IP 2.通过配置缺省路由让公网互通 3.配置ppp 1.R1和R5间的ppp的PAP认证&#xff1b; 2.R2与R5之间的ppp的CHAP认证; 3. R3与R5之间的HDLC封装; 4.构建R1、…