/*分治法——歸并排序
 * 二路歸并排序的分治策略是：
（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的值，即數(shù)組的起始和終止的坐標  
            // 輔助數(shù)組b，作為臨時數(shù)組  
            int b[] = new int[a.length];  
            //輸出排序前的數(shù)組  
            System.out.print("排序前：");  
            for (int i = 0; i <= high; i++) {  
                System.out.print(a[i] + " ");  
            }  
            // 歸并排序  
            mergerSort(a, low, high, b);  
            //輸出排序后的數(shù)組  
            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;// 分治位置,即將數(shù)組拆分的位置  
                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 
         *            輔助數(shù)組 
         */  
        public static void merger(int[] a, int low, int mid, int high, int b[]) {  
      
      
            int i = low;  
            int j = mid + 1;  
            int p = 0;  
            // 合并兩個有序數(shù)組 子序列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沒有合并完則直接復制到復制數(shù)組中去  
            while (i <= mid) {  
                b[p++] = a[i++];  
            }  
            // 如果子序列2沒有合并完則直接復制到復制數(shù)組中去  
            while (j <= high) {  
                b[p++] = a[j++];  
            }  
            // 把輔助數(shù)組的元素復制到原來的數(shù)組中去  
            for (p = 0, i = low; i <= high; i++, p++) {  
                a[i] = b[p];  
            }  
        }  
    }  

標簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。