分治——合并排序

分治思路：

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-) return;
        if(left<right-){//因為right取不到，是以如果left==right-1,隻有一個元素，傳回
            int mid = (left+right)/;
            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+];
            temp = new int[n+];
            for(int i=;i<n;i++) nums[i] = in.nextInt();
            mergeSort(, n);
            System.out.println("After sorted!");
            for(int i=;i<n;i++) System.out.println(nums[i]);
        }
    }

}
           

對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