C++歸并排序

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

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

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

11.6.1   算法流程

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

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

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

圖 11-11   歸并排序步驟

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

• 后序遍歷：先遞歸左子樹(shù)，再遞歸右子樹(shù)，最后處理根節(jié)點(diǎn)。
• 歸并排序：先遞歸左子數(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;
    // 通過(guò)覆蓋原數(shù)組 nums 來(lái)合并左子數(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; // 當(dāng)子數(shù)組長(zhǎng)度為 1 時(shí)終止遞歸
    // 劃分階段
    int mid = (left + right) / 2;    // 計(jì)算中點(diǎn)
    mergeSort(nums, left, mid);      // 遞歸左子數(shù)組
    mergeSort(nums, mid + 1, right); // 遞歸右子數(shù)組
    // 合并階段
    merge(nums, left, mid, right);
}

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

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

算法特性

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

鏈表排序 *

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

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

具體實(shí)現(xiàn)細(xì)節(jié)比較復(fù)雜，有興趣的同學(xué)可以查閱相關(guān)資料進(jìn)行學(xué)習(xí)。