C++歸并排序

「歸并排序 merge sort」是一種基于分治策略的排序算法，包含圖 11-10 所示的“劃分”和“合并”階段。

1. 劃分階段：通過遞歸不斷地將數(shù)組從中點處分開，將長數(shù)組的排序問題轉(zhuǎn)換為短數(shù)組的排序問題。
2. 合并階段：當子數(shù)組長度為 1 時終止劃分，開始合并，持續(xù)地將左右兩個較短的有序數(shù)組合并為一個較長的有序數(shù)組，直至結(jié)束。

圖 11-10   歸并排序的劃分與合并階段

11.6.1   算法流程

如圖 11-11 所示，“劃分階段”從頂至底遞歸地將數(shù)組從中點切分為兩個子數(shù)組。

1. 計算數(shù)組中點 ?mid? ，遞歸劃分左子數(shù)組（區(qū)間 ?[left, mid]? ）和右子數(shù)組（區(qū)間 ?[mid + 1, right]? ）。
2. 遞歸執(zhí)行步驟 1. ，直至子數(shù)組區(qū)間長度為 1 時，終止遞歸劃分。

“合并階段”從底至頂?shù)貙⒆笞訑?shù)組和右子數(shù)組合并為一個有序數(shù)組。需要注意的是，從長度為 1 的子數(shù)組開始合并，合并階段中的每個子數(shù)組都是有序的。

圖 11-11   歸并排序步驟

觀察發(fā)現(xiàn)，歸并排序與二叉樹后序遍歷的遞歸順序是一致的。

• 后序遍歷：先遞歸左子樹，再遞歸右子樹，最后處理根節(jié)點。
• 歸并排序：先遞歸左子數(shù)組，再遞歸右子數(shù)組，最后處理合并。

merge_sort.cpp

/* 合并左子數(shù)組和右子數(shù)組 */
// 左子數(shù)組區(qū)間 [left, mid]
// 右子數(shù)組區(qū)間 [mid + 1, right]
void merge(vector<int> &nums, int left, int mid, int right) {
    // 初始化輔助數(shù)組
    vector<int> tmp(nums.begin() + left, nums.begin() + right + 1);
    // 左子數(shù)組的起始索引和結(jié)束索引
    int leftStart = left - left, leftEnd = mid - left;
    // 右子數(shù)組的起始索引和結(jié)束索引
    int rightStart = mid + 1 - left, rightEnd = right - left;
    // i, j 分別指向左子數(shù)組、右子數(shù)組的首元素
    int i = leftStart, j = rightStart;
    // 通過覆蓋原數(shù)組 nums 來合并左子數(shù)組和右子數(shù)組
    for (int k = left; k <= right; k++) {
        // 若“左子數(shù)組已全部合并完”，則選取右子數(shù)組元素，并且 j++
        if (i > leftEnd)
            nums[k] = tmp[j++];
        // 否則，若“右子數(shù)組已全部合并完”或“左子數(shù)組元素 <= 右子數(shù)組元素”，則選取左子數(shù)組元素，并且 i++
        else if (j > rightEnd || tmp[i] <= tmp[j])
            nums[k] = tmp[i++];
        // 否則，若“左右子數(shù)組都未全部合并完”且“左子數(shù)組元素 > 右子數(shù)組元素”，則選取右子數(shù)組元素，并且 j++
        else
            nums[k] = tmp[j++];
    }
}

/* 歸并排序 */
void mergeSort(vector<int> &nums, int left, int right) {
    // 終止條件
    if (left >= right)
        return; // 當子數(shù)組長度為 1 時終止遞歸
    // 劃分階段
    int mid = (left + right) / 2;    // 計算中點
    mergeSort(nums, left, mid);      // 遞歸左子數(shù)組
    mergeSort(nums, mid + 1, right); // 遞歸右子數(shù)組
    // 合并階段
    merge(nums, left, mid, right);
}

實現(xiàn)合并函數(shù) merge() 存在以下難點。

• 需要特別注意各個變量的含義。nums 的待合并區(qū)間為 [left, right] ，但由于 tmp 僅復制了 nums 該區(qū)間的元素，因此 tmp 對應區(qū)間為 [0, right - left] 。
• 在比較 tmp[i] 和 tmp[j] 的大小時，還需考慮子數(shù)組遍歷完成后的索引越界問題，即 i > leftEnd 和 j > rightEnd 的情況。索引越界的優(yōu)先級是最高的，如果左子數(shù)組已經(jīng)被合并完了，那么不需要繼續(xù)比較，直接合并右子數(shù)組元素即可。

算法特性

• 時間復雜度 O(nlog?n)、非自適應排序：劃分產(chǎn)生高度為 log?n 的遞歸樹，每層合并的總操作數(shù)量為 n ，因此總體時間復雜度為 O(nlog?n) 。
• 空間復雜度 O(n)、非原地排序：遞歸深度為 log?n ，使用 O(log?n) 大小的棧幀空間。合并操作需要借助輔助數(shù)組實現(xiàn)，使用 O(n) 大小的額外空間。
• 穩(wěn)定排序：在合并過程中，相等元素的次序保持不變。

鏈表排序 *

對于鏈表，歸并排序相較于其他排序算法具有顯著優(yōu)勢，可以將鏈表排序任務的空間復雜度優(yōu)化至 O(1) 。

• 劃分階段：可以通過使用“迭代”替代“遞歸”來實現(xiàn)鏈表劃分工作，從而省去遞歸使用的棧幀空間。
• 合并階段：在鏈表中，節(jié)點增刪操作僅需改變引用（指針）即可實現(xiàn)，因此合并階段（將兩個短有序鏈表合并為一個長有序鏈表）無須創(chuàng)建額外鏈表。

具體實現(xiàn)細節(jié)比較復雜，有興趣的同學可以查閱相關資料進行學習。