分治——合并排序

- 日理万妓 2022-08-21 04:54 118阅读 0赞

分治思路：

1.  大问题分解为子问题
2.  子问题相互独立，可以直接解决
3.  将子问题合解，得到原问题的解

使用分治法进行数组排序。  
\* 将一个数列等分为两半，递归的进行排序，拆成两半，每一块都已经排好序了，但是并不代表这两块直接拼起来  
\* 不一定是整体有序的，还需要进一步操作————将两个有序集合通过while循环附设两个指针合并为一个有序的,  
\* 同样这就说明了需要再额外开一个数组进行辅助，也就说合并排序非就地排序。

注意：  
1.合并排序不是就地排序的，可是一开始我忽略了Java的另外一个语法，将辅助数组temp与原始数组nums指向了同一块内存空间（temp = nums = int \[n+10\])，所以出现了bug，无法正确排序。  
2.仿照Java的写法，排序区间是左闭右开的\[a,b)。所以程序在递归至只有一个元素时应返回，其对应的标志是a==b-1，所以递归的条件是a

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    
        public static final boolean DEBUG = true;
        public static int n;
        public static int[] nums,temp;
    
        public static void test(){
            if(DEBUG) System.out.println("breakpoint!");
        }
        public static void show(int x,int y){
            for(int i=x;i<y;i++) System.out.print(nums[i]+" ");
            System.out.println();
        }
        //区间[l,m)与区间[m，r)合并。
        public static void merge(int l,int m,int r){
            int i=l,j=m,k=l;
            while(i<m&&j<r){
                if(nums[i]<=nums[j]) temp[k++] = nums[i++];
                else temp[k++] = nums[j++];
            }
            while(i<m) temp[k++] = nums[i++];
            while(j<r) temp[k++] = nums[j++];
        }
        public static void mergeSort(int left,int right){
       //[left,right）
            if(left==right-1) return;
            if(left<right-1){
       //因为right取不到，所以如果left==right-1,只有一个元素，返回
                int mid = (left+right)/2;
                System.out.println("left part:");
                show(left, mid);
                System.out.println("right part:");
                show(mid, right);
                mergeSort(left, mid);//[left,mid)
                mergeSort(mid, right);//[mid,right)
                merge(left,mid,right);
                for(int i=left;i<right;i++) nums[i] = temp[i];
                System.out.println("After Merging:");
                show(left, right);
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                n = in.nextInt();
                //如果temp = nums则两者指向同一块内存空间
                nums = new int[n+10];
                temp = new int[n+10];
                for(int i=0;i<n;i++) nums[i] = in.nextInt();
                mergeSort(0, n);
                System.out.println("After sorted!");
                for(int i=0;i<n;i++) System.out.println(nums[i]);
            }
        }
    
    }

![这里写图片描述][20160316153004555]

对5个元素（9,8,7,6,5）进行排序，从运行结果可以看出：  
1. 分为两部分，left part : 9 , 8 ; right part : 7 , 6 , 5  
2. 对这两部分再递归排序。将1阶段的left part再分为两部分，left part : 9;  
right part : 8 。由于左右两边都只有一个元素了，向上回溯，合解，得到8，9。（注意：这里的递归过程相当于一棵二叉树的后序遍历。）  
3. 同样的，对1阶段的right part分为两部分，left part : 7 ; right part : 6 , 5。由于right part还有两个元素，继续分解递归，分为left part(son) : 6;  
right part(son) : 5。回溯，合解：5,6。接着再回溯，合解：5,6,7。左边子树和右边子树，回溯，合解到根：5,6,7,8,9  
3. 排序完成，打印输出：5,6,7,8,9

[20160316153004555]: /images/20220731/67f0117ab0004360a4ddf3047fdc9a1b.png