当前位置: 首页 > news >正文

归并排序含非递归版

目录

1.归并排序的原理

 2.实现归并排序

2.1框架

2.2区间问题和后序遍历

2.3归并并拷贝

2.4归并排序代码

2.5测试

3.非递归实现归并排序 

3.1初次实现

3.2测试 

3.3修改

 3.4修改测试


1.归并排序的原理

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;

即先使每个子序列有序,再使子序列段间有序   若将两个有序表合并成一个有序表,称为二路归并。 

可以将数组内容想象成一颗二叉树,通过递归的方式将数组的内容分为左子树和右子树,分出来的左子树和右子树又分别有它们的左子树和右子树。不断地向下进行拆分,直到拆分到没有对应区间和区间只有一个元素(有序)的时候便递归返回。然后使用归并的方式将左子树和右子树归并成有序数组,再将其拷贝会原数组,这样对应的子树便会有序,再递归返回,不断地递归。直到根左子树和根右子树有序,再归并和拷贝,整个数组就会变得有序。

如图所示:

 2.实现归并排序

归并排序需要开额外的空间来辅助实现   之所以不在原数组实现,是因为如果你使用交换的方式来进行排序,可能会将原数组已经排好序的部分又一次变回无序,而使用令数组向后移动的方式进行对应的排序,时间复杂度便会大大增加,因此归并排序可以理解成一种以空间换时间的排序方法。

归并排序需要开额外的空间,但每次递归都要开空间显然是不合理的,因此我们使用一个函数来完成递归的部分。思考一下,新创建的函数的参数应该有哪些,首先得有原数组,其次得有我们开辟好的数组,而我们要如二叉树一般形成对应的递归,显然需要区间,而区间的形成需要两个数来辅助,因此可以传递两个代表区间的数进来,可以取名为begin,end(left,right),这样理解起来轻松一些。

2.1框架

2.2区间问题和后序遍历

如二叉树一般实现后序遍历注意: 当begin>=end时代表着区间不存在或者只有一个元素(有序)的时候返回。因为是后序遍历,需要先将区间的分界给计算出来之后才能使用。

2.3归并并拷贝

可以看出,每次递归都会有两个区间的生成[begin,mid]和[mid+1,end]我们的目标就是将这两个区间归并在一起,这个很简单,循环便可以搞定。注意:两个区间不知道是哪个区间先完成循环,因此在外面需要将未完成循环的区间,补充回辅助数组中。

搞定完归并后,使用memcpy将辅助数组中的内容拷贝回原数组,排序便结束了。注意:我们传递的是闭区间,因此拷贝的长度为,end-begin+1

2.4归并排序代码

void MergeSort(int*arr,int n)
//将数组和数组的元素个数传递过来
{int* a = (int*)malloc(sizeof(int)*n);//创建辅助数组if (a == NULL){perror("malloc fail");return;}_MergeSort(arr,a,0,n-1);free(a);
}
void _MergeSort(int*arr,int*a,int begin ,int end)
{//检验区间是否有效if (begin >= end){return;}//后序遍历int mid = (begin + end) / 2;//新区间为[begin,mid],[mid+1,end]_MergeSort(arr,a,begin,mid);_MergeSort(arr,a,mid+1,end);//归并int begin1 = begin; int end1 = mid;int begin2 = mid+1; int end2 = end;//两个区间int index = begin;//新区间第一个元素的下标while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){a[index++] = arr[begin1++];}else{a[index++] = arr[begin2++];}}while (begin1 <= end1){a[index++] = arr[begin1++];}while (begin2 <= end2){a[index++] = arr[begin2++];}//将归并好的内容拷贝回原数组memcpy(arr+begin,a+begin,(end-begin+1)*sizeof(int));
}

2.5测试

3.非递归实现归并排序 

根据我们之前的排序我们可以看到它的本质是和预排序差不多的形态,因此我们可以通过一个整型如gap来区分一个元素和一个元素排序,两个元素和两个元素排序.......

3.1初次实现

void MergeSortNonR(int* arr, int n)
{int* a = (int*)malloc(sizeof(int) * n);//创建辅助数组int gap = 1;//gap=1便是1个元素和1个元素归并while (gap < n){int i = 0;for (i = 0; i < n; i += 2 * gap)//i+=2*gap跳过一整个区间{//两个区间int begin1 = i; int end1 = i + gap - 1;int begin2 = i + gap; int end2 = i + 2 * gap - 1;int index = i;	//新区间第一个元素的下标//归并while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){a[index++] = arr[begin1++];}else{a[index++] = arr[begin2++];}}while (begin1 <= end1){a[index++] = arr[begin1++];}while (begin2 <= end2){a[index++] = arr[begin2++];}memcpy(arr + i, a + i, sizeof(int) * (2 * gap));}gap *= 2;}free(a);
}

3.2测试 

出现了越界问题

程序在打印之前就被迫中止了

 

3.3修改

观察可以发现,第一个区间的为[begin1,end1],第二个区间为[begin2,end2],那么begin1必然不会越界,而end1和更后面的begin2,end2都可能会越界。而其中end1和begin2越界的话都在说明已经排好序了,而end2越界,begin2没越界,则在说明还有数据未被排序。

再想一想细节,end1越界了,begin2一定越界,而begin2越界,end1不一定越界,所以无需考虑end1越界,只要begin2越界就说明排序已完成直接break   而只有end2越界,便将end2修正成数组的最大下标即可。

注意:我们之前使用拷贝函数均是拷贝2*gap个过去,在这里显然不合适,总区间长度应修正 为end2-begin1,这个修正不应该放在最后,因为在进行归并的期间,begin1会++至end1   也不应该放在判断begin2,end2越界之前,因为可能会对end2进行修正。综上所述,得出的代码为

void MergeSortNonR(int* arr, int n)
{int* a = (int*)malloc(sizeof(int) * n);//创建辅助数组int gap = 1;//gap=1便是1个元素和1个元素归并while (gap < n){int i = 0;for (i = 0; i < n; i += 2 * gap)//i+=2*gap跳过一整个区间{//两个区间int begin1 = i; int end1 = i + gap - 1;int begin2 = i + gap; int end2 = i + 2 * gap - 1;if (begin2 >= n){break;}if (end2 >= n)end2 = n - 1;//修正区间长度int order = end2 - begin1+1;//修正要拷贝的长度int index = i;	//新区间第一个元素的下标//归并while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){a[index++] = arr[begin1++];}else{a[index++] = arr[begin2++];}}while (begin1 <= end1){a[index++] = arr[begin1++];}while (begin2 <= end2){a[index++] = arr[begin2++];}/*int order = 2 * gap;if (2 * gap >= n){order = n;}*/memcpy(arr + i, a + i, sizeof(int) * order);}gap *= 2;}free(a);
}

 3.4修改测试

至此,归并排序的递归版和非递归版讲解完成,感谢各位友友的来访,祝各位友友前程似锦O(∩_∩)O 

相关文章:

归并排序含非递归版

目录 1.归并排序的原理 2.实现归并排序 2.1框架 2.2区间问题和后序遍历 2.3归并并拷贝 2.4归并排序代码 2.5测试 3.非递归实现归并排序 3.1初次实现 3.2测试 3.3修改 3.4修改测试 1.归并排序的原理 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治…...

项目进展(八)-编写代码,驱动ADS1285

一、代码 根据芯片的数据手册编写部分驱动&#xff0c;首先看部分引脚的波形&#xff1a; DRDY: CS&#xff1a; 首先在代码初始化时连续写入三个寄存器&#xff1a; void WriteReg(uint8_t startAddr, uint8_t *regData, uint8_t number) {uint8_t i0;// 循环写number1次…...

【MyBatis-Plus】快速精通Mybatis-plus框架—快速入门

大家在日常开发中应该能发现&#xff0c;单表的CRUD功能代码重复度很高&#xff0c;也没有什么难度。而这部分代码量往往比较大&#xff0c;开发起来比较费时。 因此&#xff0c;目前企业中都会使用一些组件来简化或省略单表的CRUD开发工作。目前在国内使用较多的一个组件就是…...

docker 安装kafka

运行容器 zookeeper: [rootk8s-master ~]# docker run -d --restartalways --log-driver json-file --log-opt max-size100m --log-opt max-file2 --name zookeeper -p 2181:2181 -v /etc/localtime:/etc/localtime zookeeper c603f292813cfd6e2b16fff88a9767cc86fc9bba34d82…...

容器内获得apiserver地址

1.容器的Env的KUBENETES_SERVICE_HOST字段 roottomcat01-69fc8f859b-w9btn:/tmp# env | grep KUBERNETES_SERVICE_HOST10.96.0.1 KUBERNETES_SERVICE_HOST10.96.0.12.通过域名查询 nslookup getent hosts roottomcat01-69fc8f859b-w9btn:/tmp# getent hosts kubernetes.def…...

linux服务端c++开发工具介绍(vscode版)

本文适合于有一定c开发经验&#xff0c;但是还不明确如何到linux服务端开发程序的同学。 一、vscode 几年前用的是ssh到云服务上&#xff0c;再用vim在云上开发的形式 ssh dongbeijing.dbj11.158.142.176 vim hello.c 现今&#xff0c;由于vscode比较好用&#xff0c;这几年…...

Linux常用命令大全

Linux常用命令大全 一、文件&目录管理1. 文件和目录操作命令2. 查看文件及内容处理命令3. 文件压缩及解压缩命令4. 搜索文件命令5. 其他 二、Linux 软件包管理三、用户管理1. 用户管理2. 查看系统用户登陆信息的命令 四、进程管理五、网络通信1. 基础网络操作命令2. 深入网…...

Python中取2023, 9, 1——2023, 10, 31的全部时间

使用datetime.date()函数定义了开始和结束日期。然后&#xff0c;我们使用datetime.timedelta()类创建了一个时间范围&#xff0c;其中n表示从开始日期到结束日期之间的天数。最后&#xff0c;我们使用一个for循环迭代时间范围内的日期&#xff0c;并打印每个日期。示例代码演示…...

创建django文件

1、在指定目录里打开终端&#xff0c;输入D:\Softwares\Anaconda3\envs\pytorch\Scripts\django-admin .exe startproject 名称 &#xff0c;即可在对应目录里创建django文件。...

全排列[中等]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给定一个不含重复数字的数组nums&#xff0c;返回其所有可能的全排列。你可以按任意顺序返回答案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例…...

mybatise-plus的id过长问题

一、问题情景 笔者在做mp插入数据库(id已设置为自增)操作时&#xff0c;发现新增数据的id过长&#xff0c;结果导致前端JS拿到的数据出现了精度丢失问题&#xff0c;原因是后端id的类型是Long。在网上查了一下&#xff0c;只要在该属性上加上如下注解就可以 TableId(value &q…...

图示矩阵分解

特征值与特征向量 设 A A A 是 n 阶矩阵&#xff0c;如果存在数 λ \lambda λ 和 n 维非零列向量 x x x&#xff0c;满足关系式&#xff1a; A x λ x ( 1 ) Ax \lambda x\quad\quad(1) Axλx(1) 则数 λ \lambda λ 称为矩阵 A A A 的特征值&#xff0c;非零向量 x…...

六、互联网技术——数据存储

文章目录 一、存储系统层次结构二、按照重要性分类三、磁盘阵列RAID三、RAID基础四、磁盘阵列分级五、数据备份与恢复六、容灾与灾难恢复 一、存储系统层次结构 常见的三层存储体系结构如下图所示&#xff0c;分为高速缓冲存储器、主存储器和外存储器。 二、按照重要性分类 …...

六、vpp 流表+负载均衡

草稿&#xff01;&#xff01;&#xff01; vpp node其实就是三个部分 1、plugin init 2、set command 3、function 实现功能&#xff0c;比如这里的流表 今天我们再用VPP实现一个流表的功能 一、流表 1.1流表----plugin init VLIB_REGISTER_NODE 注册流表节点 // 注册流…...

word已排序好的参考文献,插入新的参考文献,序号更新

原排序好的文献序号。 现在在3号后面插入一个新文献。4&#xff0c;5号应该成为5&#xff0c;6 这时在3号后面&#xff0c;回车&#xff0c;就会自动的增长。如下图&#xff1a; 但是如果手滑&#xff0c;把[4]删除了如何排序&#xff1f;&#xff1f; 如下图&#xff1a; …...

二叉树的顺序存储——堆——初识堆排序

前面我们学过可以把完全二叉树存入到顺序表中&#xff0c;然后利用完全二叉树的情缘关系&#xff0c;就可以通过数组下标来联系。 但是并不是把二叉树存入到数组中就是堆了&#xff0c;要看原原来的二叉树是否满足&#xff1a;所有的父都小于等于子&#xff0c;或者所有的父都…...

CYEZ 模拟赛 9

A a ⊥ b ⇒ a − b ⊥ a b (1) a \perp b \Rightarrow a-b \perp ab \tag {1} a⊥b⇒a−b⊥ab(1) 证明&#xff1a; gcd ⁡ ( a , b ) gcd ⁡ ( b , a − b ) \gcd(a,b) \gcd(b, a-b) gcd(a,b)gcd(b,a−b)&#xff0c;故 a − b ⊥ b a - b \perp b a−b⊥b&#xff0c;同…...

typescript: Builder Pattern

/*** file: CarBuilderts.ts* TypeScript 实体类 Model* Builder Pattern* 生成器是一种创建型设计模式&#xff0c; 使你能够分步骤创建复杂对象。* https://stackoverflow.com/questions/12827266/get-and-set-in-typescript* https://github.com/Microsoft/TypeScript/wiki/…...

WPS/word 表格跨行如何续表、和表的名称

1&#xff1a;具体操作&#xff1a; 将光标定位在跨页部分的第一行任意位置&#xff0c;按下快捷键ctrlshiftenter&#xff0c;就可以在跨页的表格上方插入空行&#xff08;在空行可以写&#xff0c;表1-3 xxxx&#xff08;续&#xff09;&#xff09; 在空行中输入…...

Python的NumPy库(一)基础用法

NumPy库并不是Python的标准库&#xff0c;但其在机器学习、大数据等很多领域有非常广泛的应用&#xff0c;NumPy本身就有比较多的内容&#xff0c;全部的学习可能涉及许多的内容&#xff0c;但我们在这里仅学习常见的使用&#xff0c;这些内容对于我们日常使用NumPy是足够的。 …...

uniapp app 导出excel 表格

直接复制运行 <template><view><button click"tableToExcel">导出一个表来看</button><view>{{ successTip }}</view></view> </template><script>export default {data() {return {successTip: }},metho…...

【RabbitMQ】常用消息模型详解

文章目录 AMQP协议的回顾RabbitMQ支持的消息模型第一种模型(直连)开发生产者开发消费者生产者、消费者开发优化API参数细节 第二种模型(work quene)开发生产者开发消费者消息自动确认机制 第三种模型(fanout)开发生产者开发消费者 第四种模型(Routing)开发生产者开发消费者 第五…...

图像拼接后丢失数据,转tiff报错rasterfile failed: an unknown

图像拼接后丢失数据 不仅是数据丢失了&#xff0c;还有个未知原因报错 部分数据存在值不存在的情况 原因 处理遥感数据很容易&#xff0c;磁盘爆满了 解决方案 清理一些无用数据&#xff0c;准备买个2T的外接硬盘用着了。 然后重新做处理...

Nginx之日志模块解读

目录 基本介绍 配置指令 access_log&#xff08;访问日志&#xff09; error_log&#xff08; 错误日志&#xff09; 基本介绍 Nginx日志主要分为两种&#xff1a;access_log(访问日志)和error_log(错误日志)。Nginx日志主要记录以下信息&#xff1a; 记录Nginx服务启动…...

latex方程组编写,一种可以保证方程编号自适应的方法

问题描述&#xff1a; 在利用latex编写方程组时&#xff0c;可以有很多种方法&#xff0c;但不总是编辑好的公式能够显示出编号&#xff0c;故提出一种有效的方程组编写方法 方法&#xff1a; \begin{equation}X_{ t1}\left \{ \begin{matrix}\frac{x_{i}}{a} \quad\quad 0&l…...

深度学习基础 2D卷积(1)

什么是2D卷积 2D参数量怎么计算 以pytorch为例子&#xff0c;2D卷积在设置的时候具有以下参数&#xff0c;具有输入通道的多少&#xff08;这个决定了卷积核的通道数量&#xff09;&#xff0c;滤波器数量&#xff0c;这个是有多少个滤波器&#xff0c;越多提取的特征就越有用…...

OpenCV DNN C++ 使用 YOLO 模型推理

OpenCV DNN C 使用 YOLO 模型推理 引言 YOLO&#xff08;You Only Look Once&#xff09;是一种流行的目标检测算法&#xff0c;因其速度快和准确度高而被广泛应用。OpenCV 的 DNN&#xff08;Deep Neural Networks&#xff09;模块为我们提供了一个简单易用的 API&#xff0…...

第八章 Linux文件系统权限

目录 8.1 文件的一般权限 1.修改文件或目录的权限---chmod命令 2.对于文件和目录&#xff0c;r&#xff0c;w&#xff0c;x有不同的作用&#xff1a; 3.修改文件或目录的所属主和组---chown,chgrp 8.2 文件和目录的特殊权限 三种通过字符描述文件权限 8.3 ACL 权限 1.A…...

XXL-JOB源码梳理——一文理清XXL-JOB实现方案

分布式定时任务调度系统 流程分析 一个分布式定时任务&#xff0c;需要具备有以下几点功能&#xff1a; 核心功能&#xff1a;定时调度、任务管理、可观测日志高可用&#xff1a;集群、分片、失败处理高性能&#xff1a;分布式锁扩展功能&#xff1a;可视化运维、多语言、任…...

java做个qq机器人

前置的条件 机器人是基于mirai框架实现的。根据官方的文档&#xff0c;建议使用openjdk11。 我这里使用的编辑工具是idea2023 在idea中新建一个maven项目&#xff0c;虽然可以使用gradle进行构建&#xff0c;不过我这里由于网络问题没有跑通。 pom.xml <dependency>&l…...

怎么自己做公司网站/怎么做网络推广优化

一、地址映射 在正式编写驱动前需要先简单了解一下 MMU 这个神器&#xff0c;MMU 全称叫做 Memory Manage Unit&#xff0c;也就是内存管理单元。在老版本的 Linux 中要求处理器必须有 MMU&#xff0c;但是现在Linux 内核已经支持无 MMU 的处理器了。MMU 主要完成的功能如下&a…...

动态网站开发的前景/百度霸屏推广靠谱吗

报告类型&#xff1a;产业研究报告格式&#xff1a;电子版、纸介版、电子纸介出品单位&#xff1a;智研咨询官网链接&#xff1a;中国产业信息网 - 产业前景投资趋势门户-智研旗下产业信息咨询平台​www.chyxx.com报告链接&#xff1a;2021-2027年中国载货电梯行业市场调查研究…...

在凡科做的网站怎么推广/小程序开发公司哪里强

MicHTTP错误列表 HTTP 400 - 请求无效 HTTP 401.1 - 未授权&#xff1a;登录失败 HTTP 401.2 - 未授权&#xff1a;服务器配置问题导致登录失败 HTTP 401.3 - ACL 禁止访问资源 HTTP 401.4 - 未授权&#xff1a;授权被筛选器拒绝 HTTP 401.5 - 未授权&#xff1a;ISAPI 或…...

wordpress放在其他端口/seo国外推广软件

【转】https://blog.csdn.net/qq_31841675/article/details/82625289最近电脑总是莫名其妙的自动关闭屏幕&#xff0c;常规办法都不好使。非逼着我使大招&#xff0c;多谢这位高手。本人电脑自带win10系统&#xff0c;设置如下&#xff1a;解决步骤&#xff1a;1、win R&#…...

福州做网站公司排名/如何引流与推广

ubuntu 开源镜像存档日期&#xff1a;2019年5月15日 | 首次发布&#xff1a;2009年8月25日 在当今的经济形势下&#xff0c;每个人都在寻找减少开支的方法。 在IT部门中&#xff0c;减少开支的一种方法是转向开源替代方案&#xff0c;而不是使用昂贵的许可产品。 在这个“ 用开…...

只使用html做简单网站/app广告联盟平台

Cordova - 实现热更新 ! 原文:Cordova - 实现热更新 !Cordova版本&#xff1a;8.0.0 更新APP平台&#xff1a;Android 操作系统&#xff1a;Windows Cordova的热更新&#xff0c;作用是把www内的变动部分更新到APP中&#xff0c;实现主程序不动&#xff0c;完成更新&#xff01…...