歸并排序MergeSort如何實(shí)現(xiàn)自頂向下與自底向上

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

歸并排序 MergeSort 是在計(jì)算機(jī)上實(shí)現(xiàn)的最早的算法之一， 由馮·諾伊曼 John von Neumann 在 1945 年發(fā)表"101報(bào)告"時提出，后在 1951 年完成的 EDVAC 計(jì)算機(jī)上應(yīng)用了這一算法。

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

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

歸并過程

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

2. 使用兩個指針同時遍歷輔助數(shù)據(jù)中的兩部分?jǐn)?shù)據(jù)

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

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

5. 當(dāng)有一邊數(shù)據(jù)遍歷完成，直接剩下的那部分?jǐn)?shù)據(jù)拷貝到原始數(shù)組中

代碼實(shí)現(xiàn)

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++]; // 左邊耗盡，取右半邊數(shù)據(jù)
        else if (j > hi) a[k] = aux[i++]; // 右邊耗盡，取左半邊數(shù)據(jù)
        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

我們可以使用斷言來驗(yàn)證猜想，前面的代碼里我們使用 assert 來判定輸入?yún)?shù)是否如我們所預(yù)想的那樣已經(jīng)排好序

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

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

我們可以加上參數(shù)來控制異常的拋出，在部署代碼到生產(chǎn)環(huán)境時禁用斷言，而在本地或者測試環(huán)境啟用斷言來幫助我們調(diào)試程序，默認(rèn)是禁用的，我們需要手動開啟

java -ea MyApplication // 啟用斷言 enable
java -da MyApplication // 禁用斷言 disable （默認(rèn)設(shè)置）

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

歸并過程完成了，我們有兩種方式可以實(shí)現(xiàn)排序算法

自頂向下排序

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

我們只需要遞歸的將數(shù)據(jù)不斷分區(qū)合并就可以達(dá)到排序的效果了，代碼如下：

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);
    }
}

這里有個小細(xì)節(jié)，輔助數(shù)組 aux 是在入口的 sort() 方法中初始化的，而不是放在遞歸的方法里，因?yàn)榉旁谶f歸的方法里會產(chǎn)生很多額外的小數(shù)組，會導(dǎo)致內(nèi)存比較碎，不利于內(nèi)存的回收整理，而放在外面只需要初始化一個數(shù)組就可以了，如果你的歸并排序性能比較差一般都是因?yàn)檫@個引起的

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

自底向上排序

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

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

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));
    
}

性能分析

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

運(yùn)行效率

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

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

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

時間復(fù)雜度

歸并排序的時間復(fù)雜度為 O(NLgN)，因?yàn)槊看味紝?shù)組分為兩部分，然后進(jìn)行合并

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

空間復(fù)雜度

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

穩(wěn)定排序

歸并排序是穩(wěn)定排序，在排序時本來排在前面的元素不會在排序過程中調(diào)換到后面，所以是穩(wěn)定排序

排序最佳實(shí)踐

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

代碼實(shí)現(xiàn)

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);
}

擴(kuò)展

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

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

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