歸并排序 java 實現

實現思路

• 將序列每相鄰的兩個元素進行歸并，得到 n/2 個序列，每個序列包含兩個元素；
• 再將上述序列歸并，每個序列有4個元素
• 重復步驟2
• 最后一步是對兩個序列歸并，這兩個序列的總長度是原數組的長度

和快速排序比較

• 歸并排序需要額外的空間，空間復雜度是O（n），快速不需要額外空間
• 歸并是穩定的，快排不是穩定的
• 兩種排序其實有是有點分治法的味道，將排序拆成一個個小問題，把這些問題組合就得到了原問題的解。
• 快速是先將原數組分成兩大塊，一塊小于中間位置的值，一塊大于中間位置的值。再將每塊重復上述步驟，直到每塊的元素個數為1。是從大往小。
• 歸并是講每個單元素進行合并，再將含有2個元素的序列進行合并，重復上述步驟。是從小往大。

首先實現一個合并算法

代碼如下

 * 指定了位置，歸并數組
     * 
     * @param data
     *            數組
     * @param low
     *            起始位置
     * @param mid
     *            第一組的截止位置，第二組的起始為 mid+1
     * @param high
     *            總截止位置
     */
    private static void merge(Integer[] data, int low, int mid, int high) {
        if (mid < low || high < mid) {
            return;
        }

        // 調試輸出
        System.out.println("2Arrays:" + Arrays.toString(Arrays.copyOfRange(data, low, mid + 1))
                + Arrays.toString(Arrays.copyOfRange(data, mid + 1, high + 1)));

        // 構建一個數組，這是歸并排序的缺點，需要額外空間
        Integer[] temp = new Integer[high - low + 1];

        int l = low;
        int m = mid + 1;
        int i = 0;

        while (l <= mid && m <= high) {
            if (data[l] < data[m]) {
                temp[i++] = data[l++];
            } else {
                temp[i++] = data[m++];
            }
        }

        // 兩個序列最后肯定只剩下一個序列
        if (l <= mid) {
            while (l <= mid)
                temp[i++] = data[l++];
        }

        if (m <= high) {
            while (m <= high)
                temp[i++] = data[m++];
        }

        // 注意這兒 k 從 low 開始，而不是從0
        int k = low;
        for (int d : temp) {
            data[k++] = d;
        }

        System.out.println("Merged: " + Arrays.toString(Arrays.copyOfRange(data, low, high + 1)));

    }

一趟歸并

假設 每個有序表的長度為 range，數字一共有 length/range 個子序列：0~range-1；range ~ range*2-1；等等。
注意有3種情況：
- 有序表的個數為偶數且長度都為 range；
- 有序表的長度為奇數 （最后一個子續表輪空，不考慮）
- 有序表的長度為偶數，最后一個子序列的長度小于 range

    /** * 本函數將數組按照以 range 長的小段進行歸并 * 數組一共被分為 data.length/range 個小段 * 兩兩小段歸并 會有3種情況： * 1.數組正常被分為偶數個小段 * 2. 數組被分為奇數個小段，最后一個輪空 * 3. 數組被分為偶數個小段，最后一段不完整 * * @param data * 數組，下標從0開始 * @param length */
    private static void mergePass(Integer[] data, int range) {

        int i = 0;
        // 從前往后遍歷，把相等的單元歸并
        while (i + 2 * range - 1 < data.length - 1) {
            merge(data, i, i + range - 1, i + 2 * range - 1);
            i = i + 2 * range; // 設置 i 新的位置
        }

        // 這種情況也是有 偶數個小單元，但最后兩個小單元一個長一個短
        if (i + range - 1 < data.length - 1) {
            merge(data, i, i + range - 1, data.length - 1);
        }

        // 如果說單元個數為奇數，那么最后一個就沒必要歸并

        // 最后肯定只剩下兩個單元？保證有序？

    }

二路歸并排序

    /** * 二路歸并排序 * @param data 待排序的數組 */
    private static void mergeSort(Integer[] data) {

        //len 每次增大一倍
        int len = 1;
        while (len < data.length) {
            mergePass(data, len);
            len *= 2;

        }

    }

這兒是對上面一趟歸并的反復調用，不過每次調用 range 值都增大了一倍。range 最大是 range*2 大于等于 data.length 的時候。

測試程序

    public static void main(String[] args) {
        Random r = new Random();
        Integer[] data = new Integer[r.nextInt(10) + 8];

        for (int ii = 0; ii < 10; ii++) {
            for (int i = 0; i < data.length; i++) {
                data[i] = r.nextInt(30);
            }
            System.out.println("------------------------");
            System.out.println(Arrays.toString(data));

            mergeSort(data);

            System.out.println(Arrays.toString(data));
        }

輸出

------------------------
[8, 2, 4, 11, 9, 22, 23, 17, 1, 2, 25, 28, 15, 16, 9, 17]
2Arrays:[8][2]
Merged: [2, 8]
2Arrays:[4][11]
Merged: [4, 11]
2Arrays:[9][22]
Merged: [9, 22]
2Arrays:[23][17]
Merged: [17, 23]
2Arrays:[1][2]
Merged: [1, 2]
2Arrays:[25][28]
Merged: [25, 28]
2Arrays:[15][16]
Merged: [15, 16]
2Arrays:[9][17]
Merged: [9, 17]
2Arrays:[2, 8][4, 11]
Merged: [2, 4, 8, 11]
2Arrays:[9, 22][17, 23]
Merged: [9, 17, 22, 23]
2Arrays:[1, 2][25, 28]
Merged: [1, 2, 25, 28]
2Arrays:[15, 16][9, 17]
Merged: [9, 15, 16, 17]
2Arrays:[2, 4, 8, 11][9, 17, 22, 23]
Merged: [2, 4, 8, 9, 11, 17, 22, 23]
2Arrays:[1, 2, 25, 28][9, 15, 16, 17]
Merged: [1, 2, 9, 15, 16, 17, 25, 28]
2Arrays:[2, 4, 8, 9, 11, 17, 22, 23][1, 2, 9, 15, 16, 17, 25, 28]
Merged: [1, 2, 2, 4, 8, 9, 9, 11, 15, 16, 17, 17, 22, 23, 25, 28]
[1, 2, 2, 4, 8, 9, 9, 11, 15, 16, 17, 17, 22, 23, 25, 28] ------------------------

從上面的輸出可以看出歸并的過程。

參考文章

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm