一起学数据结构(12)——归并排序的实现

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

1. 归并排序原理:

归并排序的大概原理如下图所示:

一起学数据结构(12)——归并排序的实现,1024程序员节

        从图中可以看出,归并排序的整体思路就是把已给数组不断分成左右两个区间,当这个区间中的数据数量到达一定数值时,便返回去进行排序,整体的结构类似二叉树的结构,因此,对于归并排序同样可以利用递归进行实现。

       对于递归实现归并排序,首先需要实现的第一步便是如何区分左右区间,在快速排序中,虽然在递归时依然同样需要根据一个值来区分左右区间,但是用于区分左右区间的值是在左右两边遍历数组时自动选出来的,对于归并排序,通过观察可以发现,归并排序的左右区间是通过数组下标的中间值进行区分的,为了方便表示,将这个中间值命名为,例如,数组在进行第一次区分左右区间时,左区间的范围是,右区间的范围是通过计算不难得到,所以,对于数组左右区间的划分,可以通过,(数组下标起始),(数组下标末位来划分)即

                                                          左区间范围:

                                                          右区间范围:一起学数据结构(12)——归并排序的实现,1024程序员节

       同时,在图中当区间中的数值数量为后,下一步直接进行排序,此处图中省略了区间分为两个区间数值数量为的两个区间的过程,这是因为,在区间中的数值数量时,便停止划分区间

所以,对于区间划分这部分的递归,可以用代码表示为:

 //归并排序
 void _MergeSort(int* a, int begin, int end)
 {
	 if (begin >= end)
	 {
		 return;
	 }

	 int mid = (begin + end) / 2;

	 MergeSort(a, begin, mid);
	 MergeSort(a,mid + 1, end);
 }

在区间划分结束后,就需要对数组进行排序。这里需要注意,在进行排序时,不能直接在原本已有的数组进行排序,为了解决这个问题,本文选择独立开辟一块空间用于排序,当一部分区间在这部分空间排序完成后,便将这部分内容返回到原数组,开辟空间的过程如下:

 void MergeSort(int* a, int begin, int end)
 {
	 int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
	 if (tmp == NULL)
	 {
		 perror("malloc fail");

	 }
	 _MergeSort(a, tmp, begin, end);
 }

因为开辟的空间需要在上面的函数中使用,所以对于函数的定义需要更改为上图中的格式。

对于如何排序,文章给出下面的方法:

对于一个区间,定义四个变量,分别为:,,,具体使用方法如下:

令,,一起学数据结构(12)——归并排序的实现,1024程序员节,,具体使用方法如下方的代码所示:

 //归并排序
 void _MergeSort(int* a,int* tmp, int begin, int end)
 {
	 if (begin >= end)
	 {
		 return;
	 }

	 int mid = (begin + end) / 2;

	 _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));
 }

为了方便解释代码内容,给出下面的图像:

一起学数据结构(12)——归并排序的实现,1024程序员节

 首先对左右区间进行区分,期间各个区间的,,,如图所示,当区间数据数量时,停止区分区间进行排序,例如对这个区间,如果,则让小的哪个值插入到,此时中的内容如下图所示:

一起学数据结构(12)——归并排序的实现,1024程序员节

向原数组拷贝数值后,原数组左区间数值如下:

一起学数据结构(12)——归并排序的实现,1024程序员节

在区间遍历完成后,再遍历区间,由于 的不同,再数据调整完拷贝到后,数组内容为:

一起学数据结构(12)——归并排序的实现,1024程序员节 

随后再向原数组中拷贝,原数组内容为

一起学数据结构(12)——归并排序的实现,1024程序员节 

对于其他的序列,依旧按照此规律,此部分不再叙述。

测试函数如下:
 

void TestMergeSort()
{
	int i[] = { 10,6,7,1,3,9,4,2 };
	int size = sizeof(i) / sizeof(int);
	MergeSort(i, 0, size - 1);
	printf("归并排序:");
	ArrayPrint(i, size);
}

运行结果如下:

一起学数据结构(12)——归并排序的实现,1024程序员节

 文章来源地址https://www.toymoban.com/news/detail-720802.html

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

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

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

相关文章

  • 【数据结构与算法】:非递归实现快速排序、归并排序

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

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

    目录 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日
    浏览(50)
  • 【数据结构】归并排序的两种实现方式与计数排序

    前言:在前面我们讲了各种常见的排序,今天我们就来对排序部分收个尾,再来对归并排序通过递归和非递归的方法进行实现,与对计数排序进行简单的学习。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博

    2024年01月18日
    浏览(50)
  • 【数据结构】—超级详细的归并排序(含C语言实现)

    ​                                         食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:斜陽—ヨルシカ            

    2024年02月08日
    浏览(44)
  • 数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

    上次是快排和冒泡:数据结构排序——详解快排及其优化和冒泡排序(c语言实现、附有图片与动图示意) 今天为大家带来归并排序 归并排序是一种分治算法,它将序列分成两个子序列,分别对 子序列进行排序 ,然后将排序好的子序列 合并起来 。这个过程可以 递归 地进行,

    2024年01月22日
    浏览(67)
  • 数据结构:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 排序:使一串数据,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 插入排序的思路:把待排序数组,逐个插入到已经排好序的有序数组中,直到所有待排序数组插入完成,的到一个新的有序

    2024年02月11日
    浏览(54)
  • 数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)

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

    2023年04月09日
    浏览(87)
  • 【算法与数据结构】归并排序的代码实现(详细图解)以及master公式的讲解

    目录 1、归并排序  1.1、算法描述  1.2、图解说明 2、代码实现  3、master公式 3.1、公式以及结论 3.2、适用于某些特殊的递归 3.3、计算归并排序的时间复杂度 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 递归 或者说是 分治法 (Divide and Conquer)的一个非

    2024年02月08日
    浏览(62)
  • 数据结构——排序算法——归并排序

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

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

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

    2024年01月20日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包