/**
 * 歸并排序：里面是一個遞歸程序，深刻理解之。
 */
public class MergeSort {
 
    /**
     * 遞歸劃分數(shù)組
     *
     * @param arr
     * @param from
     * @param end
     * @param c
     *            void
     */
    public void partition(Integer[] arr, int from, int end) {
        // 劃分到數(shù)組只有一個元素時才不進行再劃分
        if (from < end) {
            // 從中間劃分成兩個數(shù)組
            int mid = (from + end) / 2;
            partition(arr, from, mid);
            partition(arr, mid + 1, end);
            // 合并劃分后的兩個數(shù)組
            merge(arr, from, end, mid);
        }
    }
 
    /**
     * 數(shù)組合并，合并過程中對兩部分數(shù)組進行排序 前后兩部分數(shù)組里是有序的
     *
     * @param arr
     * @param from
     * @param end
     * @param mid
     * @param c
     *            void
     */
    public void merge(Integer[] arr, int from, int end, int mid) {
        Integer[] tmpArr = new Integer[arr.length];
        int tmpArrIndex = 0;// 指向臨時數(shù)組
        int part1ArrIndex = from;// 指向第一部分數(shù)組
        int part2ArrIndex = mid + 1;// 指向第二部分數(shù)組
 
        // 由于兩部分數(shù)組里是有序的，所以每部分可以從第一個元素依次取到最后一個元素，再對兩部分
        // 取出的元素進行比較。只要某部分數(shù)組元素取完后，退出循環(huán)
        while ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) {
            // 從兩部分數(shù)組里各取一個進行比較，取最小一個并放入臨時數(shù)組中
            if (arr[part1ArrIndex] - arr[part2ArrIndex] < 0) {
                // 如果第一部分數(shù)組元素小，則將第一部分數(shù)組元素放入臨時數(shù)組中，并且臨時數(shù)組指針
                // tmpArrIndex下移一個以做好下次存儲位置準備，前部分數(shù)組指針part1ArrIndex
                // 也要下移一個以便下次取出下一個元素與后部分數(shù)組元素比較
                tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
            } else {
                // 如果第二部分數(shù)組元素小，則將第二部分數(shù)組元素放入臨時數(shù)組中
                tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
            }
        }
        // 由于退出循環(huán)后，兩部分數(shù)組中可能有一個數(shù)組元素還未處理完，所以需要額外的處理，當(dāng)然不可
        // 能兩部分數(shù)組都有未處理完的元素，所以下面兩個循環(huán)最多只有一個會執(zhí)行，并且都是大于已放入
        // 臨時數(shù)組中的元素
        while (part1ArrIndex <= mid) {
            tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
        }
        while (part2ArrIndex <= end) {
            tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
        }
 
        // 最后把臨時數(shù)組拷貝到源數(shù)組相同的位置
        System.arraycopy(tmpArr, 0, arr, from, end - from + 1);
    }
 
    /**
     * 測試
     *
     * @param args
     */
    public static void main(String[] args) {
        Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7, -1, 0, -5, -2 };
        MergeSort insertSort = new MergeSort();
        insertSort.partition(intgArr, 0, intgArr.length - 1);
        for (Integer a : intgArr) {
            System.out.print(a + " ");
        }
    }
}

標簽：

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