常见排序算法之归并排序——归并排序

Bertha 。 2023-10-03 19:34 17阅读 0赞

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm_size_20_color_FFFFFF_t_70_g_se_x_16][]

哈喽大家好，我是保护小周ღ，本期为大家带来的是常见[排序算法][Link 1]中的**归并排序**，博主在这里先分享归并排序的递归算法，包您一看就会，快来试试吧~

![f89deef4fd5b408f8b4b1c0a50c0a9e9.png][]

![85764f66f6234828a19ffa3d1f192f6b.png][]

--------------------

**目录**

一、归并排序

1.1 基本思想

1.2 算法思想

1.3 程序设计思想

1.4 程序实现

1.5 归并排序的特性总结：

--------------------

### 一、归并排序 ###

#### 1.1 基本思想 ####

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

--------------------

#### 1.2 算法思想 ####

![6ad3b8700b9548e1b0c41ae7f1714df7.png][]

到这里，我们可以得到一条结论，**两个有序的子序列可以合成一个新的有序子序列**，通过递归，我们两个新的有序序列也可以组成新的有序数列，最终实现排序的目的。有些朋友就会问了，这个我懂，关键是咋实现有序数列，其实非常的简单，分割递归至每个子序列只有一个元素时，是不是就有序啦，然后就可以合成有两个元素有序的列表嘛，再合成4个，8个……

![3f916a693fd449d4b20d92e5e45a559b.png][]

--------------------

#### 1.3 程序设计思想 ####

定义一个tmp数组，可以是动态开辟的(malloc)，用于临时存放合并后的有序数据，定义\_MergeSort()函数，用于分解，合并数据（递归实现），参数有，待处理数组，数据区间（数组下标），tmp数组。

> 1.  判断区间是否存在，区间不存在以及只有**一个元素**的情况结束程序。
> 2.  分割区间：mid=(left+right)/2;递归左右区间，分割递归至每个子序列只有一个元素。
> 3.  每两个子序列一组，循环遍历每一个元素，if比较两个子序列各元素的大小，取大或取小，放入tmp数组，tmp\[index++\]=子序列++；直到有一个子序列遍历完，循环结束。
> 4.  循环判断是子序列是否遍历完毕，未遍历完毕的子序列剩余元素直接给到tmp数组。
> 5.  将tmp数组的对应的元素拷贝回原数组（已有序）。

--------------------

#### 1.4 程序实现 ####

#define _CRT_SECURE_NO_WARNINGS
    
    #include<stdio.h>
    #include<stdlib.h>//动态开辟空间的函数的头文件
    
    void _MergeSort(int *a,int left,int right,int *tmp)
    {
    	//区间不存在以及只有一个元素的情况结束程序
    	if (left>=right)
    	{
    		return;
    	}
    
    	int mid = (left + right) / 2;
    	//假设[left,mid],[mid+1,right]有序，那么我们就可以归并了
    	//递归使左右区间有序
    	//分割递归至每个子序列只有一个元素
    	_MergeSort(a,left,mid,tmp);
    	_MergeSort(a, mid+1,right, tmp);
    
    	//归并
    	int begin1 = left, end1 = mid;
    	int begin2 = mid + 1, end2 = right;
    	int index = left;
    
    	while (begin1<=end1&&begin2<=end2)//有一个子序列遍历完，循环结束
    	{
    		if (a[begin1] < a[begin2])//升序，取小
    		{
    			tmp[index++] = a[begin1++];
    
    		}
    		else
    		{
    			tmp[index++] = a[begin2++];
    		}
    	}
    
    	//判断子序列是否遍历完，未遍历完毕的子序列剩余元素直接给到tmp数组
    	while (begin1 <= end1)
    	{
    		tmp[index++] = a[begin1++];
    	}
    
    	while (begin2<=end2)
    	{
    		tmp[index++] = a[begin2++];
    	}
    
    	//拷贝回去
    	for (int i=left;i<=right;++i)
    	{
    		a[i] = tmp[i];
    	}
    }
    
    //归并排序
    void MergeSort(int *a,int n)
    {
    	int* tmp=(int*)malloc(sizeof(int)*n);//动态开辟与待排序数组大小相等的一片连续的空间
    	_MergeSort(a,0,n-1,tmp);//子函数实现归并
    
    	free(tmp);//释放动态开辟的空间
    }
    
    //打印
    void Print(int* a, int n)
    {
    	for (int i=0;i<n;++i)
    	{
    		printf("%d ",a[i]);
    	}
    }
    int main()
    {
    	int a[] = {10,6,7,1,3,9,4,2};
    	MergeSort(a,sizeof(a)/sizeof(a[0]));
    	Print(a,sizeof(a)/sizeof(a[0]));
    	return 0;
    }

![e067349a59794cf3bbaad928f05f06cb.png][]

--------------------

#### 1.5 归并排序的特性总结： ####

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。

2. 时间复杂度：O(N\*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

--------------------

至此归并排序的递归算法博主已经分享完了，相信大家对这个归并排序的逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下。

![40e36dfc27804c04afb4a9da45afda94.jpeg][]

本期收录于博主的专栏——排序算法，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“常见排序”。[排序算法\_保护小周ღ的博客-CSDN博客][-CSDN]

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ ——归并排序非递归算法

文章存在借鉴，如有侵权请联系修改删除！

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8c9e9ec025db4ad1884bbc8f2cb13814.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm,size_20,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://so.csdn.net/so/search?q=%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&spm=1001.2101.3001.7020
[f89deef4fd5b408f8b4b1c0a50c0a9e9.png]: https://img-blog.csdnimg.cn/f89deef4fd5b408f8b4b1c0a50c0a9e9.png
[85764f66f6234828a19ffa3d1f192f6b.png]: https://img-blog.csdnimg.cn/85764f66f6234828a19ffa3d1f192f6b.png
[6ad3b8700b9548e1b0c41ae7f1714df7.png]: https://img-blog.csdnimg.cn/6ad3b8700b9548e1b0c41ae7f1714df7.png
[3f916a693fd449d4b20d92e5e45a559b.png]: https://img-blog.csdnimg.cn/3f916a693fd449d4b20d92e5e45a559b.png
[e067349a59794cf3bbaad928f05f06cb.png]: https://img-blog.csdnimg.cn/e067349a59794cf3bbaad928f05f06cb.png
[40e36dfc27804c04afb4a9da45afda94.jpeg]: https://img-blog.csdnimg.cn/40e36dfc27804c04afb4a9da45afda94.jpeg
[-CSDN]: https://blog.csdn.net/weixin_67603503/category_11904303.html