归并排序C语言实现与分析

落日映苍穹つ 2022-01-22 07:11 268阅读 0赞

### 归并排序 ###

*  具体代码
 *  过程分析
 *  性能分析

# 具体代码 #

#include<stdio.h>
    
    //将两个有序数组合并的过程
    void Merge(int* R, int start, int mid, int end)
    {
        
    	//需要把元素全誊到这个新数组去
    	int A[end-start+1];
    	//i代表第一个有序数组的起始位置
    	int i = start;
    	//j代表第二个有序数组的起始位置
    	int j = mid+1;
    	//k用来逐个表示A数组中的元素
    	int k = 0;
    
    	//从这两个有序数组中找出小的，逐个放入A数组
    	while(i<=mid && j<=end)
    	{
        
    		//j的小就放j
    		if(R[i]>R[j])
    		{
        
    			A[k] = R[j];
    			j++;
    		}
    		else
    		{
        
    			A[k] = R[i];
    			i++;
    		}
    		k++;
    	}
    	
    	//当出现某个数组放完了之后，直接把另一个数组剩下的全放入A即可
    	//其实下面那两个if可以不写，只不过这里只是增强可读性而已....
    	if(i>mid)
    	{
        
    		while(j<=end)
    		{
        
    			A[k] = R[j];
    			j++;
    			k++;
    		}		
    	}
    	if(j>end)
    	{
        
    		while(i<=mid)
    		{
        
    			A[k] = R[i];
    			i++;
    			k++;
    		}		
    	}
    	
    	//然后再把已经有序了的元素装回到原来啊的R数组
    	for(int m = 0;m<k;m++)
    	{
        
    		R[start] = A[m];
    		start++;
    	}
    }
    
    //归并排序
    void MergeSort(int* R, int start, int end) 
    {
        
    	//如果没把数组分到单个元素，就一直分治
    	if(start<end)
    	{
        
    		//一分为二
    		int mid = (start+end)/2;
    		//左右两边排好序
    		MergeSort(R,start,mid);
    		MergeSort(R,mid+1,end);
    		//拼接到一起
    		Merge(R,start,mid,end);
    	}
    }
    
    int main()
    {
        
    	int M[6] = {
        1,5,3,7,8,2};
    	MergeSort(M,0,5);
    	for(int i=0;i<6;i++)
    	{
        
    		printf("%d  ", M[i]);	
    	}
    }

# 过程分析 #

这是冯诺依曼大佬提出的算法，利用了分治的思想，各层分治递归可以同时进行。所以我连分步解释的图都不好画了。。。。。。  
不过总体流程大概是这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]  
这个算法的主体思路就是把一个数组全部划分成单个元素，单个元素进行比较后合并。由于是递归，多个比较同时发生，所以会更快。每次在比较完后，会得到两个有序数组，只需要将有序数组合并即可（对于只用单个元素的情况，就是直接比大小了）。  
我这里就只讲一下合并步骤的思路了。

合并步骤

1.得到两个有序数组，但是他们在空间上是连在一起的，他们以你之前划分的标准mid元素来分界。  
2.所以两个数组的空间位置分别是  
start—mid， mid+1—end-1  
准备好指针，开始排序即可  
3.由于他们的都是有序数组，从头逐个比较，取走小的那个即可。  
比如：  
A数组-----------1，6，7，9，9  
B数组-----------2，3，4，5，8  
那么我们先从A中取走1，再比较A的第二个元素和B的第一个元素，取走2，同理，继续比较，取走B中的3，然后4，然后5，然后再取A中的7，再取B中的。  
4.这时，B数组已经取完了，只需要把剩下的A中的两个9全部放到数组里即可。  
5.最后注意我们是把数组先有序地誊到一个空的数组里了，还要放回来，完成。

# 性能分析 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]: /images/20220122/569c59fecbba48be936c0fc1cdbc24d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]: /images/20220122/d6b04afd57404f94a5a07e50fecdefc3.png