一起学数据结构(12)——归并排序的实现
1. 归并排序原理:
归并排序的大概原理如下图所示:

从图中可以看出,归并排序的整体思路就是把已给数组不断分成左右两个区间,当这个区间中的数据数量到达一定数值时,便返回去进行排序,整体的结构类似二叉树的结构,因此,对于归并排序同样可以利用递归进行实现。
对于递归实现归并排序,首先需要实现的第一步便是如何区分左右区间,在快速排序中,虽然在递归时依然同样需要根据一个值来区分左右区间,但是用于区分左右区间的值是在左右两边遍历数组时自动选出来的,对于归并排序,通过观察可以发现,归并排序的左右区间是通过数组下标的中间值进行区分的,为了方便表示,将这个中间值命名为,例如,数组在进行第一次区分左右区间时,左区间的范围是
,右区间的范围是
,通过计算不难得到
,所以,对于数组左右区间的划分,可以通过
,
(数组下标起始),
(数组下标末位来划分)即
左区间范围:
右区间范围:
同时,在图中当区间中的数值数量为后,下一步直接进行排序,此处图中省略了区间分为两个区间数值数量为
的两个区间的过程,这是因为,在区间中的数值数量
时,便停止划分区间
所以,对于区间划分这部分的递归,可以用代码表示为:
//归并排序void _MergeSort(int* a, int begin, int end){if (begin >= end){return;}int mid = (begin + end) / 2;MergeSort(a, begin, mid);MergeSort(a,mid + 1, end);}
在区间划分结束后,就需要对数组进行排序。这里需要注意,在进行排序时,不能直接在原本已有的数组进行排序,为了解决这个问题,本文选择独立开辟一块空间用于排序,当一部分区间在这部分空间排序完成后,便将这部分内容返回到原数组,开辟空间的过程如下:
void MergeSort(int* a, int begin, int end){int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));if (tmp == NULL){perror("malloc fail");}_MergeSort(a, tmp, begin, end);}
因为开辟的空间需要在上面的函数中使用,所以对于函数的定义需要更改为上图中的格式。
对于如何排序,文章给出下面的方法:
对于一个区间,定义四个变量,分别为:,
,
,具体使用方法如下:
令,
,
,
,具体使用方法如下方的代码所示:
//归并排序void _MergeSort(int* a,int* tmp, int begin, int end){if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a,tmp, begin, mid);_MergeSort(a,tmp,mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;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 + begin, tmp + begin, sizeof(int) * (end - begin + 1));}
为了方便解释代码内容,给出下面的图像:

首先对左右区间进行区分,期间各个区间的,
,
,如图所示,当区间数据数量
时,停止区分区间进行排序,例如对
这个区间,如果
,则让小的哪个值插入到
,此时
中的内容如下图所示:

向原数组拷贝数值后,原数组左区间数值如下:

在区间遍历完成后,再遍历
区间,由于
的不同,再数据调整完拷贝到
后,
数组内容为:
随后再向原数组中拷贝,原数组内容为
对于其他的序列,依旧按照此规律,此部分不再叙述。
测试函数如下:
void TestMergeSort()
{int i[] = { 10,6,7,1,3,9,4,2 };int size = sizeof(i) / sizeof(int);MergeSort(i, 0, size - 1);printf("归并排序:");ArrayPrint(i, size);
}
运行结果如下:

相关文章:
一起学数据结构(12)——归并排序的实现
1. 归并排序原理: 归并排序的大概原理如下图所示: 从图中可以看出,归并排序的整体思路就是把已给数组不断分成左右两个区间,当这个区间中的数据数量到达一定数值时,便返回去进行排序,整体的结构类似二叉树…...
读书笔记之《敏捷测试从零开始》(一)
大家好,我是rainbowzhou。 子曰:学而时习之,不亦说乎?今天我想和大家分享一本测试书籍——《敏捷测试从零开始》。以下为我的读书笔记: 精彩片段摘录: 焦虑往往来自于对比,当你在自己的圈子里面…...
视频亮度太低了,如何调高
充足、均匀、稳定的光亮对于视频制作是至关重要的,在现实生活中,不可预见的天气变化和拍摄地方的阴暗常常给我们留下暗淡无光的视频片段。 如果你的视频太暗想知道如何使它变亮,且又不知道使用哪个工具,那你无需担心,因…...
Xubuntu16.04系统中安装create_ap创建无线AP
1.背景说明 在Xubuntu16.04系统的设备上安装无线WIFI模块后,想通过设备自身的无线AP,进行和外部设备的连接,需要安装create_ap软件,并设置无线AP的名称和密码,并设置为开机自启动。 create_ap是一个用于在Linux系统上创…...
WPF 设置全局静态参数
可以使用system官方库来设置参数 引入system xmlns:system"clr-namespace:System;assemblymscorlib"设置参数资源 <Window.Resources><system:Double x:Key"ButtonWidth">90</system:Double></Window.Resources>使用参数资源 &l…...
Leetcode链表问题汇总
目录 [2. 两数相加](https://leetcode.cn/problems/add-two-numbers/)[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)[206. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii/)[19. 删除链表的倒数第 N 个结点](https://leetcode.cn/p…...
基于卷的磁盘扫描算法设计
1、设计目的 常规情况下,当我们扫描计算机的硬盘时, 通常会使用诸如FindFirstFile/FindNextFile(Windows),或者opendir/readdir(Linux)遍历扫描的目录。 一般情形下,由于文件数量相对较少,文件夹层次低,扫…...
计算机组成原理-存储器概念
计算机组成原理-存储器 存储系统的基本概念 1.层次结构 可以直接被CPU读取: 高速缓存:cache主存储器: 主存和内存 辅助存储器: 辅存和外存 2.分类 1.按层次结构划分 如上面所示 2.按存储介质 半导体存储器磁表面存储器光存储器 3.按信息可更改性 r/w存储器ROM(只读存储器) 4…...
力扣刷题 day54:10-24
1.十进制整数的反码 每个非负整数 N 都有其二进制表示。例如, 5 可以被表示为二进制 "101",11 可以用二进制 "1011" 表示,依此类推。注意,除 N 0 外,任何二进制表示中都不含前导零。 二进制的反…...
Java基础篇 | Java8流式编程
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏…...
SolidworksSimulation完成对压力容器的强度分析
如何通过使用SolidworksSimulation完成对压力容器的分析并查看实 体的膜片应力强度以及弯曲应力强度,操作简单易学,让我们进入到操作界面。 我们以罐体底部实体模型为例,这里已经提前设置好了材料。 点击新算例,选择静应力分析 由…...
【C++】继承 ⑨ ( 继承中成员变量同名的处理方案 )
文章目录 一、继承中成员变量同名的处理方案1、继承中成员变量同名的场景说明2、使用域作用符区分同名成员变量 二、代码示例 - 继承中成员变量同名的处理方案 一、继承中成员变量同名的处理方案 1、继承中成员变量同名的场景说明 子类 继承 父类 的 成员 , 如果 子类 中定义了…...
Python报错:‘EagerTensor‘ object has no attribute ‘reshape‘
在使用RPython时,发现python代码部分报错:‘EagerTensor‘ object has no attribute ‘reshape‘ 如何解决? 使用np.array 转换为array,再进行reshape 参考: ‘EagerTensor‘ object has no attribute ‘reshape‘处…...
docker-compose手册
大家好,我叫徐锦桐,个人博客地址为www.xujintong.com。平时记录一下学习计算机过程中获取的知识,还有日常折腾的经验,欢迎大家访问。 前言 一些自己经常用到的docker-compose知识。 一、运行和启动项目 1.1、docker-compose运行…...
【珠峰 WEB 前端架构师课程】学习笔记 100 篇(完结)
该课程是珠峰姜文老师讲的,个人觉得讲的很不错,一路在 b 站学习下来做了 100 篇的学习笔记,收获颇丰。 该课程主要讲了高阶函数、函数柯里化、发布订阅模式、观察者模式、从 0 到 1 实现一个 promise,co 库的实现、eventloop 执行…...
Java线程中sleep()、wait()、yield()、join()方法的使用
1.sleep() sleep(): sleep 方法属于 Thread 类,该行为中线程不会释放锁,只阻塞线程,让出cpu给其他线程,当达到指定的时间后会自动恢复运行状态继续运行。 2.wait() wait(): 该方法属于 Object 类,在这个过程里线程会…...
【机器学习】数据均衡学习笔记
文章目录 序言1. 样本不均衡2. 样本不均衡的影响以及样本均衡的意义3. 什么时候需要进行样本均衡/数据均衡4. 数据不均衡的解决办法 序言 数据集制作过程中需要关注样本均衡问题,学习笔记,简单记录 1. 样本不均衡 分类任务中不同类别样本数差别很大的…...
【软件教程】如何用C++交叉编译出能在Android运行的ELF程序或so动态库
一、配置NDK交叉编译平台 1. 打开Android的官方ndk下载链接https://developer.android.com/ndk/downloads?hlzh-cn,下载windows 64位ndk环境包。 2. 解压后将具有以下文件的路径加入到系统环境变量。 3. 配置好环境变量,如下图所示,Path中存…...
进阶JAVA篇- Map 系列集合的遍历方法与常用API
目录 1.0 Map 集合的说明 1.1 Map 集合的常用方法 1.2 Map 系列集合的特点 2.0 Map 系列集合的遍历方法(三种方法) 2.1 使用 keySet() 方法遍历 2.2 使用 entrySet() 方法遍历 2.3 使用 forEach() 方法遍历(Java 8) 1.0 Map 集合的…...
Auth.js:多合一身份验证解决方案 | 开源日报 No.60
nodejs/node Stars: 96.2k License: NOASSERTION Node.js 是一个开源的、跨平台的 JavaScript 运行时环境。它具有以下关键特性和核心优势: 强大:Node.js 提供了强大且高效的服务器端运行能力,可以处理并发请求,并支持异步编程…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
