归并排序详解(递归与非递归)
归并排序是建立在归并操作上的一种有效算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列间断有序。若将两个有序表合并成一个有序表,成为二路归并。
一、递归实现归并排序
1.算法描述
● 把长度为n的输入序列分成两个长度近似为n/2([begin,mid] [mid + 1,end] )的子序列
● 对这两个子序列再分别进行归并排序,将区间分解到不可在分为止
● 依次将两个排序好的子序列合并成一个最终的排序序列
方法: 开辟新数组,用双指针选出两个子序列中的较小元素尾插在新数组中
2.动图演示

3.核心步骤
(1)图示

(2)思考
为什么要将区间拆分成[begin,mid] [mid + 1,end] ?
上面介绍过我们的算法步骤是把长度为 n 的输入序列分成两个长度近似为 n/2 的子序列,在此前提下,除了分成[begin,mid] [mid + 1,end]外,还有一种分法:[begin,mid-1] [mid,end],为什么不用这种分法?
mid = (begin + end)/2,所以mid是偶数
示例:用两种不同的分法分解区间[0,9]
当所要分解的区间是 [偶数,偶数],上述的两种分法都行得通,但是当区间是[偶数,偶数+1]的情况,[begin,mid-1] [mid,end]这种分法就行不通。
5.参考代码
void _MergeSort(int* arr, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;//偶数//[begin,mid] [mid+1,end] ——>[偶数,偶数] [偶数+1,偶数+1]_MergeSort(arr,tmp, begin, mid);_MergeSort(arr, tmp, mid + 1, end);//左右区间有序就可以归并了//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}//剩下的尾插在tmp数组while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}//将一定长度的tmp复制到arr中memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}_MergeSort(arr,tmp, 0, n - 1);free(tmp);tmp = NULL;
}
不同排序对一百万个随机数进行排序的效率: (毫秒)

二、非递归实现归并排序
1.算法描述
● gap表示每组归并的数据个数
● i 表示每组归并的起始位置
● 两层循环,一层循环用来归并数组中的数据,另一层扩大归并的数据个数
2.核心步骤
(1)图示


(2)思考
为什么要归并一次拷贝一次?
● 如果整体拷贝,在上述的“第二组的都越界不存在”的情况下,虽然跳出循环,但在整体拷贝的时候还会把越界的部分拷贝回去
● 但如果归并一次拷贝一次,在“第二组的都越界不存在”的情况下,直接跳出循环,不会将越界的部分拷贝到数组中
3.参考代码
//归并(非递归)
void MergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}//gap表示每组要归并数据的个数int gap = 1;while (gap < n){ //i表示每组归并的起始位置for (int i = 0; i < n; i += 2 * gap)//个数于区间的转化关系{//[bagin1,end1] [bagin2,end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二组的都越界不存在,那么第二组不用归并了,跳出循环if (begin2 > n)break;//第二组的begin2没越界,end2越界了,需要修正区间,再归并if (end2 > n)end2 = n - 1;//归并int j = i;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[j++] = arr[begin1++];}else{tmp[j++] = arr[begin2++];}}//剩下的尾插在tmp数组while (begin1 <= end1){tmp[j++] = arr[begin1++];}while (begin2 <= end2){tmp[j++] = arr[begin2++];}//将一定长度的tmp复制到arr中//归并一次拷贝一次memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);tmp = NULL;
}
三、算法分析
归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是,代价是需要额外的内存空间。
特性总结:
(1) 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在此版中的外排序问题
(2) 时间复杂度:O(N*logN) 相当于一个满二叉树
(3) 空间复杂度:O(N) 开辟了一个额外的数组
(4) 稳定性:稳定
相关文章:
归并排序详解(递归与非递归)
归并排序是建立在归并操作上的一种有效算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列间断有序。若将两个有序表合并成一个有序表,成为二路归并。 一…...
计算机系统基础(二)
1.数值数据的表示 为什么采用二进制? 二进制只有两种基本状态,两个物理器件就可以表示0和1二进制的编码、技术、运算规则都很简单0和1与逻辑命题的真假对应,方便通过逻辑门电路实现算术运算 数值数据表示的三要素 进位记数制(十…...
vue根据文字长短展示跑马灯效果
介绍 为大家介绍一个我编写的vue组件 auto-marquee ,他可以根据要展示文本是否超出展示区域,来判断是否使用跑马灯效果,效果图如下所示 假设要展示区域的宽度为500px,当要展示文本的长度小于500px时,只会展示文本&…...
leetcode-21-回溯-全排列及其去重
一、[46]全排列 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 其中,不需要使用startIndex used数组,其实就是记录此时path里都有哪些元素…...
如何根据两个关键字查询报错日志的位置
1、查找两个关键字(无顺序要求) 如果你不关心这两个关键字出现的顺序,你可以使用egrep(等同于grep -E)或grep的-E选项来启用扩展正则表达式,并使用管道(|)来组合两个搜索模式。 gr…...
短视频预算表:成都柏煜文化传媒有限公司
短视频预算表:精打细算,打造高质量视觉盛宴 在数字时代,短视频以其独特的魅力迅速占领了互联网内容的半壁江山,成为品牌宣传、文化传播乃至个人表达的重要载体。然而,每一个成功的短视频背后,都离不开一份…...
【Llama 2的使用方法】
Llama 2是Meta AI(Facebook的母公司Meta的AI部门)开发并开源的大型语言模型系列之一。Llama 2是在其前身Llama模型的基础上进行改进和扩展的,旨在提供更强大的自然语言处理能力和更广泛的应用场景。 以下是Llama 2的一些关键特性和更新点&am…...
mysql-sql-第十三周
学习目标: sql 学习内容: 37.查询各科成绩最高分、最低分和平均分: 以如下形式显示:课程 ID,课程 name,最高分,最低分,平均分,及格率,中等率,优良率,优秀率 及格为>60,中等为:70-80,优良为:80-90,优秀…...
【Android】ViewPage2嵌套Fragment+SeekBar横向滑动冲突
问题描述 ViewPage2嵌套FragmentSeekBar,拖动SeekBar的进度条时,触发ViewPage2的滑动。 解决方案: 方案一:通过事件总线ViewPage2的isUserInputEnabled属性 子Fragment: class SeekBarFragment : Fragment() {priv…...
【408考点之数据结构】图的遍历
图的遍历 图的遍历是指从图中的某个顶点出发,按照一定的规则访问图中所有顶点,并使每个顶点仅被访问一次。图的遍历包括两种主要方法:深度优先搜索(DFS)和广度优先搜索(BFS)。这两种遍历方法在…...
自动驾驶---Motion Planning之多段五次多项式
1 前言 在之前的博客系列文章中和读者朋友们聊过Apollo的 Motion Planning方案: 《自动驾驶---Motion Planning之LaneChange》 《自动驾驶---Motion Planning之Path Boundary》 《自动驾驶---Motion Planning之Speed Boundary》 《自动驾驶---Motion Planning之轨迹Path优化》…...
Linux基础IO操作详解
C文件IO相关接口 fopen函数 pathname: 要打开的文件名字符串mode: 访问文件的模式 模式描述含义“r”读文件不存在失败返回null“r”读写文件不存在打开失败返回null,文件存在则从头开始覆盖现有的数据(不会清空数据)“w”写文件不存在创建…...
轻松掌握:Hubstudio指纹浏览器如何接入IPXProxy代理IP
代理IP对于保护个人和企业网络安全起到了至关重要的作用,然而在需要多个工作的时候,就需要搭配指纹浏览器来使用。其中Hubstudio指纹浏览器就可以模拟多个浏览器环境,然而有些用户不知道如何将Hubstudio和代理IP一起使用,下面以…...
React小记(五)_Hooks入门到进阶
React 16.8 版本 类组件 和 函数组件 两种组件共存,到目前 React 18 版本,官方已经不在推荐使用类组件,在函数组件中 hooks 是必不可少的,它允许我们函数组件像类组件一样可以使用组件的状态,并模拟组件的生命周期等一…...
使用工业自动化的功能块实现大语言模型应用
大语言模型无所不能? 以chatGPT为代表的大语言模型横空出世,在世界范围内掀起了一场AI革命。给人的感觉似乎大模型语言无所不能。它不仅能够生成文章,图片和视频,能够翻译文章,分析科学和医疗数据,甚至可以…...
PPT文件中,母版视图与修改权限的区别
在PPT(PowerPoint)制作过程中,母版视图和修改权限是两个重要的概念,它们各自在演示文稿的编辑、管理和分发中扮演着不同的角色。本文将从定义、功能、使用场景及区别等方面详细探讨PPT母版视图与修改权限的异同。 PPT母版视图 定…...
php简单的单例模式
本文由 ChatMoney团队出品 单例模式是一种常用的设计模式,它的核心思想是确保一个类只有一个实例,并提供一个全局访问点来获取这个实例。在 PHP 中实现单例模式通常有三种形式:饿汉式(Eager)、懒汉式(Lazy&…...
【面试题】IPS(入侵防御系统)和IDS(入侵检测系统)的区别
IPS(入侵防御系统)和IDS(入侵检测系统)在网络安全领域扮演着不同的角色,它们之间的主要区别可以归纳如下: 功能差异: IPS:这是一种主动防护设备,不仅具备检测攻击的能力&…...
宠物博主亲测养宠好物安利,口碑好的狗毛空气净化器推荐
作为一名6年资深铲屎官,一到春季换季就开始各种疯狂打喷嚏、全身过敏红肿,这是因为宠物在换季的时候就疯狂掉毛,家里就想下雪一样,空气中都是宠物浮毛。而宠物毛上附带的细菌会跟随浮毛被人吸入人体,从而产生打喷嚏、过…...
常用工具类
计算当天开始时间和结束时间 DateTime date DateUtil.date(); String startDateStr DateUtil.formatDateTime(DateUtil.beginOfDay(date)); String endDateStr DateUtil.formatDateTime(DateUtil.beginOfDay(DateUtil.offsetDay(date,1))); params.put("startDate&quo…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...


