归并排序中的分治与递归

偏执的太偏执、 2022-05-14 15:56 235阅读 0赞

在计算机科学中，分治与递归是两个很容易混淆的概念。我觉得很有必要搞清楚二者之间的关系。我的理解，分治是一种思想，递归是一种手段。下面是百科里面对分治和递归的定义：

【分治算法】的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

程序调用自身的编程技巧称为【递归】。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

在众多的排序算法中，有一种算法能够直观明了地体现分治和递归的关系，那就是【归并排序】。

归并排序的基本思路：将一个数组分成两部分，两个部分各自排序，然后将两个部分归并，得到最终结果。

听起来好像还差了点什么，这里缺的就是分治思想：一个规模为N的问题，把它分解成2个规模为N/2的问题，它们的规模依旧很大，所以要把它们一直分解下去，直到计算机能够很轻易地解决它们。当归并排序中的子数组长度为2的时候（即子数组中只有2个元素），归并就成为了一种排序。接下来将归并后的最小子数组作为待归并的一部分返回给更大规模的子数组，以此类推，就完成了归并排序中的分治。

基于上述的分治思想，应该没有比递归更好的解决办法了。先看一个例子：

初始化逆序数组a：16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

假设每次归并数组的下界为lo，上界为hi，定义对称点mid=lo+(hi-lo)/2。

下面是利用递归的归并过程（红色部分为每次归并的数组）：

lo=0, mid=0, hi=1  
15 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1

lo=2, mid=2, hi=3  
15 16 13 14 12 11 10 9 8 7 6 5 4 3 2 1

lo=0, mid=1, hi=3  
13 14 15 16 12 11 10 9 8 7 6 5 4 3 2 1

lo=4, mid=4, hi=5  
13 14 15 16 11 12 10 9 8 7 6 5 4 3 2 1

lo=6, mid=6, hi=7  
13 14 15 16 11 12 9 10 8 7 6 5 4 3 2 1

lo=4, mid=5, hi=7  
13 14 15 16 9 10 11 12 8 7 6 5 4 3 2 1

lo=0, mid=3, hi=7  
9 10 11 12 13 14 15 16 8 7 6 5 4 3 2 1

lo=8, mid=8, hi=9  
9 10 11 12 13 14 15 16 7 8 6 5 4 3 2 1

lo=10, mid=10, hi=11  
9 10 11 12 13 14 15 16 7 8 5 6 4 3 2 1

lo=8, mid=9, hi=11  
9 10 11 12 13 14 15 16 5 6 7 8 4 3 2 1

lo=12, mid=12, hi=13  
9 10 11 12 13 14 15 16 5 6 7 8 3 4 2 1

lo=14, mid=14, hi=15  
9 10 11 12 13 14 15 16 5 6 7 8 3 4 1 2

lo=12, mid=13, hi=15  
9 10 11 12 13 14 15 16 5 6 7 8 1 2 3 4

lo=8, mid=11, hi=15  
9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8

lo=0, mid=7, hi=15  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

实现代码：

public class merge_sort {
    	private static int[] aux;//辅助数组
    
    	public static void sort(int[] a){
    		aux=new int[a.length];
    		sort(a, 0, a.length-1);
    	}//调用排序算法
    	
    	private static void sort(int[] a, int lo, int hi){
    		if (hi<=lo)
    			return;//当前排序结束条件
    
    		int mid=lo+(hi-lo)/2;
    		sort(a, lo, mid);//s1:排序前半部分
    		sort(a, mid+1, hi);//s2:排序后半部分
    		merge(a, lo, mid, hi);//s1与s2执行完后归并两部分
    	}
    	
    	public static void merge(int[] a, int lo, int mid, int hi){
    		int i=lo, j=mid+1;
    		for (int k=lo; k<=hi; k++)
    			aux[k]=a[k];
    		
    		for (int k=lo; k<=hi; k++)
    			if (i>mid)
    				a[k]=aux[j++];
    			else if (j>hi)
    				a[k]=aux[i++];
    			else if (aux[j]<aux[i])
    				a[k]=aux[j++];
    			else
    				a[k]=aux[i++];
    	}//归并算法
    }

归并过程：

归并递归树（缩进量代表深度，执行顺序从上到下）
    
                merge(a, 0, 0, 1)
    
                merge(a, 2, 2, 3)
    
            merge(a, 0, 1, 3)
    
                merge(a, 4, 4, 5)
    
                merge(a, 6, 6, 7)
    
            merge(a, 4, 5, 7)
    
        merge(a, 0, 3, 7)
    
                merge(a, 8, 8, 9)
    
                merge(a, 10, 10, 11)
    
            merge(a, 8, 9, 11)
    
                merge(a, 12, 12, 13)
    
                merge(a, 14, 14, 15)
    
            merge(a, 12, 13, 15)
    
        merge(a, 8, 11, 15)
    
    merge(a, 0, 7, 15)