数据结构——lesson12排序之归并排序

这篇具有很好参考价值的文章主要介绍了数据结构——lesson12排序之归并排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

💞💞 前言

hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记 、排序算法合集
💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

前面我们学习过六种排序——直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序和快速排序,今天我们就来学习归并排序🥳🎉🎉🎉

1.归并排序

基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序核心步骤:
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言
归并排序的步骤类似于二叉树的后序遍历,先一直分解到不能再分,然后对两个子序列合并排序,最终得到全部排序好的序列;数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言

1.1归并排序(递归版)

在上图中我们看到它把序列拿下来排好后再放回原序列,归并排序需要在内存中重新开辟一个数组来存放排好的子序列,然后再拷贝回原数组,这样可以防止在原数组中操作困难以及很多错误的发生;
步骤:
①使用malloc函数开辟一个大小为原数组的空间存放在tmp中;
②重新构造递归函数(因为如果在原来的函数中递归,那么每次都会malloc开辟一个数组,不合适)_mergesort();
③分解数列,进行递归,创建mid遍量,从中间开始分割;
④当只有一个数时就不再分割(也就是begin>=end时);
⑤对子序列进行归并排序;

void _mergesort(int* a,int begin,int end, int* tmp)
{
	//递归结束条件
	if (begin >= end)
		return;
	//分左右区间
	
	int mid = (begin + end) / 2;
	_mergesort(a, begin, mid,tmp);
	_mergesort(a, mid+1, end,tmp);
	//归并排序
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1];
			begin1++;
		}
		else
		{
			tmp[i++] = a[begin2];
			begin2++;
		}
	}
	//如果最后begin1的序列有剩余
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	//如果最后begin2的序列有剩余
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//最后再拷贝回原数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

}

// 归并排序递归实现
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	
	_mergesort(a,0,n-1,tmp);
	free(tmp);//释放内存空间
}

结果如下:
上面一排是排序前,下面一排是用归并排序排完序后
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言

1.2归并排序(非递归版)

归并排序非递归版主要是通过循环来实现两两归并;
步骤如下:
①使用malloc开辟tmp数组来存放归并好的数;
②创建gap来设定每次归并的序列的范围
③利用while循环来实现整个序列的多次归并;
while循环内部与递归的归并对子序列排序类似,不同的是需要嵌套for循环来实现多个gap范围的序列归并(因为此时已经将整个序列分成每gap个为一组,所以需要for循环来控制,使得这些序列全部都两两归并);
⑤归并完了后要使用memcpy函数将数据拷贝回原数组;

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//开辟数组来归并
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;//定义每次归并范围
	
	while (gap < n)//gap不能==n,因为此时?
	{
		int j = 0;//记录tmp数组下标
		//每次距离为gap的两组归并
		for (int i = 0; i < n; i+=2*gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (end1 >= n || begin2 >= n)
			{
				end1 = n - 1;
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1];
					begin1++;
				}
				else
				{
					tmp[j++] = a[begin2];
					begin2++;
				}
			}
			//如果最后begin1的序列有剩余
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			//如果最后begin2的序列有剩余
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

结果如下:
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言

✨✨这里要注意两点:
🥳🥳(1)将数组每gap为一组分完后进行两两归并时,可能出现三种情况:
💥 ①到最后可能第一个序列存在,下一个序列不存在也就是begin2>=n的情况;
💥②还可能出现第一个序列只有一部分也就是end1>=n的情况;
💥 ③第二个序列只有一部分存在也就是end2>=n的情况;
出现①②两种情况说明最后一组只有一组或半组,这时不需要再归并,将end2 = n -1,并break跳出循环即可;
情况③有两组可以归并,但是第二组不完整,所以此时需要将end2 = n-1,不跳出循环继续归并即可;
🥳🥳(2)memcpy将tmp中归并的数拷贝回原数组时;
💥①可以考虑在for循环内部每次归并完两个序列后拷贝回去(上述代码就是使用这种)此时:
memcpy(a + i, tmp + i, sizeof(int)*(end2 - begin1 + 1))
要注意拷贝的位置要+i,并且拷贝的个数也应该是归并的两个序列的长度,(但是不能使用2*gap因为会出现上面的(1)问题,有可能序列不存在或部分存在)所以序列长度应该是end2 - i;
💥②可以在每次完整归并完距离为gap的序列后再进行拷贝,此时:
memcpy(a, tmp, sizeof(int) * n);
如下图所示:
此时不需要考虑拷贝的位置,直接全部拷贝即可;
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言
??真的以为这么简单吗???不可能,绝对不可能😭😭
刚刚将十个数据0,1,2,3,4,5,6,7,8,9改成九个数据1,2,3,4,5,6,7,8,9结果如下:
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言
可恶又错了,得重新捋一遍:
现在我们是要等for循环一遍将间距为gap的组两两归并,直到全部归并完再进行拷贝,之前是for循环内部每两组归并完就拷贝,那为什么全部归并完再拷贝会出错呢???
捋一遍发现:
if (end1 >= n || begin2 >= n) { end1 = n - 1; break; }
这里有问题,在只有一个序列或半个序列时,我们直接跳出了循环,也就是此时原数组后面的数根本没有输入到tmp数组里面,此时tmp后面的数是不知道是什么的,然后你再全部一拷贝回原数组,这样不仅不能排序,还会将原数组的数给覆盖掉,所以如果要使用: memcpy(a, tmp, sizeof(int) * n);
我们不能再次使用上面的if语句,需要改一改:

if (end1 >= n || begin2 >= n)
{
	end1 = n - 1;
	//break
	//不能跳出循环,需要将序列1的数录入到tmp数组中,所以只要设置序列2不存在即可
	//要是序列2不存在,只需begin2 > end2 即可
	begin2 = i + 1;
	end2 = i;
}

结果如下:
数据结构——lesson12排序之归并排序,排序合集,数据结构,数据结构,排序算法,算法,c语言
此时就可以使用 memcpy(a, tmp, sizeof(int) * n);啦🥳🥳🥳

注意不可以在跳出break循环后再进行拷贝哦~因为这样没办法知道之前归并好的数据是什么,所以没办法进行归并排序💫💫

2.归并排序复杂度分析

2.1空间复杂度

无论递归还是非递归,我们都使用malloc函数开辟了tmp数组,大小是n,所以它的空间复杂度是O(n);🥳🥳🥳

2.2时间复杂度

我们可以利用非递归的来看归并排序的时间复杂度:
①首先,无论gap是什么,都需要借助for循环来遍历一遍数组进行归并排序每一遍都是n;
②所以只需要确定while循环多少次即可,有因为while循环条件是gap < n,每次gap*=2;
③所以while循环log(n)次所以归并排序非递归的时间复杂度是O(nlogn);
而非递归是利用while循环对递归的另一种表现形式,它们的原理逻辑都是一样的,所以递归版的时间复杂度也应该是O(n
logn);🥳🥳🥳

3.结语

我们学习了归并排序的两种实现——递归与非递归版;并分析了归并排序的时间和空间复杂度,以上就是归并排序的所有内容啦~ 完结撒花~🥳🎉🎉🎉文章来源地址https://www.toymoban.com/news/detail-846060.html

到了这里,关于数据结构——lesson12排序之归并排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法—归并排序&计数排序

    目录 一、归并排序 1、主函数 2、递归实现 3、优化递归  4、非递归实现 5、特性总结: 二、计数排序 1、代码: 2、特性总结: 三、各种排序总结 时间空间复杂度汇总  基本思想: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法 的一个非常典型的

    2024年02月04日
    浏览(46)
  • 数据结构算法--5 归并排序

    我们先看一下归并排序是怎么归并的  两个有序列表,有low指针指向2,high指针指向6,mid指针指向9 再建一个新列表,12,所以1放到列表,右指针右移一位,再比较2和3,2放入列表,左指针右移一位,以此类推,肯定有一部分列表率先没有数,这时将另一列表直接append进入新

    2024年02月11日
    浏览(46)
  • 数据结构与算法:归并排序

    在讲解归并排序前,我们先看到一个问题: 对于这样两个有序的数组,如何将它们合并为一个有序的数组? 在此我们处理这个问题的思路就是:开辟一个新的数组,然后分别安置一个指针在左右数组,利用指针遍历数组,每次对比将比较小的那个元素插入到数组的尾部。 像

    2024年01月21日
    浏览(43)
  • python算法与数据结构---排序和归并排序

    掌握归并排序的基本原理 使用python语言解答归并排序题目 原理及过程 将两个有序的数组合并成一个有序数组称为 从上往下分解:把当前区间一分为二,直至分解为若干个长度为1的子数组 从上往下的合并:两个有序的子区域两两向上合并; 体现了分治思想,稳定排序 复杂

    2024年01月21日
    浏览(70)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(50)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(52)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分:[begin, mid-1],[mid, end] 3.2.2 正确划分:[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(45)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

    排序是计算机内经常进行的一种操作,其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分 内部排序 和 外部排序 ,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能

    2023年04月09日
    浏览(44)
  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(62)
  • 【数据结构】- 排序(详细介绍几种排序算法!!!*直接插入排序,*希尔排序,*选择排序,*堆排序,*冒泡排序,*快速排序,*归并排序)

    排序无处不在,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 内部排序 :数据元素全部放在内存中的排序。 外部排序 :数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 今天

    2024年01月20日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包