Java 排序算法-歸并排序

算法思想

歸并排序（MergeSort）是将兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若幹個子序列，每個子序列是有序的。然後再把有序子序列合并為整體有序序列。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。 将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。

算法原理

歸并算法的示意圖（圖檔來自維基百科）

算法實作

使用遞歸的歸并排序

public class TestJava {

    private static int[] array = new int[]{, , , , , , , , , , , , , , , };

    public static void main(String[] args) {
        mergeSort(array, , array.length - );

        for (int k : array) {
            System.out.println("array:" + k);
        }
    }

    private static void mergeSort(int[] array, int left, int right) {

        if (left >= right) {
            return;
        }

        int middle = (left + right) / ;

        int[] A = new int[middle - left + ];
        int[] B = new int[right - middle];

        System.arraycopy(array, left, A, , A.length);
        System.arraycopy(array, middle + , B, , B.length);

        mergeSort(A, , A.length -);
        mergeSort(B, , B.length - );


        int i = ;
        int j = ;

        for (int index = left; index <= right; index++) {
            if (i < A.length && j < B.length) {
                array[index] = A[i] < B[j] ?  A[i ++] : B[j ++];
            } else if (i < A.length) {
                array[index] = A[i ++];
            } else if (j < B.length) {
                array[index] = B[j ++];
            }
        }
    }
}
           

歸并排序的優化（非遞歸歸并排序）

public class CustomMergeSort {

    private static int[] array = new int[]{, , , , , , , , , , , , , , , };

    public static void main(String[] args) {
        mergeSort();
        for (int i : array) {
            System.out.println(i);
        }
    }


    public static void mergeSort() {

        int len = array.length;

        int k = ;

        while (k < len) {
            mergePass(array, k, len);
            k *= ;
        }
    }


    private static void mergePass(int[] array, int k, int n) {
        int i = ;

        while (i < n -  * k + ) {
            merge(array, i , i +  * k - );
            i += * k;
        }

        if (i < n - k) {
            merge(array, i, n -);
        }
    }


    private static void merge(int[] array, int left, int right) {

        if (left >= right) {
            return;
        }

        int middle = (left + right) / ;

        int[] A = new int[middle - left + ];
        int[] B = new int[right - middle];

        System.arraycopy(array, left, A, , A.length);
        System.arraycopy(array, middle + , B, , B.length);



        int i = ;
        int j = ;

        for (int index = left; index <= right; index++) {
            if (i < A.length && j < B.length) {
                array[index] = A[i] < B[j] ?  A[i ++] : B[j ++];
            } else if (i < A.length) {
                array[index] = A[i ++];
            } else if (j < B.length) {
                array[index] = B[j ++];
            }
        }
    }
}
           

算法分析

（1）穩定性

　歸并排序是一種穩定的排序。

（2）存儲結構要求

　可用順序存儲結構。也易于在連結清單上實作。

（3）時間複雜度

　對長度為n的檔案，需進行 趟二路歸并，每趟歸并的時間為O(n)，故其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。

（4）空間複雜度

　 需要一個輔助向量來暫存兩有序子檔案歸并的結果，故其輔助空間複雜度為O(n)，顯然它不是就地排序。