归并算法:分治而治的高效算法大揭秘(图文详解)

这篇具有很好参考价值的文章主要介绍了归并算法:分治而治的高效算法大揭秘(图文详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++

🎬 鸽芷咕:个人主页

 🔥 个人专栏: 《数据结构&算法》《粉丝福利》
⛺️生活的理想,就是为了理想的生活!

📋 前言

归并算法是我们算法中最常见的算法之一,其思想非常巧妙。本身归并是只能归并有序数组但是当我们利用了二路归并分治法之后,就可以使用归并的思想来帮我们排序其算法性能属于第一梯队。

一、什么是归并排序

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

1.1 归并的核心思想

归并的思想大家都知道就是俩个有序数组的数据进行比较,如果 数组一的数据小 就把它插入到我们的新数组里面:

  • 当一个数组比较完后直接把另一个还没比较完的有序数组数组插入到新数组就归并完了

🔥 注:归并的前提是俩个数组都是有序的。

1.2 归并排序的图文解析

那么我们无序数组想要排成有序的改怎么办,这时就有人提出了分治的思想把每个数组的数据都看为一个有序数组,在进行归并

归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++

先递归进行分割然后再利用递归返回的特性来进行,回溯归并这样就可以达成俩个有序数组合并了

归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++

二、归并排序的实现

归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++
归并的思想讲完了,以上就是归并排序的全部过程了,诶这样大家是不是理解起来更方便了,既然是归并那么必须就需要一个另一个空间来存放数据:

  • 而我们需要归并的数组就是原数组所递归分割我区间每次归并完了之后在复制
  • 回原数组,这样就能从归并一个数据到整个数组的数据了;

归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++

-归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++
归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&算法》,算法,数据结构,排序算法,c++

2.1 实现代码

好滴思路捋清楚了,代码实现就简单首先我们需要开辟一个和排序数组一模一样大的空间那么就 malloc 一个但是我们需要递归分割所以肯定不能再这个函数里面进行递归这时就需要:

  • _MergeSort 来进行递归分割排序数组
  • 剩下的注意好每次分割的区间和,每次归并完了复制到原数组就好了

🍸 代码演示:

void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (end <= begin)
		return;

	int mid = (begin + end) / 2;
	//[begin, mid-1] [mid, end]
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid+1, end);

	//开始归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	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 (begin2 <= end2)
	{
		tmp[index++] = 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);
	if (tmp == NULL)
	{
		perror("malloc file");
		exit(-1);
	}

	_MergeSort(a, tmp, 0, n-1);

	free(tmp);
}

这里每次的区间都是数组的区间,只要分割好了,那么就照着思路写下去就好了

三、归并排序的总结

总体来说归并排序的性能还是非常好的采取的是拿空间换时间的概念,归并排序的思考更多的是解决在磁盘中的外排序问题。

  1. 归并的缺点在于需要O(N)的空间复杂度
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

📝文章结语:

看到这里了还不给博主扣个:
⛳️ 点赞🍹收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。
归并算法:分治而治的高效算法大揭秘(图文详解),《数据结构&amp;算法》,算法,数据结构,排序算法,c++文章来源地址https://www.toymoban.com/news/detail-776028.html

到了这里,关于归并算法:分治而治的高效算法大揭秘(图文详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++算法 —— 分治(2)归并

    本篇前提条件是已学会归并排序 912. 排序数组 排序数组也可以用归并排序来做。 剑指 Offer 51. 数组中的逆序对 如果暴力枚举,一定是可以解决问题的,但肯定不用这个解法。选择逆序对,可以先把数组分成两部分,左半部分 + 右半部分的逆序对,以及再找左半部分的数字和

    2024年02月10日
    浏览(40)
  • 【算法系列篇】分治-归并

    上一篇算法文章,我们介绍了分治-快排的算法,今天我将为大家分享关于分治的另外一种算法——归并。 归并算法是一种常用的排序算法,它采用分治策略将待排序的数组分解为更小的子数组,然后逐步合并这些子数组以获得最终的有序数组。归并排序的主要思想是将两个

    2024年02月09日
    浏览(48)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(53)
  • 算法:分治思想处理归并递归问题

    利用归并思想进行分治也是很重要的一种思路,在解决逆序对的问题上有很大的需求空间 于是首先归并排序是首先的,归并排序要能写出来: 以上为归并排序基本算法原理,基于这个原理可以解决逆序对问题,逆序对问题通常问法是,给定某一个数据,在整个数组中找比这

    2024年02月10日
    浏览(43)
  • 算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解

    引言,少年们,大家好。在这里祝大家元旦快乐,我是博主 那一脸阳光 ,今天来介绍二分查找 在计算机科学领域,搜索算法是数据处理和问题解决的重要工具之一。其中,**二分查找算法(Binary Search)**以其卓越的时间复杂度和简洁高效的实现,在众多搜索算法中脱颖而出

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

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

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

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

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

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

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

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

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

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

    2024年02月21日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包