經典算法3：分治法求解歸并排序

/分治法——歸并排序
  二路歸并排序的分治策略是：
（1）劃分：將待排序序列r1, r2, …, rn劃分為兩個長度相等的子序列r1, …, rn/2和rn/2＋1, …, rn；
（2）求解子問題：分別對這兩個子序列進行排序，得到兩個有序子序列；
（3）合并：將這兩個有序子序列合并成一個有序序列。
 */

    public class MergeSort {


    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        int a[] = { 21, 34, 56, 43, 99, 37, 78, 10 };// 這里對8個元素進行排序  
        int low = 0, high = 7;// 初始化low和high的值，即數組的起始和終止的坐標  
        // 輔助數組b，作為臨時數組  
        int b[] = new int[a.length];  
        //輸出排序前的數組  
        System.out.print("排序前：");  
        for (int i = 0; i <= high; i++) {  
            System.out.print(a[i] + " ");  
        }  
        // 歸并排序  
        mergerSort(a, low, high, b);  
        //輸出排序后的數組  
        System.out.print("排序后：");  
        for (int i = 0; i <= high; i++) {  
            System.out.print(a[i] + " ");  
        }  
    }  


    /** 
     * 分治和歸并 
     *  
     * @param a 
     * @param low 
     * @param high 
     * @param b 
     */  
    public static void mergerSort(int a[], int low, int high, int b[]) {  
        int mid = 0;  
        if (low < high) {  
            mid = (high + low) / 2;// 分治位置,即將數組拆分的位置  
            mergerSort(a, low, mid, b);  
            mergerSort(a, mid + 1, high, b);  
            merger(a, low, mid, high, b);// 歸并  
        }  
    }  


    /** 
     * 合并兩個有序子序列 
     *  
     * @param a 
     * @param low 
     * @param mid 
     * @param high 
     * @param b 
     *            輔助數組 
     */  
    public static void merger(int[] a, int low, int mid, int high, int b[]) {  


        int i = low;  
        int j = mid + 1;  
        int p = 0;  
        // 合并兩個有序數組 子序列1 a[low..mid] 子序列2 a[mid+1..high]  
        while (i <= mid && j <= high) {  
            b[p++] = (a[i] <= a[j]) ? a[i++] : a[j++];  
        }  
        // 如果子序列1沒有合并完則直接復制到復制數組中去  
        while (i <= mid) {  
            b[p++] = a[i++];  
        }  
        // 如果子序列2沒有合并完則直接復制到復制數組中去  
        while (j <= high) {  
            b[p++] = a[j++];  
        }  
        // 把輔助數組的元素復制到原來的數組中去  
        for (p = 0, i = low; i <= high; i++, p++) {  
            a[i] = b[p];  
        }  
    }  
}  </pre>