归并排序详解(非递归)

 

感谢各位大佬的光临,希望和大家一起进步,望得到你的三连,互三支持,一起进步

个人主页:LaNzikinh-CSDN博客

收入专栏:http://t.csdnimg.cn/LJ2J2

文章目录

  • 前言
  • 一.归并排序
  • 二.代码实现归并排序(递归)
  • 三.代码实现归并排序(非递归)
  • 总结

前言

我们之前讲了希尔排序直接插入排序堆排序,我们今天来讲一讲归并排序,讲之前我们先要知道归并排序的思想和什么是归并排序


一.归并排序

什么是归并排序

归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

归并排序的思想

规定排序的主要思想就是先分解再合并,先分解到只有一个的时候再两两合并,那他是怎么个排序法呢?两两归并,两组的头一个进行比较小的放在前面,然后往后加加,继续比较小的放前面按顺序排好。

二.代码实现归并排序(递归)

我需要在外面提前开辟一个空间,我为什么不在函数内部开辟,是因为函数递归需要反复调用函数,这样子会多次开辟空间,所以我在外面提前开辟了,再去释放

void MergrSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergrSort(a, 0, n - 1,tmp);
	free(tmp);
}

2.2利用分治思路,将归并展开

我们将这个归并排序的一行数字的下标,分成两个区间,两个区间又继续分,有点像我们二叉树那里的左子树右子树的分治思路,我们可以根据之前那幅图分析我们最开始就是要先分开,然后在后面再进行归并

void _MergrSort(int* a, int left, int right,int*tmp)
{
	if (left >= right)
		return;
	int mid = (left + right)/2;
	//用递归将[left,mid][mid+1,right]有序
	_MergrSort(a, left, mid,tmp);
	_MergrSort(a, mid+1, right, tmp);
	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;

2.3归并

根据上面的地规可以看出第一个循环就是第一组数已经分到最当头了,判定条件也很简单,只要左边不会超越右边就可以两边之中,只要有一边达到的话就要结束这个循环,后面的循环就是说,当一个区间结束时,把另一个区间拷回去

	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 (begin1 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	//最后把排好的数据拷入开辟的数组中去
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}	
}

2.4总代码

它其实整体的思路并不是像图中层序一样的往下走的,他其实是先把左边的排好了之后再一步一步往右边走的

void _MergrSort(int* a, int left, int right,int*tmp)
{
	if (left >= right)
		return;
	int mid = (left + right)/2;
	//用递归将[left,mid][mid+1,right]有序
	_MergrSort(a, left, mid,tmp);
	_MergrSort(a, mid+1, right, tmp);
	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	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 (begin1 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	//最后把排好的数据拷入开辟的数组中去
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}	
}
void MergrSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergrSort(a, 0, n - 1,tmp);
	free(tmp);
}

三.代码实现归并排序(非递归)

递归他就是把这一串数字先从左开始变得有序,再不断地向右延伸变得有序,最后再让整体变得有序,非递归就是不用递归的方式去想办法,那我们该怎么做呢?

思路就在这个图中

我们可以把这个数组进行分组,再把每一组进行归并,先从gap=1开始归并完之后,从gap=2开始一直往下,直到gap的值大于总长度就可以停止了

i += 2 * gap是控制gap为几的分组进行总体归并,就是i += 2 * gap了之后,可以要这组全部归并下去

[i,i+gap-1][i+gap,i+2*gap-1]是怎么看出来的,注意一点,这个是数组,[]内的都是下标,我是不是每次归并都需要找两个组去归,所以说我这个代码就是要找两个组的,而是初始位置i加上gap就是表示第一组的末尾,因为是下标,所以要减1,所以第2组的尾就是i+2*gap-1,然后这两组比完后面还会有,所以i += 2 * gap就可以比到后面的组了

void MergeSortNonR(int* a, int n)
{
	//开辟空间
	int* tmp = (int*)malloc(sizeof(int) * n);
	//gap从1开始,gap代表每组的数据个数
	int gap = 1;
	//gap大于总长度就停下来
	while (gap < n)
	{
		//i += 2 * gap控制gap为几的分组进行总体归并
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i,i+gap-1][i+gap,i+2*gap-1]
			int begin1 = i, end1 = i+gap-1;
			int begin2 = i + gap, end2 = i+ 2 * gap-1;
			int index = i;
			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 (begin1 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			for (int j = 1; j <= n; j++)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);
}

但是这个代码存在问题!!!

如果是这样就存在越界现象

改:

//归并过程中右半区间可能不存在
if (begin2 >= n)
	break;
//归并过程中右半区间算多了,需要修正
if (end2 >= n)
{
	end2 = n - 1;
}


//循环这里也要改
for (int j = 1; j <= end2; j++)
{
	a[j] = tmp[j];
}

总代码

void MergeSortNonR(int* a, int n)
{
	//开辟空间
	int* tmp = (int*)malloc(sizeof(int) * n);
	//gap从1开始,gap代表每组的数据个数
	int gap = 1;
	//gap大于总长度就停下来
	while (gap < n)
	{
		//i += 2 * gap控制gap为几的分组进行总体归并
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i,i+gap-1][i+gap,i+2*gap-1]
			int begin1 = i, end1 = i+gap-1;
			int begin2 = i + gap, end2 = i+ 2 * gap-1;
			//归并过程中右半区间可能不存在
			if (begin2 >= n)
				break;
			//归并过程中右半区间算多了,需要修正
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			int index = i;
			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 (begin1 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			for (int j = 1; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);
}

总结

归并排序是算法中非常重要的一个方法,无论是递归还是非递归,我们都应该要搞清楚

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

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

相关文章

【6】单向循环链表

【6】单向循环链表 1、单向循环链表2、add(int index, E element)3、删除 1、单向循环链表 &#x1f58a; 在单向链表的基础上&#xff0c;尾节点的 next 指向头节点 2、add(int index, E element) &#x1f58a; 往尾部添加的代码不用修改&#xff08;和单向链表一样的&am…

华为ensp中基本acl 原理及配置命令(详解)

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月5日10点45分 基本ACL的简介 华为ensp中的基本acl是指华为设备中用于控制网络访问的访问控制列表的其中一种类型。基本acl可以根据数据包的源IP地址进行过滤&#…

备战蓝桥杯---多路归并与归并排序刷题

话不多说&#xff0c;直接看题 1. 我们考虑一行一行合并&#xff0c;一共m次&#xff0c;我们合并两个并取前n小&#xff0c;那么我们怎么取&#xff1f; 我们采用分组的思想&#xff1a; 我们选第一列的min,然后把后面那个再纳入考虑&#xff0c;用优先队列实现即可。 下面…

今年考研是太卷了还是太水了,为什么分数线都高的离谱?

25考研的备考形势&#xff0c;势必跟以前不一样了&#xff01; 有些人问&#xff0c;分数线那么高&#xff0c;是不是题目太水了&#xff1f; 问的人肯定不是24考生。 24的题&#xff0c;也就政治正常一点。 其它的&#xff0c;英语难上热搜&#xff0c;数学难度空前&#x…

04---webpack编写可维护的构建配置

01 构建配置抽离成npm包&#xff1b; 意义&#xff1a;通用性&#xff1a; 业务开发者无需关注构建配置 统一团队构建脚本可维护性&#xff1a;构建配置合理的拆分 质量&#xff1a;冒烟测试 单元测试 持续集成构建配置管理的可选方案&#xff1a;1 通过多个配置文件管理不同…

一、OpenCV(C#版本)环境搭建

一、Visual Studio 创建新项目 二、选择Windows窗体应用&#xff08;.NET Framework&#xff09; 直接搜索模板&#xff1a;Windows窗体应用(.NET Framework) 记得是C#哈&#xff0c;别整成VB(Visual Basic)了 PS&#xff1a;若搜索搜不到&#xff0c;直接点击安装多个工具和…

【OJ】动规练习七之【模板】01背包

个人主页 &#xff1a; zxctscl 如有转载请先通知 DP41 【模板】01背包 1. DP41 【模板】01背包2. 分析3. 代码4. 优化5. 优化后代码 1. DP41 【模板】01背包 2. 分析 一、题目解析&#xff1a; 来看一下例1&#xff0c;3代表有三个物品&#xff0c;5代表能够容纳的体积。第一…

VGA 多分辨率

REVIEW VGA 时序与实现-CSDN博客 对于不同分辨率&#xff0c;每次使用都去查表比较麻烦&#xff1b; 学习条件编译的使用&#xff0c;减轻后续调用的麻烦。 1. 条件编译格式 条件编译是当设计中满足某个条件时&#xff0c;将该条件下的一段代码编译进设计中。 因此&#xff0…

C++ 类和对象(初篇)

类的引入 C语言中&#xff0c;结构体中只能定义变量&#xff0c;在C中&#xff0c;结构体内不仅可以定义变量&#xff0c;也可以定义函数。 而为了区分C和C我们将结构体重新命名成class去定义 类的定义 标准格式&#xff1a; class className {// 类体&#xff1a;由成员函…

AI绘图:Stable Diffusion ComfyUI局部重绘与智能扩图全面教程

前言 在数字艺术创作中&#xff0c;局部重绘和智能扩图是两个非常重要的功能。局部重绘允许我们在保留原有图像的基础上&#xff0c;对特定区域进行修改或创新。而智能扩图则能够帮助我们在图像的边缘添加新的元素&#xff0c;从而扩展图像的内容。本文将详细介绍如何在Stable…

深度学习pytorch好用网站分享

深度学习在线实验室Featurizehttps://featurize.cn/而且这个网站里面还有一些学习教程 免费好用 如何使用 PyTorch 进行图像分类https://featurize.cn/notebooks/5a36fa40-490e-4664-bf98-aa5ad7b2fc2f

jforgame-doctor快速入门

背景 游戏热更新,是指在不重启服务器/客户端app的情况下,对游戏内容进行修改或者对代码bug进行修复。 对于一个上线产品项目来说,热更新为维持项目的稳定健康提供了坚强的保障。小到策划数据的修改,代码bug的修改,大到动态扩展游戏业务功能。试想一下,没有热更新机制,…

基于SSM的邮票鉴赏系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的邮票鉴赏系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring Spri…

电脑硬盘分区表的两种格式:MBR 和 GPT

电脑硬盘分区表的两种格式&#xff1a;MBR 和 GPT 段子手168 2024-4-5 电脑硬盘分区表有两种格式&#xff1a;MBR 和 GPT&#xff1a; 一、MBR 分区表 1.MBR 是主引导记录 (Master Boot Record) 的英文缩写 在传统&#xff08;Legacy&#xff09;硬盘分区模式中&#xff0c…

1970-2021年全国区县级碳排放数据8

1970-2021年全国区县级碳排放数据 1、时间&#xff1a;1970-2021年 2、指标&#xff1a;2877个区县 3、来源&#xff1a;EDGAR 4、指标&#xff1a;二氧化碳排放量 5、样本量&#xff1a;14W 6、指标解释&#xff1a; 二氧化碳排放是一个生态环境专业术语&#xff0c;主…

项目经理必须知道的三大财务报表相关知识

清晖有个不错的讲项目经理应该知道的三大财务报表相关知识&#xff0c;地址&#xff1a;项目经理必备的财务知识_哔哩哔哩_bilibili

深度学习的数学基础--Homework2

学习资料&#xff1a;https://www.bilibili.com/video/BV1mg4y187qv/?spm_id_from333.788.recommend_more_video.1&vd_sourced6b1de7f052664abab680fc242ef9bc1 神经网络的特点&#xff1a;它不是一个解析模型&#xff0c;它的储存在一堆参数里面&#xff08;确定一个超平…

File(一),IO流,递归详解

File类 介绍 java.io.File类是Java语言提供了用来描述文件和目录(文件夹)的 构造 方法 注意&#xff1a; 构造方法中通常用的是第一个方法文件和目录可以通过File封装成对象File封装的对象仅仅是一个路径名&#xff0c;它是可以存在的&#xff0c;也可以不存在 绝对路径…

详解protected访问限定符

1.同一个包中的同一类 package demo1;public class Test1 {protected int a 10;protected void b() {System.out.println("这是protected修饰的成员方法");}public static void main(String[] args) {Test1 test new Test1();System.out.println(test.a);test.b()…

Vue学习笔记-S1

1 什么是Vue Vue是一款用于构建用户界面的渐进式JavaScripte框架&#xff0c;可基于数据渲染用户页面. 1.1 Vue的知识架构 Vue核心包&#xff1a;声明式渲染、组件系统Vue构建&#xff1a;客户端路由、状态管理、构建工具局部使用Vue&#xff1a;快速入门、常用指令、生命周…