自顶向下与自底向上的归并排序

刺骨的言语ヽ痛彻心扉 2022-04-21 22:58 284阅读 0赞

自顶向下和自底向上归并排序是两个归并顺序不同的排序过程。通过例子来说明：

初始化数组：int a\[\]=\{16, 15, 14, 13. 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1\}

自顶向下：

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

自底向上：

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=4, mid=4, hi=5
    15 16 13 14 11 12 10 9 8 7 6 5 4 3 2 1 
    
    lo=6, mid=6, hi=7
    15 16 13 14 11 12 9 10 8 7 6 5 4 3 2 1 
    
    lo=8, mid=8, hi=9
    15 16 13 14 11 12 9 10 7 8 6 5 4 3 2 1 
    
    lo=10, mid=10, hi=11
    15 16 13 14 11 12 9 10 7 8 5 6 4 3 2 1 
    
    lo=12, mid=12, hi=13
    15 16 13 14 11 12 9 10 7 8 5 6 3 4 2 1 
    
    lo=14, mid=14, hi=15
    15 16 13 14 11 12 9 10 7 8 5 6 3 4 1 2 
    
    lo=0, mid=1, hi=3
    13 14 15 16 11 12 9 10 7 8 5 6 3 4 1 2 
    
    lo=4, mid=5, hi=7
    13 14 15 16 9 10 11 12 7 8 5 6 3 4 1 2 
    
    lo=8, mid=9, hi=11
    13 14 15 16 9 10 11 12 5 6 7 8 3 4 1 2 
    
    lo=12, mid=13, hi=15
    13 14 15 16 9 10 11 12 5 6 7 8 1 2 3 4 
    
    lo=0, mid=3, hi=7
    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

归并递归树（缩进量代表深度，执行顺序从上到下）
    
    自顶向下归并递归树：
     
                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)
    
    自底向上归并递归树：
    sz=1
                merge(a, 0, 0, 1)
                merge(a, 2, 2, 3)
                merge(a, 4, 4, 5)
                merge(a, 6, 6, 7)
                merge(a, 8, 8, 9)
                merge(a, 10, 10, 11)
                merge(a, 12, 12, 13)
                merge(a, 14, 14, 15)
    sz=2
            merge(a, 0, 1, 3)
            merge(a, 4, 5, 7)
            merge(a, 8, 9, 11)
            merge(a, 12, 13, 15)
    sz=4
        merge(a, 0, 3, 7)
        merge(a, 8, 11, 15)
    sz=8
    merge(a, 0, 7, 15)

可以通过遍历子数组大小组成的二叉树来理解归并排序的顺序（数字为数组大小，字母为数组编号）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70][]

自顶向下（二叉树中序遍历）：H I D J K E B L M F N O G C A

自底向上（二叉树按层次遍历）：H I J K L M N O D E F G B C A

代码：

public class merge_sort{
        private static int[] aux;
    /*自顶向下*/
    public static void sort(int[] a){
    		aux=new int[N];
    		sort(a, 0, N-1);
    	}
    
    /*自底向上*/
    public static void sort(int[] a){
    		int N=a.length;
    		aux=new int[N];
    		for (int sz=1; sz<N; sz=sz+sz)
    			for (int lo=0; lo<N-sz; lo+=sz+sz)
    				merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-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);
    		sort(a, mid+1, hi);
    		merge(a, lo, mid, hi);
    	}
    
    /*归并*/
    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++];
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70]: /images/20220422/04204160acc64fbf9e3e547fb8f67831.png