【数据结构】——排序篇(下)
前言:前面我们的排序已经详细的讲解了一系列的方法,那么我们现在久之后一个归并排序了,所以我们现在就来讲解一下归并排序。

归并排序:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and
Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有
序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// [begin, mid][mid+1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;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++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
 
a是我们待排序的数组,里面存放了要排序的数据,tmp是我们额外开辟的数组用来存放我们排好序的数据,而我们排好序的数据则是像链表一样尾插入数组的。我们先找出中间值,给这个区间分成两个小区间,两个小区间各自在分成小区间。从左到右逐一比较两个小区间中的元素,把较小的元素优先放入额外开辟的数组tmp,如果一个小区间的全部尾插到tmp中就结束了循环,而另外一个数组则按顺序的尾插到tmp中。最后我们的tmp中的数据拷贝到数组a中就完成了。
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
 
这里就是用来开辟额外数组tmp的,我们传参到函数_MergeSort,在_MergeSort中递归完成排序之后就返回,再将开辟的空间销毁。
如果最大家有所帮助的话就支持一下吧!感谢大家!
相关文章:
【数据结构】——排序篇(下)
前言:前面我们的排序已经详细的讲解了一系列的方法,那么我们现在久之后一个归并排序了,所以我们现在就来讲解一下归并排序。 归并排序: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法…...
C++ 模拟实现vector
目录 一、定义 二、模拟实现 1、无参初始化 2、size&capacity 3、reserve 4、push_back 5、迭代器 6、empty 7、pop_back 8、operator[ ] 9、resize 10、insert 迭代器失效问题 11、erase 12、带参初始化 13、迭代器初始化 14、析构函数 完整版代码 一、…...
基于hadoop下的spark安装
目录 简介 安装准备 spark安装 配置文件配置 简介 Spark主要⽤于⼤数据的并⾏计算,⽽Hadoop在企业主要⽤于⼤数据的存储(⽐如HDFS、Hive和HBase 等),以及资源调度(Yarn)。但是也有很多公司也在使⽤MR2进…...
面试经典150题(10-13)
leetcode 150道题 计划花两个月时候刷完,今天(第四天)完成了4道(10-13)150: 10. (45. 跳跃游戏 II)题目描述: 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[…...
Sql server数据库数据查询
请查询学生信息表的所有记录。 答:查询所需的代码如下: USE 学生管理数据库 GO SELECT * FROM 学生信息表 执行结果如下: 查询学生的学号、姓名和性别。 答:查询所需的代码如下: USE 学生管理数据库 GO SELE…...
前端开发tips
前端开发tips 关于package.json里面,尖角号(^)和波浪线(~)的区别 在package.json里面,我们可以使用尖角号(^)和波浪线(~)来表示不同的包版本。这些符号通常被…...
实现跨VLAN通信、以及RIP路由协议的配置
一、如下图片: 1. 按照拓扑图所示,将8台计算机分别配置到相应的VLAN中。(20分) 2. 配置实现同一VLAN中的计算机可以通信。(22分) 3. 配置实现PC1,PC2,PC3,PC4可以互相通信,PC5,PC6,PC7,PC8可以互…...
使用python绘制现有彩票记录走势图
在数据分析和可视化的领域中,彩票走势图是一个经典的例子,它可以展示彩票数字随时间的出现频率和趋势。这里使用英国使用EuroMillions彩票的历史数据作为示例,使用Python和Matplotlib库来创建一个简单的走势图。可以在以下网站搜索.csv文件。…...
Kubernetes实战(十)-升级k8s集群
1 Kubernetes(k8s) 集群升级过程 Kubernetes 使用 kubeadm 工具来管理集群组件的升级。在集群节点层面,升级 Kubernetes(k8s)集群的过程可以分为以下几个步骤: 1)检查当前环境和配置是否满足升级要求。 2)升级master主节点&…...
点击el-tree小三角后去除点击后的高亮背景样式,el-tree样式修改
<div class"videoTree" v-loading"loadingTree" element-loading-text"加载中..." element-loading-spinner"el-icon-loading" element-loading-background"rgba(0, 0, 0, 0.8)" > <el-tree :default-expand-all&q…...
【电子取证篇】汽车取证数据提取与汽车取证实例浅析(附标准下载)
【电子取证篇】汽车取证数据提取与汽车取证实例浅析(附标准下载) 关键词:汽车取证,车速鉴定、声像资料鉴定、汽车EDR提取分析 汽车EDR一般记录车辆碰撞前后的数秒(5s左右)相关数据,包括车辆速…...
系列学习前端之第 3 章:一文精通 css
全套学习 HTMLCSSJavaScript 代码和笔记请下载网盘的资料: 链接: 百度网盘 请输入提取码 提取码: 6666 一、CSS基础 1. CSS简介 CSS 的全称为:层叠样式表 ( Cascading Style Sheets ) 。 CSS 也是一种标记语言,用于给 HTML 结构设…...
基于JavaWeb+SSM+Vue马拉松报名系统微信小程序的设计和实现
基于JavaWebSSMVue马拉松报名系统微信小程序的设计和实现 源码获取入口Lun文目录前言主要技术系统设计功能截图订阅经典源码专栏Java项目精品实战案例《500套》 源码获取 源码获取入口 Lun文目录 1系统概述 1 1.1 研究背景 1 1.2研究目的 1 1.3系统设计思想 1 2相关技术 2 2.…...
leetcode 255.用队列实现栈
255.用队列实现栈 不出意外大概率这几天都会更新 leetcode,如果没有做新的题,大概就会把 leetcode 之前写过的题整理(单链表的题目居多一点)出来写成博客 今天讲的题蛮容易出错的(注意传参啊,最好把队列的…...
排序算法---选择排序
1.实现流程: 1. 把第一个没有排序过的元素设置为最小值; 2. 遍历每个没有排序过的元素; 3. 如果元素 < 现在的最小值; 4. 将此元素设置成为新的最小值; 5. 将最小值和第一个没有排序过的位置交换 选择排序执行流程…...
物联网IC
物联网IC 电子元器件百科 文章目录 物联网IC前言一、物联网IC是什么二、物联网IC的类别三、物联网IC的应用实例四、物联网IC的作用原理总结前言 物联网IC的功能和特性可以根据不同的物联网应用需求来选择和配置,以满足物联网设备在连接、通信、感知和控制方面的需求。 一、物…...
2022年第十一届数学建模国际赛小美赛A题翼龙如何飞行解题全过程文档及程序
2022年第十一届数学建模国际赛小美赛 A题 翼龙如何飞行 原题再现: 翼龙是翼龙目中一个已灭绝的飞行爬行动物分支。它们存在于中生代的大部分时期:从三叠纪晚期到白垩纪末期。翼龙是已知最早进化出动力飞行的脊椎动物。它们的翅膀是由皮肤、肌肉和其他组…...
Blender学习--制作带骨骼动画的机器人
1. 首先创建一个机器人模型 时间关系,这部分步骤有时间补充 2. 然后为机器人创建一副骨架 时间关系,这部分步骤有时间补充 3.骨骼绑定 切换到物体模式,选中机器人头部,Shift选中骨骼,切换到姿态模式,&am…...
单片机学习13——串口通信
单片机的通信功能: 实现单片机和单片机的信息交换,实现单片机和计算机的信息交换。 计算机通信是指计算机与外部设备或计算机与计算机之间的信息交换。 通信有并行通信和串行通信两种方式。 在多微机系统以及现在测控系统中信息的交换多采用串行通信方…...
Unity 实现单例模式
目录 基本概念 饿汉模式(推荐) 懒汉模式: 基本概念 单例模式:类只有一个实例,一般使用static来实现单例模式; 比如:有一个Test类,实现了单例,假设这个唯一的实例名为SingTonle,实例在类内被实现并被stat…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
【Linux】使用1Panel 面板让服务器定时自动执行任务
服务器就是一台24小时开机的主机,相比自己家中不定时开关机的主机更适合完成定时任务,例如下载资源、备份上传,或者登录某个网站执行一些操作,只需要编写 脚本,然后让服务器定时来执行这个脚本就可以。 有很多方法实现…...

