歸并排序MergeSort如何實現自頂向下與自底向上

歸并排序MergeSort如何實現自頂向下與自底向上，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

歸并排序 MergeSort 是在計算機上實現的最早的算法之一， 由馮·諾伊曼 John von Neumann 在 1945 年發表"101報告"時提出，后在 1951 年完成的 EDVAC 計算機上應用了這一算法。

歸并排序是在歸并的基礎上將數組不斷劃分成子數組進行排序，從而使整個數組完全有序，該算法是采用了典型的分治法來解決問題，即先將問題分解成子問題，再對子問題的解進行合并從而得到整個問題的解。

歸并排序的核心思想就在于 并（merging），為了更好的理解歸并排序，我們先來了解一下原地歸并的概念

歸并過程

1. 新建一個原始數組的拷貝作為輔助數組

2. 使用兩個指針同時遍歷輔助數據中的兩部分數據

3. 將兩個指針指向的較小元素放置到原始數組中

4. 然后將較小元素的指針往后一位

5. 當有一邊數據遍歷完成，直接剩下的那部分數據拷貝到原始數組中

代碼實現

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    assert isSorted(a, lo, mid);
    assert isSorted(a, mid + 1, hi);
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) a[k] = aux[j++]; // 左邊耗盡，取右半邊數據
        else if (j > hi) a[k] = aux[i++]; // 右邊耗盡，取左半邊數據
        else if (less(aux[i], aux[j])) a[k] = aux[j++]; // 取較小值
        else a[k] = aux[i++];
    }
    assert isSorted(a, lo, hi);
}

public static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

public static boolean isSorted(Comparable[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
         if (less(a[i], a[i-1])) return false;
    }
    return true;
}

public static boolean isSorted(Comparable[] a) {
    return isSorted(a, 0, a.length - 1);
}

這里代碼用到了 assert，順便提一下

斷言 Assertions

我們可以使用斷言來驗證猜想，前面的代碼里我們使用 assert 來判定輸入參數是否如我們所預想的那樣已經排好序

1. 斷言可以幫助我們檢測邏輯上的 bug

2. 讓代碼可讀性更強?如果 assert 后面的條件語句不滿足，則會拋出異常

我們可以加上參數來控制異常的拋出，在部署代碼到生產環境時禁用斷言，而在本地或者測試環境啟用斷言來幫助我們調試程序，默認是禁用的，我們需要手動開啟

java -ea MyApplication // 啟用斷言 enable
java -da MyApplication // 禁用斷言 disable （默認設置）

如果使用 IDEA 的話在 Application 的 VM Options 中加上 -ea 就可以開啟了，不填默認是禁用的

歸并過程完成了，我們有兩種方式可以實現排序算法

自頂向下排序

將數組元素不斷二分，直到子數組元素只有一個，然后將兩個有序的數組向下合并，再將新的兩個有序的數組向下合并，直至整個數組有序

我們只需要遞歸的將數據不斷分區合并就可以達到排序的效果了，代碼如下：

public class MergeSort {
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
	/** 見前面歸并部分 */
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

這里有個小細節，輔助數組 aux 是在入口的 sort() 方法中初始化的，而不是放在遞歸的方法里，因為放在遞歸的方法里會產生很多額外的小數組，會導致內存比較碎，不利于內存的回收整理，而放在外面只需要初始化一個數組就可以了，如果你的歸并排序性能比較差一般都是因為這個引起的

歸并排序是典型的分治思想的實踐，將問題分解成子問題，各個擊破，然后將結果合并

自底向上排序

將數組中元素一個個歸并成兩兩有序的子數組，再歸并成 2 個，再歸并成 8 個直至數組完全有序

數組是按照長度進行劃分的，最后子數組的數量可能不滿足要求，不能超過數據最大長度，需要特殊處理一下

private static void sortByBottomUp(Comparable[] a) {
    int N = a.length;
    Comparable[] aux = new Comparable[N];
    for (int size = 1; size < N; size = size + size) 
        for (int lo = 0; lo < N - size; lo += size + size) 
            merge(a, aux, lo, lo + size + 1, Math.min(lo + size + size - 1, N - 1));
    
}

性能分析

歸并排序在數據量非常大的情況下性能是很好的，比插入排序快很多

運行效率

• 個人 PC： 10^8 次比較/秒

• 超級 PC：10^12 次比較/秒

所以一個好的算法可以強過超級 PC，簡而言之可以省錢

時間復雜度

歸并排序的時間復雜度為 O(NLgN)，因為每次都將數組分為兩部分，然后進行合并

C(N) ≤ C(?N / 2?) + C(?N/ 2?) + N = NLgN

// 證明過程

D (N) = 2 D (N/2) + N
D (N) / N = 2 D (N/2) / N + 1
= D (N/2) / (N/2) + 1
= D (N/4) / (N/4) + 1 + 1
= D (N/8) / (N/8) + 1 + 1 + 1
. . .
= D (N/N) / (N/N) + 1 + 1 + ... + 1
= lgN

D(N) = NLgN

空間復雜度

我們在排序時借助了一個與原數組空間相等的數組，所以空間復雜度為 O(N)

穩定排序

歸并排序是穩定排序，在排序時本來排在前面的元素不會在排序過程中調換到后面，所以是穩定排序

排序最佳實踐

歸并排序比較適合大數組，對于較小數組，使用插入排序性能比較好，我們在做排序時可以設置一個閾值，當大于這個值的時候我們就使用歸并排序，否則我們使用插入排序，這個閾值約為 7。 并且我們在合并前可以先進行檢測，如果已經是有序的，則可以直接 return 了

代碼實現

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo + CUTOFF - 1) {
        Insertion.sort(a, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort (a, aux, lo, mid);
    sort (a, aux, mid+1, hi);
    if (!less(a[mid+1], a[mid])) return; // 有序則直接 return
    merge(a, aux, lo, mid, hi);
}

擴展

Java 集合類中提供的排序方法 Collections.sort() 也是復合實現，在數據量小的時候使用插入排序，里面的閾值是 32，但是它實現的插入排序方法有優化過，是二分插入排序

感興趣的同學可以看看 Collections.sort() 方法的源碼，里面涉及到了各種不同的排序算法

關于歸并排序MergeSort如何實現自頂向下與自底向上問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。