这个 归并排序详解过程 我能吹一辈子!!!

这篇具有很好参考价值的文章主要介绍了这个 归并排序详解过程 我能吹一辈子!!!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

归并排序概念

1945年,约翰·冯·诺依曼(John von Neumann)发明了归并排序,这是典型的分治算法的应用。

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

归并排序算法思路

归并排序算法有两个基本的操作,一个是分,也就是把原数组划分成两个子数组的过程。另一个是治,它将两个有序数组合并成一个更大的有序数组。

1> 将待排序的线性表不断地切分成若干个子表,直到每个子表只包含一个元素,这时,可以认为只包含一个元素的子表是有序表。
2> 将子表两两合并,每合并一次,就会产生一个新的且更长的有序表,重复这一步骤,直到最后只剩下一个子表,这个子表就是排好序的线性表。
这个 归并排序详解过程 我能吹一辈子!!!

相信大家都知道如何将两个有序序列合为一个有序序列吧:
这个 归并排序详解过程 我能吹一辈子!!!

那么如何得到有序的子序列呢?当序列分解到只有一个元素或是没有元素时,就可以认为是有序了,这时分解就结束了,开始合并:
这个 归并排序详解过程 我能吹一辈子!!!

归并排序递归实现

归并排序,从其思想上看就很适合使用递归来实现,并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列,合并完毕后再将数据拷贝回原数组。

代码示例:

//归并排序(子函数)
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)//归并结束条件:当只有一个数据或是序列不存在时,不需要再分解
	{
		return;
	}
	int mid = left + (right - left) / 2;//中间下标
	_MergeSort(a, left, mid, tmp);//对左序列进行归并
	_MergeSort(a, mid + 1, right, tmp);//对右序列进行归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	//将两段子区间进行归并,归并结果放在tmp中
	int i = left;
	while (begin1 <= end1&&begin2 <= end2)
	{
		//将较小的数据优先放入tmp
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//归并完后,拷贝回原数组
	int j = 0;
	for (j = left; j <= right; j++)
		a[j] = tmp[j];
}
//归并排序(主体函数)
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与原数组大小相同的空间
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);//归并排序
	free(tmp);//释放空间
}

时间复杂度:O(N*logN)  空间复杂度:O(N)

归并排序非递归实现

归并排序的非递归算法并不需要借助栈来完成,我们只需要控制每次参与合并的元素个数即可,最终便能使序列变为有序:
这个 归并排序详解过程 我能吹一辈子!!!
当然,以上例子是一个待排序列长度比较特殊的例子,我们若是想写出一个广泛适用的程序,必定需要考虑到某些极端情况:

情况一
 当最后一个小组进行合并时,第二个小区间存在,但是该区间元素个数不够gap个,这时我们需要在合并序列时,对第二个小区间的边界进行控制。
这个 归并排序详解过程 我能吹一辈子!!!

情况二
 当最后一个小组进行合并时,第二个小区间不存在,此时便不需要对该小组进行合并。
这个 归并排序详解过程 我能吹一辈子!!!

情况三
 当最后一个小组进行合并时,第二个小区间不存在,并且第一个小区间的元素个数不够gap个,此时也不需要对该小组进行合并。(可与情况二归为一类)
这个 归并排序详解过程 我能吹一辈子!!!

只要把控好这三种特殊情况,写出归并排序的非递归算法便轻而易举了。

代码示例:

//归并排序(子函数)
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
	int j = begin1;
	//将两段子区间进行归并,归并结果放在tmp中
	int i = begin1;
	while (begin1 <= end1&&begin2 <= end2)
	{
		//将较小的数据优先放入tmp
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//归并完后,拷贝回原数组
	for (; j <= end2; j++)
		a[j] = tmp[j];
}
//归并排序(主体函数)
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间,用于辅助合并序列
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	int gap = 1;//需合并的子序列中元素的个数
	while (gap < n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个,此时不需要对该小组进行合并
				break;
			if (end2 >= n)//最后一组的第二个小区间不够gap个,则第二个小区间的后界变为数组的后界
				end2 = n - 1;
			_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列
		}
		gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍
	}
	free(tmp);//释放空间
}

时间复杂度:O(N*logN)  空间复杂度:O ( N )文章来源地址https://www.toymoban.com/news/detail-454043.html

到了这里,关于这个 归并排序详解过程 我能吹一辈子!!!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 归并排序的具体实现过程

    作者主页: paper jie的博客_CSDN博客-C语言,算法详解领域博主 本文作者: 大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于 《算法详解》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将算法基础知识一网打尽,希望

    2024年02月12日
    浏览(28)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(66)
  • 【初阶算法4】——归并排序的详解,及其归并排序的扩展

    目录 前言 学习目标: 学习内容: 一、介绍归并排序 1.1 归并排序的思路 1.2 归并排序的代码 1.2.1 mergesort函数部分  1.2.2 process函数部分  1.2.3 merge函数部分  二、AC两道经典的OJ题目 题目一:逆序对问题 题目二:小和问题  三、练习一道LeetCode的题目 四、总结在什么情况下使

    2024年02月08日
    浏览(39)
  • C++排序算法:归并排序详解

    一、归并排序 二、基本算法         1、分离         2、合并         3、图片讲解 三、代码实现         1、分离函数         2、合并函数          3、完整代码          4、样例 四、总结          归并排序 (Merge Sort)是建立在归并操作上的一种既有效又稳

    2024年02月12日
    浏览(40)
  • 【排序算法】 归并排序详解!分治思想!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是归并?通过归并排序就能让数据有序?分治法是怎么在归并排序上应用的?本文将对归并排序进行细致入微的讲解,庖丁解牛般让你彻底明白归并排序! 归并排序(MERGE-SORT)是建

    2024年02月08日
    浏览(43)
  • 算法基础(一)| 快速排序和归并排序详解

    ⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法

    2024年02月21日
    浏览(48)
  • 【排序算法】 归并排序详解!深入理解!思想+实现!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是归并?通过归并排序就能让数据有序?分治法是怎么在归并排序上应用的?本文将对归并排序进行细致入微的讲解,庖丁解牛般让你彻底明白归并排序! 归并排序(MERGE-SORT)是建

    2024年02月08日
    浏览(42)
  • 【排序算法】 归并排序详解!深入理解!思想+源码实现!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是归并?通过归并排序就能让数据有序?分治法是怎么在归并排序上应用的?本文将对归并排序进行细致入微的讲解,庖丁解牛般让你彻底明白归并排序! 归并排序(MERGE-SORT)是建

    2024年02月06日
    浏览(43)
  • 【算法】归并排序 详解

    排序: 排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中, r[i] = r[j], 且 r[i] 在 r[j] 之前,而

    2024年02月09日
    浏览(31)
  • 归并排序的详解!

    本文旨在讲解归并排序的实现(递归及非递归)搬好小板凳,干货来了!   在介绍归并排序之前,需要给大家介绍的是什么是归并, 归并操作,也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法 ,相信不少小伙伴之前都做过合并两个有序链表或者两个有序数

    2024年02月10日
    浏览(28)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包