一、是什么

歸并排序（Merge Sort）是建立歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法的一個非常典型的應用

將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序

例如對于含有?n?個記錄的無序表，首先默認表中每個記錄各為一個有序表（只不過表的長度都為 1）

然后進行兩兩合并，使?n?個有序表變?yōu)?code>n/2?個長度為 2 或者 1 的有序表（例如 4 個小有序表合并為 2 個大的有序表）

通過不斷地進行兩兩合并，直到得到一個長度為?n?的有序表為止

例如對無序表{49，38，65，97，76，13，27}進行歸并排序分成了分、合兩部分：

如下圖所示：

歸并合過程中，每次得到的新的子表本身有序，所以最終得到有序表

上述分成兩部分，則稱為二路歸并，如果分成三個部分則稱為三路歸并，以此類推

二、如何實現

關于歸并排序的算法思路如下：

• 分：把數組分成兩半，再遞歸對子數組進行分操作，直至到一個個單獨數字

• 合：把兩個數合成有序數組，再對有序數組進行合并操作，直到全部子數組合成一個完整的數組

  • 合并操作可以新建一個數組，用于存放排序后的數組
  • 比較兩個有序數組的頭部，較小者出隊并且推入到上述新建的數組中
  • 如果兩個數組還有值，則重復上述第二步
  • 如果只有一個數組有值，則將該數組的值出隊并推入到上述新建的數組中

?用代碼表示則如下圖所示：

function mergeSort(arr) {  // 采用自上而下的遞歸方法
    const len = arr.length;
    if(len < 2) {
        return arr;
    }
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    const result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

上述歸并分成了分、合兩部分，在處理分過程中遞歸調用兩個分的操作，所花費的時間為2乘T(n/2)，合的操作時間復雜度則為O(n)，因此可以得到以下公式：

總的執(zhí)行時間 = 2 × 輸入長度為n/2的sort函數的執(zhí)行時間 +?merge函數的執(zhí)行時間O(n)

當只有一個元素時，T(1) = O(1)

如果對T(n) = 2 * T(n/2) + O(n)進行左右 / n的操作，得到?T(n) / n = (n / 2) * T(n/2) + O(1)

現在令?S(n) = T(n)/n，則S(1) = O(1)，然后利用表達式帶入得到S(n) = S(n/2) + O(1)

所以可以得到：S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S(1) + O(logn) = O(logn)

綜上可得，T(n) = n * log(n) = nlogn

關于歸并排序的穩(wěn)定性，在進行合并過程，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也不會交換，由此可見歸并排序是穩(wěn)定的排序算法

三、應用場景

在外排序中通常使用排序-歸并的策略，外排序是指處理超過內存限度的數據的排序算法，通常將中間結果放在讀寫較慢的外存儲器，如下分成兩個階段：

• 排序階段：讀入能夠放進內存中的數據量，將其排序輸出到臨時文件，一次進行，將帶排序數據組織為多個有序的臨時文件
• 歸并階段：將這些臨時文件組合為大的有序文件

例如，使用100m內存對900m的數據進行排序，過程如下：

• 讀入100m數據內存，用常規(guī)方式排序
• 將排序后的數據寫入磁盤
• 重復前兩個步驟，得到9個100m的臨時文件
• 將100m的內存劃分為10份，將9份為輸入緩沖區(qū)，第10份為輸出緩沖區(qū)
• 進行九路歸并排序，將結果輸出到緩沖區(qū)
  • 若輸出緩沖區(qū)滿，將數據寫到目標文件，清空緩沖區(qū)
  • 若緩沖區(qū)空，讀入相應文件的下一份數據

參考文獻

• https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015
• https://chowdera.com/2021/09/20210920201630258d.html#_127
• https://juejin.cn/post/6844904007899561998

如果對您有所幫助，歡迎您點個關注，我會定時更新技術文檔，大家一起討論學習，一起進步。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-856726.html

到了這里，關于說說你對歸并排序的理解？如何實現？應用場景？的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！