数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

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

上次是快排和冒泡:数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意)

今天为大家带来归并排序



1.基本思想

归并排序是一种分治算法,它将序列分成两个子序列,分别对子序列进行排序,然后将排序好的子序列合并起来。这个过程可以递归地进行,直到序列长度小于等于1时停止递归。

在合并子序列的过程中,需要比较两个子序列的元素,并按顺序将它们合并成一个有序序列

注意:归并排序的关键在于合并两个有序的子序列,这一步需要额外的空间来存储中间结果。在实际的实现中,可以使用递归非递归的方式来完成归并排序

数据结构排序——详细讲解归并排序(c语言实现递归及非递归),数据结构,数据结构——排序,数据结构,c语言,排序算法,java,数据挖掘,人工智能,机器学习


2.递归实现

递归归并排序:

  1. 如果序列长度小于等于1,无需排序,直接返回
  2. 将序列分成两个子序列,分别进行递归归并排序
  3. 合并两个已排序的子序列
void _MergeSort(int* a, int* tmp, int left, int right)//是下标,不是值
{
	if (left >= right)//只有一个元素或不存在这样的区间递归停止
	{
		return;
	}
	int mid = (left + right) / 2;//分成两部分,分别有序后再进行归并
	// [begin, mid][mid+1, end]
	_MergeSort(a, tmp, left, mid);
	_MergeSort(a, tmp, mid+1,right );//这两部分都有序啦
	//开始归并:归并到到tmp数组的相同位置,再拷贝回去

	int left1 = left; int right1 = mid;//第一个数组的两端
	int left2 = mid+1; int right2 = right;//第二个数组的两端
	int index = left;//两个数组是从left开始的,left给index就是到相同区间上

	while (left1 <= right1 && left2 <= right2)//两个比,小的放进去
	{
		if (a[left1] < a[left2])
		{
			tmp[index] = a[left1];
			index++;
			left1++;
		}
		else
		{
			tmp[index] = a[left2];
			index++;
			left2++;
		}
	}//有一个排完了,剩下的一个就直接放
	while (left1 <= right1)
	{
		tmp[index] = a[left1];
		index++;
		left1++;
	}
	while (left2 <= right2)
	{
		tmp[index] = a[left2];
		index++;
		left2++;
	}//到此,tmp内已经归并成功,接下来复制回a中
	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

void MergeSort(int* a, int n)
{
	//创建一个临时数组
	int tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	_MergeSort(a, tmp, 0, n - 1);//子函数,在这里递归不好,有动态开辟
	free(tmp);
}

int main()
{
	int a[] = { 10,6,7,1,3,9,4,2 };
	//MergeSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));//用来打印数组的
	MergeSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
	return 0;
}

数据结构排序——详细讲解归并排序(c语言实现递归及非递归),数据结构,数据结构——排序,数据结构,c语言,排序算法,java,数据挖掘,人工智能,机器学习


3.非递归实现

非递归实现归并排序是一种迭代式的排序算法,它避免了递归调用带来的额外开销,通常使用循环和迭代来实现归并排序的过程:

  1. 确定归并区间的思路:对于给定的数组,首先将相邻的元素两两归并(gap=1),然后将归并的区间长度不断扩大,依次归并相邻的区间、长度为 2 的区间、长度为 4 的区间,直到整个数组都归并完成(gap=2)。*
  2. 归并的逻辑:在每次归并的过程中,根据当前的区间长度,确定待归并的两个区间的边界。然后比较这两个区间的元素,并将较小的元素依次放入临时数组中。当某一个区间的元素已经全部放入临时数组后,将另一个区间剩余的元素直接放入临时数组中。
  3. 复制回原数组:在每次归并完成后,将临时数组中归并好的结果复制回原数组中,以便进行下一轮的归并操作。
  4. 不断扩大归并区间:通过不断扩大归并的区间长度,最终完成整个序列的排序
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;//第一次1为长度
	while (gap < n)
	{
		for (int i = 0; i < n ; i += 2*gap)//每次两个区间的左起点都是i ,每次跳过两个gap
		{
			//一个区间里有gap个元素
			int left1 = i; int right1 = i + gap - 1;//第一个区间
			int left2 = i+gap; int right2 = i + 2*gap - 1;//第二个
			
			if (left2 > n)//没有与之相归并的第二个数组
			{
				break;//直接出去,进行下一层
			}
			if (right2 > n)
			{
				right2 = n - 1;
			}

			//开始归并
			int index = i;
			while (left1 <= right1 && left2 <= right2)//两个比,小的放进去
			{
				if (a[left1] < a[left2])
				{
					tmp[index] = a[left1];
					index++;
					left1++;
				}
				else
				{
					tmp[index] = a[left2];
					index++;
					left2++;
				}
			}//有一个排完了,剩下的一个就直接放
			while (left1 <= right1)
			{
				tmp[index] = a[left1];
				index++;
				left1++;
			}
			while (left2 <= right2)
			{
				tmp[index] = a[left2];
				index++;
				left2++;
			}//到此,tmp内已经归并成功,接下来复制回a中
			memcpy(a + i, tmp + i, sizeof(int) * (right2 - i + 1));
		}
		gap *= 2;
	}
}

数据结构排序——详细讲解归并排序(c语言实现递归及非递归),数据结构,数据结构——排序,数据结构,c语言,排序算法,java,数据挖掘,人工智能,机器学习


今天就先讲这么多了,数据结构排序部分也马上迎来了尾声,感谢大家支持!!!文章来源地址https://www.toymoban.com/news/detail-813508.html

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

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

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

相关文章

  • 数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)

    目录 插入排序  希尔排序 选择排序 堆排序 冒泡排序 快速排序 hoare法 挖坑法 前后指针法 快排特性总结 三数取中优化 小区间优化 快排非递归 归并排序 归并排序非递归 计数排序 总结 OJ测试 1、元素集合越接近有序,直接插入排序算法的时间效率越高 2、时间复杂度:O(N^2

    2023年04月09日
    浏览(81)
  • 《数据结构》八大排序(详细图文分析讲解)

    目录 排序 排序的应用       排序简介 排序的分类 排序算法的好坏评判 冒泡排序法  思路分析 代码实现   选择排序法 思路分析 代码实现   插入排序 思路分析 代码实现  希尔排序 思路分析 代码演示  归并排序法  思路分析 代码演示  快速排序  思路分析 代码实现 

    2024年02月03日
    浏览(46)
  • 数据结构进阶篇 之【选择排序】详细讲解(选择排序,堆排序)

    民以食为天,我以乐为先 嘴上来的嘘寒问暖,不如直接打笔巨款 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接选择排序的特性总结 跳转链接:数据结构 之 堆的应用 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀

    2024年04月09日
    浏览(40)
  • 数据结构进阶篇 之 【插入排序】详细讲解(直接插入排序,希尔排序)

    千万不要因为一件事不会做而失去信心,你又不是只有这一件事不会,你还有很多呢 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接插入排序的特性总结 2.1 基本思想 2.2 实现原理 2.3 代码实现 2.4希尔排序的特性总结 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

    2024年04月12日
    浏览(71)
  • 数据结构进阶篇 之 【交换排序】(冒泡排序,快速排序递归、非递归实现)详细讲解

    当你觉的自己不行时,你就走到斑马线上,这样你就会成为一个行人 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 前后指针版本 2.3 快速排序优化 2.3.1 随机数选key 2.3.2 三数取中选key 2.3.3 递归到小的子区间使用插入排

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

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

    2024年01月22日
    浏览(66)
  • 数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(41)
  • 【数据结构】快速排序,归并排序

    1.hoare版本 根据动图的演示,整理的思路如下, 1.定义left,right,key。key默认是左边第一个元素,像两个指针,左边找比key大的,右边找比k小的,找到的话,交换二者,往返这个过程,当left与right相遇时,交换key和此时相遇的值. 单趟下来,6出现在正确的位置。 1.为什么大循环

    2024年01月20日
    浏览(38)
  • 【数据结构】排序(3)—堆排序&归并排序

                                      目录      一. 堆排序       基本思想         代码实现    向上调整算法    向下调整算法       时间和空间复杂度       稳定性     二. 归并排序       基本思想       代码实现       时间和空间复杂度       稳定性      

    2024年02月08日
    浏览(37)
  • 【数据结构】——归并排序和计数排序

    🌇个人主页:_麦麦_ 📚今日名言:繁华落尽,我心中仍有花落的声音。一朵,一朵,在无人的山间轻轻飘落。——席慕蓉《桐花》 目录 一、前言 二、正文 1.归并排序 1.1 基本思想 1.2【递归版】具体实现  1.3【递归版】代码部分  1.4【非递归版】具体实现  1.5【非递归版】

    2023年04月15日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包