归并排序详解(C语言和java实现)

左手的ㄟ右手 2022-12-19 11:49 98阅读 0赞

# 自顶向下的归并排序详解（C语言和java实现） #

## 归并排序分析 ##

归并排序其实是一个建立在**分治**算法基础上的一种排序，什么身**分治**算法呢?就是把一个大问题分解成多个小问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。  
分治算法最重要的三个特性：  
**1.分  
2.治  
3.合**  
而我们的归并排序就是把一个长的序列，先分割成两个子序列，再对子序列不断地划分，知道不能划分位置，在对不能划分地部分进行比较，最后再把整个数据合在一起  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center]  
我们会返现，对于归并排序而言，最难和最关键的点就在于**合**，我们只要抓住如何将两个有序的数组进行合并的话，那我们的设计就会简单很多，在这里我们采用标记法来进行合并两个有序数组  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center 1]  
如果能看懂上面这个操作的话，那代码就好些的多了，因为对于一个完整的数组来说，用归并排序排出来的两个有序数组肯定是在同一数组中逻辑相邻的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center 2]  
这是我们就可以先写合并函数Merge,此时我先使用C语言，最后我会教大家用java实现

int B[n];//辅助数组
    void Merge(int A[],int low,int mid,int high){
        
    	for(int k=low,k<=high;k++)
    	B[k]=A[k];
    	for(int i = low,int j=mid+1,int k=low;i<=mid&&j<=high;k++)
    	{
        
    		if(B[i]<=b[j])
    		A[k]=B[i++];
    		else
    		A[k]=B[j++];
    	}
    	while(i<=mid) A[k++]=B[i++];
    	while(j<=high) A[k++]=B[j++];
    }

当我们完成了最关键的合并操作后，那整个程序就已经很清晰了，接下来的重点就是划分了，在这里我们使用了递归思想，不了解递归的朋友们可以先去搜一搜看一看，如果有机会，我会单独讲一次递归给大家

void Mergesort(int A[],int low,int high)
    {
        
    	if(low<high)
    	{
        
    		int mid=(low+high)/2;
    		Mergesort(A,low,mid);
    		Mergesort(A,mid+1,high);
    		Merge(A,low,mid,high);
    	}
    }

这样整个函数就完了，我们在主程序测试一下

int main(){
        
    	int a[10]={
        1,10,2,9,3,8,4,7,5,6};
    	Mergesort(a,0,9);
    	for(int i =0;i<10;i++)
    	{
        
    		printf("%d ",a[i]);
    	}
    }

![在这里插入图片描述][20201107121547730.png_pic_center]  
没有问题

## 算法分析 ##

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。

归并排序总时间=分解时间+子序列排好序时间+合并时间

无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计。

则：归并排序总时间=子序列排好序时间+合并时间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center 3]  
我们可以得到这么一个归并次数，每一层代表一次归并次数，然后在这个树状结构里，我们可以看出来，归并的路径实际上是一个**二叉决策树**，二叉树的第h层最多有2(h-1)个结点，若树的高度为h，则应满足n<=2(h-1),即：h-1=\[logn\]  
结论：n个元素进行归并排序，归并的次数为logn次，而每次归并的过程里都要将每两个有序数组挨个遍历一遍，所以每一次的时间复杂度为O(n),最后可以得出，归并排序所需要的时间复杂度为O(nlogn),空间上我们利用了一个辅助数字B\[n\]  
![在这里插入图片描述][20201107123211440.png_pic_center]

## java实现 ##

这里原理我已经讲过了，二话不说，直接上代码

import java.util.Arrays;
    
    public class MergeSort {
        
    
    	public static void main(String[] args) {
        
    		int[] A= {
        1,10,2,9,3,8,4,7,5,6};
    		int a=A.length;
    		MergeSort(A,0,a-1);
    		System.out.print(Arrays.toString(A));
    	}
    
    	public static void  Merge(int[] A,int low,int mid,int high) {
        
    		int[] B=new int[A.length];
    		int i,j,k;
    		for(k=low;k<=high;k++)
    			B[k]=A[k];
    		for( i =low,j=mid+1,k =low;i<=mid&&j<=high;k++)
    		{
        
    			if(B[i]<=B[j])
    				A[k]=B[i++];
    			else 
    				A[k]=B[j++];
    		}
    		while(i<=mid) A[k++]=B[i++];
    		while(j<=high) A[k++]=B[j++];
    	}
    	
    	public static void MergeSort(int[] A,int low,int high)
    	{
        
    		if(low<high)
    		{
        
    			int mid=(low+high)/2;
    			MergeSort(A,low,mid);
    			MergeSort(A,mid+1,high);
    			Merge(A,low,mid,high);
    		}
    	}
    }

## 总结 ##

我这里只是写了最简单也是最传统的归并排序，并且我这种方法是自顶向下的，还有一种自底向上的排序方法，留给大家自行讨论。谢谢您的访问，如果觉得有帮助麻烦点个赞哦，欢迎指出错误~~~

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8f232607cda24cb1864c53c80a4520f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/2bd558bb288444d198ab8e2f939bd019.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/f3781ef446244c6aa0da78ee9a32b09f.png
[20201107121547730.png_pic_center]: /images/20221120/b7b3a8b19bb64488bf3dce8eb69c6633.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDUzMzIw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/2b4afbae585f41f7a3dfa9c1a644e2cc.png
[20201107123211440.png_pic_center]: /images/20221120/38a872f14d3e4a1089701b7054fef8cb.png