数据结构归并排序（Merge Sort）详解附C++代码实现：

た入场券 2024-02-19 18:11 67阅读 0赞

**目录**

简介：

算法描述：

代码实现：

总结：

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

## 简介： ##

归并排序是典型的递归思想的应用，将一个序列分为两个子序列，叫做二路归并，是一种稳定的排序算法，时间复杂度为：O(nlogn）

## 算法描述： ##

![849589-20171015230557043-37375010.gif][]

*  把长度为n的输入序列分成两个长度为n/2的子序列；
 *  对这两个子序列分别采用归并排序；
 *  将两个排序好的子序列合并成一个最终的排序序列。

## 代码实现： ##

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    using namespace std;
    #define num 10000
    void mergearray(int a[],int first,int mid,int last,int t[])
    {
    	int i=first,j=mid+1;
    	int n=mid,m=last;
    	int k=0;
    	while(i<=n&&j<=m)
    	{
    		if(a[i]<=a[j])
    		t[k++]=a[i++];
    		else
    		t[k++]=a[j++];
    	}
    	while(i<=n)
    	{
    		t[k++]=a[i++];
    	}
    	while(j<=m)
    	{
    		t[k++]=a[j++];
    	}
    	for(i=0;i<k;i++)
    	{
    		a[first+i]=t[i];
    	}
    }
    
    void mergesort(int a[],int first,int last,int t[])
    {
    	if(first<last)
    	{
    		int mid=(first+last)/2;
    		mergesort(a,first,mid,t);
    		mergesort(a,mid+1,last,t);
    		mergearray(a,first,mid,last,t);
    	}
    }
    
    
    int MergeSort(int a[],int len)
    {
    	int *temp=new int [len];
    	if(temp==NULL)
    	return 0;
    	else
    	mergesort(a,0,len-1,temp);
    	delete []temp;
    	return 1;
    } 
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	freopen("out_arr.txt","r",stdin);
    	freopen("out归并排序.txt","w",stdout);
    	int arr[num];
    	int n=num;
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",&arr[i]);
    	}
    	MergeSort(arr,n);
    	for(int i=0;i<n;i++)
    	{
    		printf("%5d ",arr[i]);
    		if((i+1)%50==0)
    		printf("\n");
    	}
    	end=clock();
    	printf("归并排序耗时：%dms\n",(float)(end-start)*1000.0/CLOCKS_PER_SEC);
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1][]

## 总结： ##

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

小伙伴们，如果还看不懂，在评论区留言，乐意解答。

##  ##

[849589-20171015230557043-37375010.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c0a392c6ab0249daaf8cb94c117a5f15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/695eb39a73894780bca796f0fc08b954.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f4a81fe9566b4993ac8851b478c65c93.png