歸并排序（Merge Sort）

一、概念

• 不斷地將當前序列平均分割成2個子序列，直到不能再分割。（序列中只剩1個元素）
• 不斷地將2個子序列合并成一個有序序列，直到最終只剩下1個有序序列。

image

二、divide（劃分）

• 遞歸調(diào)用，將數(shù)據(jù)遞歸劃分到最小，然后再合并。

public class MergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    /**
     * 對 [begin, end) 范圍的數(shù)據(jù)進行歸并排序
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }
}
復制代碼

三、merge（合并）

1、概念

• 兩個數(shù)組都有一個指向頭節(jié)點的指針。
• 比較兩個指針對應值的大小，將小的值取出，并將其指針向后移動一位。
• 黑色代表已填入的數(shù)據(jù)，黃色代表這一輪比較較小的值。

image

2、細節(jié)

• 需要merge的2組序列存在于同一個數(shù)組中，并且是挨在一起的。

image

• 如果我們將3和8比較的結果放入數(shù)組左側，那么8的值就會被覆蓋。
• 為了更好的完成merge操作，最好將其中一組序列備份出來，比如[begin, mid)
• 我們將左側數(shù)組復制一份出來，然后進行merge操作。

image

3、實例

• 黑色代表已填入的數(shù)據(jù)，黃色代表這一輪比較較小的值。

image

• 左邊先結束，右邊剩下的無需再排序，可結束排序。

image

• 右邊先結束，左邊剩下的可直接搬到右邊，結束排序。

image

4、代碼實現(xiàn)

public class MergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 將 [begin, mid) 和 [mid, end) 范圍的序列合并成一個有序序列
     */
    private void merge(int begin, int mid, int end) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;

        // 備份左邊數(shù)組
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + I];
        }

        // 如果左邊還沒有結束
        while (li < le) { 
            if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
                array[ai++] = array[ri++];
            } else {
                array[ai++] = leftArray[li++];
            }
        }
    }
}
復制代碼

• 由于歸并排序總是平均分割子序列，所以最好，最壞，平均時間復雜度都是O(nlogn)，屬于穩(wěn)定排序。
• 歸并排序的空間復雜度是O(n)。