εc外部排序的實戰(zhàn)指南)
經(jīng)常有人問我分治和歸并到底是兩個東西還是一個東西。我的回答是它們是一對黃金搭檔。分治是方法論解決問題時把大任務(wù)拆成小任務(wù)再把小任務(wù)的結(jié)果匯總成大結(jié)果歸并是這場拆解之后最經(jīng)典的合并動作把兩個有序序列合成一個有序序列。如果你正在學(xué)算法或者刷題時被一堆“遞歸爆棧”“指針越界”折磨這篇文章就是寫給你看的。我會從分治的底層邏輯講起接著把歸并排序的代碼徹底拆透再順手解決幾個高頻經(jīng)典問題最后分享一些進階玩法和踩坑實錄。所有代碼用C寫牽扯到復(fù)雜度推導(dǎo)的地方我會算給你看。文章不會太長篇大論講廢話該給代碼給代碼該給經(jīng)驗給經(jīng)驗。1. 分治思想的底層邏輯不是簡單的“拆了再合”1.1 分治的核心三件套分治思想聽起來玄乎本質(zhì)上就三步分解、解決、合并。把原來規(guī)模為 n 的問題拆成若干個規(guī)模更小的同類子問題子問題繼續(xù)遞歸拆直到小到可以直接解決然后逐層返回把子問題的解合并成原問題的解。我習(xí)慣用一個生活例子來解釋。假設(shè)你要在一堆撲克牌里找出最大的那一張正常思路是拿著一張一張比O(n) 次比較就結(jié)束了。分治的思路是把這堆牌從中間分成兩堆分別找出兩堆各自的最大牌再比較這兩張誰更大。你可能會覺得這不是多此一舉嗎但注意當(dāng)“找出最大值”升級成“給整副牌排序”或者“統(tǒng)計多少對元素是逆序的”單次遍歷解決不了分治的價值就體現(xiàn)出來了。分治真正厲害的地方不在“拆”而在“合”。很多新手只把分治理解成遞歸 折半然后寫出來的代碼只是形式上的分治合并階段沒有任何信息利用那自然快不起來。歸并排序的合并階段利用了“兩個子數(shù)組已經(jīng)有序”這個已知條件才能在 O(n) 時間內(nèi)把兩個 n/2 規(guī)模的子數(shù)組合并成有序數(shù)組從而把整體復(fù)雜度做到 O(n log n)。1.2 為什么分治能跑得比暴力快這里不得不做一點簡單的復(fù)雜度推導(dǎo)。以歸并排序為例設(shè) T(n) 是排序 n 個元素所需時間遞歸地看T(n) 2T(n/2) O(n)意思是排序 n 個元素分解成兩個 n/2 規(guī)模的子問題各花 T(n/2)合并兩個有序數(shù)組要花 O(n)。展開這個遞推式每一層總的比較工作量都是 O(n)遞歸深度一共 log2(n) 層所以 T(n) O(n log n)。對比冒泡排序和插入排序的 O(n2)n 從 10 萬到 100 萬規(guī)模時O(n log n) 和 O(n2) 的差距不是一倍兩倍而是千倍萬倍。你想想如果核心業(yè)務(wù)接口里有一段 O(n2) 的排序邏輯數(shù)據(jù)一漲接口就超時換成歸并或快排瓶頸往往立刻消失。主定理把這些規(guī)律總結(jié)成了公式。形如 T(n) aT(n/b) O(n^d) 的遞推式滿足條件時復(fù)雜度可以直接查表得出。分治算法的場景非常多歸并排序、快速排序、最近點對、快速冪、歸并求逆序?qū)诵亩际沁@套“分解-解決-合并”的思路。我踩過的一個坑是分治的子問題必須互相獨立合并代價必須可控。如果子問題之間有大量重疊強行分治只會浪費遞歸開銷這時候應(yīng)該用動態(tài)規(guī)劃或記憶化搜索。反過來如果合并操作本身就需要 O(n2)那整體復(fù)雜度還會被合并拖累分治的收益也會被抵消。2. 歸并排序最標(biāo)準(zhǔn)的分治實戰(zhàn)2.1 核心代碼逐行拆解歸并排序是分治思想最樸素的實現(xiàn)。我先把完整代碼貼出來再逐段講為什么這樣寫。#include bits/stdc.h using namespace std; void merge(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; // 左半部分起點 int j mid 1; // 右半部分起點 int k left; // 臨時數(shù)組寫入位置 // 雙指針掃描誰小誰先進臨時數(shù)組 while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 左邊有剩余直接拷過去 while (i mid) { temp[k] arr[i]; } // 右邊有剩余直接拷過去 while (j right) { temp[k] arr[j]; } // 把合并結(jié)果復(fù)制回原數(shù)組 for (int idx left; idx right; idx) { arr[idx] temp[idx]; } } void mergeSort(vectorint arr, int left, int right, vectorint temp) { if (left right) { return; // 單個元素已經(jīng)有序 } int mid left ((right - left) 1); // 防溢出寫法 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); }遞歸的邊界是left right。當(dāng)區(qū)間里只有一個元素或沒有元素時它天然有序不需要繼續(xù)拆。mid的計算我特意用了left ((right - left) 1)而不是(left right) 1主要防止 left 和 right 都很大時整數(shù)溢出。雖然刷題時數(shù)據(jù)范圍可能到不了那個量級但好習(xí)慣要養(yǎng)起來。合并函數(shù)的核心是兩個指針 i 和 j分別指向左右兩個子數(shù)組的當(dāng)前元素。誰小就先把誰放進臨時數(shù)組然后對應(yīng)指針往后走。這個“雙指針歸并”的手法值得背下來后面求逆序?qū)?、求小和問題全都還會用到它。2.2 穩(wěn)定性與空間占用歸并排序是穩(wěn)定的排序算法這一點和快速排序不一樣。代碼里我用的是if (arr[i] arr[j])當(dāng)左右兩個元素相等時優(yōu)先取左半邊的元素放進臨時數(shù)組。因為左半邊的元素在原數(shù)組中本來就出現(xiàn)在右半邊之前這樣做保證了相等元素的相對順序不變。空間占用方面合并時需要一塊長度等于當(dāng)前區(qū)間的臨時數(shù)組。我是在函數(shù)外預(yù)先分配好一整塊temp長度和原數(shù)組一樣每次合并都復(fù)用這塊空間。這樣做的原因是如果每次遞歸都在函數(shù)內(nèi)部新建臨時數(shù)組總的空間開銷會變成 O(n log n)而且頻繁分配內(nèi)存帶來的常數(shù)時間非?？捎^。實測下來大數(shù)據(jù)量下每次分配臨時數(shù)組的版本可能慢上三四倍。時間上歸并排序的 O(n log n) 是穩(wěn)定可預(yù)期的不依賴輸入數(shù)據(jù)的初始狀態(tài)。這一點比快排更讓人安心快排在極端情況下會退化到 O(n2)而歸并永遠不會。2.3 歸并排序的應(yīng)用邊界歸并排序有一個優(yōu)勢場景常常被忽略鏈表排序。數(shù)組版的歸并需要額外臨時數(shù)組但鏈表版的歸并不需要額外空間只要改指針就能完成合并空間復(fù)雜度直接降到 O(1)。LeetCode 上一堆鏈表排序題用歸并幾乎是常規(guī)解法。數(shù)組場景里如果數(shù)據(jù)量不大、對穩(wěn)定性沒有特殊要求大多數(shù)時候直接用內(nèi)置 sort快排 插入排序混合就夠了常數(shù)小、代碼簡單。但一旦遇到“不僅排序還需要在排序過程中統(tǒng)計信息”的問題比如逆序?qū)?、小和問題歸并排序就是唯一能同時完成排序和統(tǒng)計的選擇。這類問題我在下一節(jié)詳細展開。3. 分治經(jīng)典問題進階從排序到統(tǒng)計3.1 分治法求最大元素位置先看一個很多人刷題時遇到的第一關(guān)分治法求一個 n 元素數(shù)組中最大元素的位置。很多在線實驗平臺把這道題放在“分治”第一關(guān)因為它邏輯簡單、結(jié)構(gòu)清晰。int getMaxIndex(vectorint arr, int left, int right) { if (left right) { return left; // 只剩一個元素它自己就是最大值 } int mid left ((right - left) 1); int leftMaxIdx getMaxIndex(arr, left, mid); int rightMaxIdx getMaxIndex(arr, mid 1, right); // 合并比較左右兩個最大值返回較大的下標(biāo) if (arr[leftMaxIdx] arr[rightMaxIdx]) { return leftMaxIdx; } return rightMaxIdx; }注意幾點。第一題目要求返回位置所以我返回的是下標(biāo)不是值。第二多個最大值同時存在時我用了保證返回的是“第一個”最大元素的位置這是很多題目隱含的細節(jié)要求。第三這個算法的時間復(fù)雜度是 O(n)因為每一層合并只做一次比較但遞歸壓棧的深度是 O(log n)也算順帶復(fù)習(xí)了遞歸。有一點我必須說清楚真正在工程環(huán)境中找最大值位置線性掃描就夠了幾行代碼搞定int maxPos 0; for (int i 1; i n; i) { if (arr[i] arr[maxPos]) maxPos i; }分治版的意義在于教學(xué)。它能幫你熟練“把大區(qū)間拆成兩個小子區(qū)間再合并子區(qū)間結(jié)果”的模式為后面更復(fù)雜的分治問題打基礎(chǔ)。別把精力浪費在糾結(jié)“為什么不用遍歷”上把分治模板練熟才是正事。3.2 逆序?qū)τ嫈?shù)逆序?qū)Χx很簡單i j 時若 a[i] a[j]這倆元素構(gòu)成一個逆序?qū)?。暴力算法兩兩比較O(n2)數(shù)據(jù)量一上萬就卡死。歸并排序版的解法時間復(fù)雜度 O(n log n)原理非常巧妙。核心思想藏在合并階段。假設(shè)當(dāng)前需要合并左數(shù)組 [left, mid] 和右數(shù)組 [mid1, right]兩邊各自已經(jīng)有序。當(dāng)右數(shù)組的指針 j 指向的元素比左數(shù)組指針 i 指向的元素小時說明 a[i..mid] 里所有元素都大于 a[j]因為左數(shù)組是有序的a[i] 已經(jīng)是左邊區(qū)間里最小的那個所以 a[j] 和左數(shù)組剩余元素一一構(gòu)成逆序?qū)δ嫘驅(qū)?shù)量直接累加mid - i 1。long long mergeCount(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long invCount 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // arr[j] 與 a[i..mid] 所有元素都構(gòu)成逆序?qū)?invCount (mid - i 1); temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } return invCount; } long long mergeSortCount(vectorint arr, int left, int right, vectorint temp) { if (left right) { return 0; } int mid left ((right - left) 1); long long count 0; count mergeSortCount(arr, left, mid, temp); count mergeSortCount(arr, mid 1, right, temp); count mergeCount(arr, left, mid, right, temp); return count; }這里有一個特別容易踩的坑逆序?qū)?shù)量要開long long不能開int。一個長度為 100000 的數(shù)組如果完全逆序排列逆序?qū)?shù)量是 n(n-1)/2大約 5 × 10^9早就超出 int 的最大值 2.1 × 10^9 了。我之前因為偷懶用 int 交題WA 了一次才反應(yīng)過來白白浪費十幾分鐘調(diào)試時間。3.3 小和問題小和問題和逆序?qū)κ峭惶啄０宓膬蓚€變體。定義是數(shù)組中每個元素左邊所有比它小的元素值之和累加所有元素就是小和。舉個例子數(shù)組 [1, 3, 5, 2, 4]3 左邊比它小的有 1貢獻 15 左邊比它小的有 1 和 3貢獻 42 左邊比它小的有 1貢獻 14 左邊比它小的有 1、3、2貢獻 6總和是 12。暴力解是 O(n2)。歸并解法的視角是反過來的與其統(tǒng)計每個元素左邊有哪些更小值不如統(tǒng)計每個值作為“更小值”時被多少個右側(cè)元素借用。合并時如果左數(shù)組當(dāng)前元素 a[i] 小于等于右數(shù)組當(dāng)前元素 a[j]說明 a[i] 比右數(shù)組從 j 到 right 的所有元素都小貢獻就是a[i] * (right - j 1)。long long mergeSmallSum(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long sum 0; while (i mid j right) { if (arr[i] arr[j]) { // arr[i] 小于右數(shù)組剩余元素累加貢獻 sum (long long)arr[i] * (right - j 1); temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } return sum; }乘法運算這里同樣要注意強制轉(zhuǎn)long long避免兩個 int 相乘溢出。這類歸并統(tǒng)計問題只要吃透了逆序?qū)δ翘住袄糜行蛐耘坑嬎恪钡乃悸坊究梢耘e一反三。4. 歸并的進階場景不止于排序4.1 多路歸并與外部排序歸并思想在最基礎(chǔ)的排序之外還有兩個經(jīng)典延伸場景多路歸并和外部排序。先看多路歸并。當(dāng)你有 k 個已經(jīng)有序的序列想合并成一個有序序列兩兩歸并需要做 k-1 次歸并。每次歸并比較兩個序列的頭部元素復(fù)雜度可以接受但當(dāng)序列數(shù)量很多時每輪尋找 k 個頭部中的最小值需要 k-1 次比較整體效率會下降。工程上的做法是用一個大小為 k 的堆來維護 k 個序列的當(dāng)前頭部元素每次彈出最小值所在序列的頭部然后從該序列補充下一個元素進堆。這樣每次取最小值的代價從 O(k) 降到 O(log k)。更進一步的數(shù)據(jù)結(jié)構(gòu)是敗者樹專門為多路歸并設(shè)計在磁盤外部排序的場景里已經(jīng)用了很多年。外部排序處理的是“內(nèi)存裝不下”的數(shù)據(jù)。假設(shè)內(nèi)存只能放下 100MB但待排序文件有 10GB。思路是把大文件切成若干小塊每塊在內(nèi)存內(nèi)排好序?qū)懗龀膳R時文件最后用多路歸并把這些有序臨時文件邊讀邊合合并結(jié)果直接寫到最終輸出文件。歸并排序在這里不只是算法題了它直接決定了數(shù)據(jù)庫排序、日志排序這些基礎(chǔ)功能的性能。我在實際項目里做過 GB 級日志文件的排序當(dāng)時就是用了這個套路把內(nèi)排序和外歸并拆開處理穩(wěn)得很。4.2 四邊形不等式優(yōu)化DP分治解法與二分解法歸并能在排序過程中順帶統(tǒng)計信息已經(jīng)屬于進階內(nèi)容但分治思想還能再往前走一步優(yōu)化動態(tài)規(guī)劃。熱搜里那個“四邊形不等式優(yōu)化 dp 分治解法 二分解法”是最容易讓初學(xué)者懵圈的一類題。先交代背景。有些 DP 的狀態(tài)轉(zhuǎn)移形如 dp[i] min(dp[j] cost(j, i))暴力枚舉所有 j 是 O(n2)。如果 cost 函數(shù)滿足四邊形不等式那么 DP 的最優(yōu)決策點會隨 i 單調(diào)遞增也就是“決策單調(diào)性”。這個性質(zhì)一起就能用分治在 O(n log n) 內(nèi)求解。分治解法的核心是遞歸求解某個區(qū)間 [l, r] 的 dp 值時同時傳入一個可能的決策點搜索區(qū)間 [optL, optR]每次枚舉決策點時只在這個區(qū)間里找。算出中點 mid 的最優(yōu)決策點 optMid 后遞歸求解左半?yún)^(qū)間時搜索區(qū)間收縮為 [optL, optMid]遞歸求解右半?yún)^(qū)間時搜索區(qū)間收縮為 [optMid, optR]。因為決策單調(diào)性保證了區(qū)間的收縮不會遺漏最優(yōu)解總的枚舉量被壓縮到 O(n log n)。二分解法的思路是另一條路。既然決策點隨 i 單調(diào)就可以逐個確定每個決策點“接管”的狀態(tài)區(qū)間。常見實現(xiàn)是維護一個單調(diào)?；螂p端隊列每個隊列元素保存“決策點 它作為最優(yōu)決策的狀態(tài)范圍”新決策點加入時用二分找到它接管范圍的邊界。整體復(fù)雜度同樣是 O(n log n)但編碼細節(jié)和分治解法差異很大。我個人的體會是如果比賽或面試中遇到這類題優(yōu)先考慮分治解法。原因很簡單分治解法的代碼模板和歸并排序的遞歸結(jié)構(gòu)相似思維負(fù)擔(dān)小邊界條件也更直觀。二分棧的寫法對邊界非常敏感我自己寫過幾次每逢“開區(qū)間閉區(qū)間”“最優(yōu)值相等時取哪個決策點”這些細節(jié)都會卡殼。你需要根據(jù)自己對哪種模板更熟悉來做選擇。5. 踩坑實錄分治代碼的邊界地獄5.1 遞歸邊界你寫對了嗎分治遞歸最常見的錯誤就是邊界處理。mergeSort里我用的邊界是if (left right) return;這個寫法做了兩件事區(qū)間里有一個元素時返回區(qū)間為空時也返回。有的寫法寫if (left right)當(dāng)調(diào)用方不小心傳入空區(qū)間就會死循環(huán)或越界。建議一律寫?zhàn)B成習(xí)慣。合并循環(huán)里的邊界同樣要小心。while (i mid j right)的兩端邊界都取等號因為兩個子數(shù)組的元素都要被掃描到不能漏掉最后一個?？截惢卦瓟?shù)組時循環(huán)也是for (int idx left; idx right; idx)從 left 到 right不是從 0 開始也不是到 n-1 結(jié)束。5.2 mid 計算的防溢出寫法mid left ((right - left) 1)這個寫法我是強烈推薦的。老寫法(left right) / 2在 left 和 right 都是 2^31 量級時可能溢出成負(fù)數(shù)結(jié)果完全錯誤。雖然普通刷題數(shù)據(jù)一般不會觸發(fā)但工程代碼里數(shù)組索引完全可能很大一次溢出就是隱蔽的 bug調(diào)試成本極高。新寫法把減法優(yōu)先算了永遠不會溢出。還有一個小細節(jié)右移一位需要加括號因為運算符優(yōu)先級里右移低于加減法。寫成left (right - left) 1會變成(left right - left) 1實際等于right 1直接整段邏輯錯亂。5.3 臨時數(shù)組的復(fù)用與性能我見過很多初學(xué)者喜歡在 merge 函數(shù)內(nèi)部寫vectorint temp(right - left 1);邏輯沒錯但性能很差。每次合并都觸發(fā)一次內(nèi)存分配遞歸的每一層都會做很多次分配總分配次數(shù)是 O(n) 級別而內(nèi)存分配本身是個昂貴操作。正確的做法是在mergeSort外層初始化一整個temp長度等于原數(shù)組長度然后遞歸過程中所有區(qū)間合并共用這塊空間。因為合并操作是串行的同一個位置不會同時被兩個合并使用安全得很。實測對 100 萬元素的數(shù)組排序復(fù)用臨時數(shù)組的版本比每次新建的版本快一倍以上這個優(yōu)化是白賺的。5.4 相等元素順序與穩(wěn)定性歸并合并時if (arr[i] arr[j])決定了穩(wěn)定性。寫成會變成不穩(wěn)定排序雖然對純數(shù)值排序結(jié)果沒影響但如果你排序的是一個對象數(shù)組按某個字段排序穩(wěn)定性和不穩(wěn)定性的結(jié)果可能完全不同。舉個例子先按時間排序再按優(yōu)先級排序穩(wěn)定排序能讓相同優(yōu)先級的元素保留原時間順序不穩(wěn)定排序則可能打亂。我在實際開發(fā)中確實遇到過一次這個需求。按訂單創(chuàng)建時間排好序后需要再按用戶等級分組排序同時保留組內(nèi)的時間順序。如果手寫的歸并排序用的是分組后時間順序就亂了排查半天才發(fā)現(xiàn)是穩(wěn)定性寫錯了。5.5 數(shù)據(jù)溢出的隱蔽炸彈歸并的統(tǒng)計類問題里溢出的坑集中出現(xiàn)在兩個地方逆序?qū)?shù)量和小和累加值。逆序?qū)?shù)量最大是 n(n-1)/2n10^5 時就達到約 5 × 10^9必須用long long。小和問題的累加值更夸張如果一個元素值是 10^9它在最壞情況下可能被累加 n 次總和的量級是 10^14連 int 的一個零頭都裝不下。不僅變量類型要注意乘法的中間結(jié)果也要轉(zhuǎn)類型。arr[i] * (right - j 1)如果兩個操作數(shù)都是 int乘法結(jié)果直接溢出賦值給 long long 也救不回來。正確寫法是(long long)arr[i] * (right - j 1)先把一邊轉(zhuǎn)成 long long整個表達式自動提升為 long long 運算。我在實際解題中多次因為這些問題返工。分治本身不難難的是各種邊界和類型細節(jié)。寫完代碼后一定自己構(gòu)造幾組數(shù)據(jù)測一下空數(shù)組、單元素、全部相等、完全逆序、完全有序。這些邊界案例跑一遍比你在編譯器里反復(fù)看代碼管用得多。最后再分享一個小技巧調(diào)試分治代碼時最好加一個打印函數(shù)把每層遞歸處理的區(qū)間 [left, mid, right] 和合并后的數(shù)組打印出來。這樣你能直觀看到遞歸是否按預(yù)期拆解合并是否真的有序。我過去調(diào)試歸并二進制轉(zhuǎn)儲數(shù)據(jù)時靠這個手段十分鐘就定位到了問題省去了兩小時的懷疑人生。 分治與歸并：從歸并排序到逆序?qū)εc外部排序的實戰(zhàn)指南
經(jīng)常有人問我分治和歸并到底是兩個東西還是一個東西。我的回答是它們是一對黃金搭檔。分治是方法論解決問題時把大任務(wù)拆成小任務(wù)再把小任務(wù)的結(jié)果匯總成大結(jié)果歸并是這場拆解之后最經(jīng)典的合并動作把兩個有序序列合成一個有序序列。如果你正在學(xué)算法或者刷題時被一堆“遞歸爆棧”“指針越界”折磨這篇文章就是寫給你看的。我會從分治的底層邏輯講起接著把歸并排序的代碼徹底拆透再順手解決幾個高頻經(jīng)典問題最后分享一些進階玩法和踩坑實錄。所有代碼用C寫牽扯到復(fù)雜度推導(dǎo)的地方我會算給你看。文章不會太長篇大論講廢話該給代碼給代碼該給經(jīng)驗給經(jīng)驗。1. 分治思想的底層邏輯不是簡單的“拆了再合”1.1 分治的核心三件套分治思想聽起來玄乎本質(zhì)上就三步分解、解決、合并。把原來規(guī)模為 n 的問題拆成若干個規(guī)模更小的同類子問題子問題繼續(xù)遞歸拆直到小到可以直接解決然后逐層返回把子問題的解合并成原問題的解。我習(xí)慣用一個生活例子來解釋。假設(shè)你要在一堆撲克牌里找出最大的那一張正常思路是拿著一張一張比O(n) 次比較就結(jié)束了。分治的思路是把這堆牌從中間分成兩堆分別找出兩堆各自的最大牌再比較這兩張誰更大。你可能會覺得這不是多此一舉嗎但注意當(dāng)“找出最大值”升級成“給整副牌排序”或者“統(tǒng)計多少對元素是逆序的”單次遍歷解決不了分治的價值就體現(xiàn)出來了。分治真正厲害的地方不在“拆”而在“合”。很多新手只把分治理解成遞歸 折半然后寫出來的代碼只是形式上的分治合并階段沒有任何信息利用那自然快不起來。歸并排序的合并階段利用了“兩個子數(shù)組已經(jīng)有序”這個已知條件才能在 O(n) 時間內(nèi)把兩個 n/2 規(guī)模的子數(shù)組合并成有序數(shù)組從而把整體復(fù)雜度做到 O(n log n)。1.2 為什么分治能跑得比暴力快這里不得不做一點簡單的復(fù)雜度推導(dǎo)。以歸并排序為例設(shè) T(n) 是排序 n 個元素所需時間遞歸地看T(n) 2T(n/2) O(n)意思是排序 n 個元素分解成兩個 n/2 規(guī)模的子問題各花 T(n/2)合并兩個有序數(shù)組要花 O(n)。展開這個遞推式每一層總的比較工作量都是 O(n)遞歸深度一共 log2(n) 層所以 T(n) O(n log n)。對比冒泡排序和插入排序的 O(n2)n 從 10 萬到 100 萬規(guī)模時O(n log n) 和 O(n2) 的差距不是一倍兩倍而是千倍萬倍。你想想如果核心業(yè)務(wù)接口里有一段 O(n2) 的排序邏輯數(shù)據(jù)一漲接口就超時換成歸并或快排瓶頸往往立刻消失。主定理把這些規(guī)律總結(jié)成了公式。形如 T(n) aT(n/b) O(n^d) 的遞推式滿足條件時復(fù)雜度可以直接查表得出。分治算法的場景非常多歸并排序、快速排序、最近點對、快速冪、歸并求逆序?qū)诵亩际沁@套“分解-解決-合并”的思路。我踩過的一個坑是分治的子問題必須互相獨立合并代價必須可控。如果子問題之間有大量重疊強行分治只會浪費遞歸開銷這時候應(yīng)該用動態(tài)規(guī)劃或記憶化搜索。反過來如果合并操作本身就需要 O(n2)那整體復(fù)雜度還會被合并拖累分治的收益也會被抵消。2. 歸并排序最標(biāo)準(zhǔn)的分治實戰(zhàn)2.1 核心代碼逐行拆解歸并排序是分治思想最樸素的實現(xiàn)。我先把完整代碼貼出來再逐段講為什么這樣寫。#include bits/stdc.h using namespace std; void merge(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; // 左半部分起點 int j mid 1; // 右半部分起點 int k left; // 臨時數(shù)組寫入位置 // 雙指針掃描誰小誰先進臨時數(shù)組 while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 左邊有剩余直接拷過去 while (i mid) { temp[k] arr[i]; } // 右邊有剩余直接拷過去 while (j right) { temp[k] arr[j]; } // 把合并結(jié)果復(fù)制回原數(shù)組 for (int idx left; idx right; idx) { arr[idx] temp[idx]; } } void mergeSort(vectorint arr, int left, int right, vectorint temp) { if (left right) { return; // 單個元素已經(jīng)有序 } int mid left ((right - left) 1); // 防溢出寫法 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); }遞歸的邊界是left right。當(dāng)區(qū)間里只有一個元素或沒有元素時它天然有序不需要繼續(xù)拆。mid的計算我特意用了left ((right - left) 1)而不是(left right) 1主要防止 left 和 right 都很大時整數(shù)溢出。雖然刷題時數(shù)據(jù)范圍可能到不了那個量級但好習(xí)慣要養(yǎng)起來。合并函數(shù)的核心是兩個指針 i 和 j分別指向左右兩個子數(shù)組的當(dāng)前元素。誰小就先把誰放進臨時數(shù)組然后對應(yīng)指針往后走。這個“雙指針歸并”的手法值得背下來后面求逆序?qū)?、求小和問題全都還會用到它。2.2 穩(wěn)定性與空間占用歸并排序是穩(wěn)定的排序算法這一點和快速排序不一樣。代碼里我用的是if (arr[i] arr[j])當(dāng)左右兩個元素相等時優(yōu)先取左半邊的元素放進臨時數(shù)組。因為左半邊的元素在原數(shù)組中本來就出現(xiàn)在右半邊之前這樣做保證了相等元素的相對順序不變。空間占用方面合并時需要一塊長度等于當(dāng)前區(qū)間的臨時數(shù)組。我是在函數(shù)外預(yù)先分配好一整塊temp長度和原數(shù)組一樣每次合并都復(fù)用這塊空間。這樣做的原因是如果每次遞歸都在函數(shù)內(nèi)部新建臨時數(shù)組總的空間開銷會變成 O(n log n)而且頻繁分配內(nèi)存帶來的常數(shù)時間非?？捎^。實測下來大數(shù)據(jù)量下每次分配臨時數(shù)組的版本可能慢上三四倍。時間上歸并排序的 O(n log n) 是穩(wěn)定可預(yù)期的不依賴輸入數(shù)據(jù)的初始狀態(tài)。這一點比快排更讓人安心快排在極端情況下會退化到 O(n2)而歸并永遠不會。2.3 歸并排序的應(yīng)用邊界歸并排序有一個優(yōu)勢場景常常被忽略鏈表排序。數(shù)組版的歸并需要額外臨時數(shù)組但鏈表版的歸并不需要額外空間只要改指針就能完成合并空間復(fù)雜度直接降到 O(1)。LeetCode 上一堆鏈表排序題用歸并幾乎是常規(guī)解法。數(shù)組場景里如果數(shù)據(jù)量不大、對穩(wěn)定性沒有特殊要求大多數(shù)時候直接用內(nèi)置 sort快排 插入排序混合就夠了常數(shù)小、代碼簡單。但一旦遇到“不僅排序還需要在排序過程中統(tǒng)計信息”的問題比如逆序?qū)?、小和問題歸并排序就是唯一能同時完成排序和統(tǒng)計的選擇。這類問題我在下一節(jié)詳細展開。3. 分治經(jīng)典問題進階從排序到統(tǒng)計3.1 分治法求最大元素位置先看一個很多人刷題時遇到的第一關(guān)分治法求一個 n 元素數(shù)組中最大元素的位置。很多在線實驗平臺把這道題放在“分治”第一關(guān)因為它邏輯簡單、結(jié)構(gòu)清晰。int getMaxIndex(vectorint arr, int left, int right) { if (left right) { return left; // 只剩一個元素它自己就是最大值 } int mid left ((right - left) 1); int leftMaxIdx getMaxIndex(arr, left, mid); int rightMaxIdx getMaxIndex(arr, mid 1, right); // 合并比較左右兩個最大值返回較大的下標(biāo) if (arr[leftMaxIdx] arr[rightMaxIdx]) { return leftMaxIdx; } return rightMaxIdx; }注意幾點。第一題目要求返回位置所以我返回的是下標(biāo)不是值。第二多個最大值同時存在時我用了保證返回的是“第一個”最大元素的位置這是很多題目隱含的細節(jié)要求。第三這個算法的時間復(fù)雜度是 O(n)因為每一層合并只做一次比較但遞歸壓棧的深度是 O(log n)也算順帶復(fù)習(xí)了遞歸。有一點我必須說清楚真正在工程環(huán)境中找最大值位置線性掃描就夠了幾行代碼搞定int maxPos 0; for (int i 1; i n; i) { if (arr[i] arr[maxPos]) maxPos i; }分治版的意義在于教學(xué)。它能幫你熟練“把大區(qū)間拆成兩個小子區(qū)間再合并子區(qū)間結(jié)果”的模式為后面更復(fù)雜的分治問題打基礎(chǔ)。別把精力浪費在糾結(jié)“為什么不用遍歷”上把分治模板練熟才是正事。3.2 逆序?qū)τ嫈?shù)逆序?qū)Χx很簡單i j 時若 a[i] a[j]這倆元素構(gòu)成一個逆序?qū)?。暴力算法兩兩比較O(n2)數(shù)據(jù)量一上萬就卡死。歸并排序版的解法時間復(fù)雜度 O(n log n)原理非常巧妙。核心思想藏在合并階段。假設(shè)當(dāng)前需要合并左數(shù)組 [left, mid] 和右數(shù)組 [mid1, right]兩邊各自已經(jīng)有序。當(dāng)右數(shù)組的指針 j 指向的元素比左數(shù)組指針 i 指向的元素小時說明 a[i..mid] 里所有元素都大于 a[j]因為左數(shù)組是有序的a[i] 已經(jīng)是左邊區(qū)間里最小的那個所以 a[j] 和左數(shù)組剩余元素一一構(gòu)成逆序?qū)δ嫘驅(qū)?shù)量直接累加mid - i 1。long long mergeCount(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long invCount 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // arr[j] 與 a[i..mid] 所有元素都構(gòu)成逆序?qū)?invCount (mid - i 1); temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } return invCount; } long long mergeSortCount(vectorint arr, int left, int right, vectorint temp) { if (left right) { return 0; } int mid left ((right - left) 1); long long count 0; count mergeSortCount(arr, left, mid, temp); count mergeSortCount(arr, mid 1, right, temp); count mergeCount(arr, left, mid, right, temp); return count; }這里有一個特別容易踩的坑逆序?qū)?shù)量要開long long不能開int。一個長度為 100000 的數(shù)組如果完全逆序排列逆序?qū)?shù)量是 n(n-1)/2大約 5 × 10^9早就超出 int 的最大值 2.1 × 10^9 了。我之前因為偷懶用 int 交題WA 了一次才反應(yīng)過來白白浪費十幾分鐘調(diào)試時間。3.3 小和問題小和問題和逆序?qū)κ峭惶啄０宓膬蓚€變體。定義是數(shù)組中每個元素左邊所有比它小的元素值之和累加所有元素就是小和。舉個例子數(shù)組 [1, 3, 5, 2, 4]3 左邊比它小的有 1貢獻 15 左邊比它小的有 1 和 3貢獻 42 左邊比它小的有 1貢獻 14 左邊比它小的有 1、3、2貢獻 6總和是 12。暴力解是 O(n2)。歸并解法的視角是反過來的與其統(tǒng)計每個元素左邊有哪些更小值不如統(tǒng)計每個值作為“更小值”時被多少個右側(cè)元素借用。合并時如果左數(shù)組當(dāng)前元素 a[i] 小于等于右數(shù)組當(dāng)前元素 a[j]說明 a[i] 比右數(shù)組從 j 到 right 的所有元素都小貢獻就是a[i] * (right - j 1)。long long mergeSmallSum(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long sum 0; while (i mid j right) { if (arr[i] arr[j]) { // arr[i] 小于右數(shù)組剩余元素累加貢獻 sum (long long)arr[i] * (right - j 1); temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } return sum; }乘法運算這里同樣要注意強制轉(zhuǎn)long long避免兩個 int 相乘溢出。這類歸并統(tǒng)計問題只要吃透了逆序?qū)δ翘住袄糜行蛐耘坑嬎恪钡乃悸坊究梢耘e一反三。4. 歸并的進階場景不止于排序4.1 多路歸并與外部排序歸并思想在最基礎(chǔ)的排序之外還有兩個經(jīng)典延伸場景多路歸并和外部排序。先看多路歸并。當(dāng)你有 k 個已經(jīng)有序的序列想合并成一個有序序列兩兩歸并需要做 k-1 次歸并。每次歸并比較兩個序列的頭部元素復(fù)雜度可以接受但當(dāng)序列數(shù)量很多時每輪尋找 k 個頭部中的最小值需要 k-1 次比較整體效率會下降。工程上的做法是用一個大小為 k 的堆來維護 k 個序列的當(dāng)前頭部元素每次彈出最小值所在序列的頭部然后從該序列補充下一個元素進堆。這樣每次取最小值的代價從 O(k) 降到 O(log k)。更進一步的數(shù)據(jù)結(jié)構(gòu)是敗者樹專門為多路歸并設(shè)計在磁盤外部排序的場景里已經(jīng)用了很多年。外部排序處理的是“內(nèi)存裝不下”的數(shù)據(jù)。假設(shè)內(nèi)存只能放下 100MB但待排序文件有 10GB。思路是把大文件切成若干小塊每塊在內(nèi)存內(nèi)排好序?qū)懗龀膳R時文件最后用多路歸并把這些有序臨時文件邊讀邊合合并結(jié)果直接寫到最終輸出文件。歸并排序在這里不只是算法題了它直接決定了數(shù)據(jù)庫排序、日志排序這些基礎(chǔ)功能的性能。我在實際項目里做過 GB 級日志文件的排序當(dāng)時就是用了這個套路把內(nèi)排序和外歸并拆開處理穩(wěn)得很。4.2 四邊形不等式優(yōu)化DP分治解法與二分解法歸并能在排序過程中順帶統(tǒng)計信息已經(jīng)屬于進階內(nèi)容但分治思想還能再往前走一步優(yōu)化動態(tài)規(guī)劃。熱搜里那個“四邊形不等式優(yōu)化 dp 分治解法 二分解法”是最容易讓初學(xué)者懵圈的一類題。先交代背景。有些 DP 的狀態(tài)轉(zhuǎn)移形如 dp[i] min(dp[j] cost(j, i))暴力枚舉所有 j 是 O(n2)。如果 cost 函數(shù)滿足四邊形不等式那么 DP 的最優(yōu)決策點會隨 i 單調(diào)遞增也就是“決策單調(diào)性”。這個性質(zhì)一起就能用分治在 O(n log n) 內(nèi)求解。分治解法的核心是遞歸求解某個區(qū)間 [l, r] 的 dp 值時同時傳入一個可能的決策點搜索區(qū)間 [optL, optR]每次枚舉決策點時只在這個區(qū)間里找。算出中點 mid 的最優(yōu)決策點 optMid 后遞歸求解左半?yún)^(qū)間時搜索區(qū)間收縮為 [optL, optMid]遞歸求解右半?yún)^(qū)間時搜索區(qū)間收縮為 [optMid, optR]。因為決策單調(diào)性保證了區(qū)間的收縮不會遺漏最優(yōu)解總的枚舉量被壓縮到 O(n log n)。二分解法的思路是另一條路。既然決策點隨 i 單調(diào)就可以逐個確定每個決策點“接管”的狀態(tài)區(qū)間。常見實現(xiàn)是維護一個單調(diào)?；螂p端隊列每個隊列元素保存“決策點 它作為最優(yōu)決策的狀態(tài)范圍”新決策點加入時用二分找到它接管范圍的邊界。整體復(fù)雜度同樣是 O(n log n)但編碼細節(jié)和分治解法差異很大。我個人的體會是如果比賽或面試中遇到這類題優(yōu)先考慮分治解法。原因很簡單分治解法的代碼模板和歸并排序的遞歸結(jié)構(gòu)相似思維負(fù)擔(dān)小邊界條件也更直觀。二分棧的寫法對邊界非常敏感我自己寫過幾次每逢“開區(qū)間閉區(qū)間”“最優(yōu)值相等時取哪個決策點”這些細節(jié)都會卡殼。你需要根據(jù)自己對哪種模板更熟悉來做選擇。5. 踩坑實錄分治代碼的邊界地獄5.1 遞歸邊界你寫對了嗎分治遞歸最常見的錯誤就是邊界處理。mergeSort里我用的邊界是if (left right) return;這個寫法做了兩件事區(qū)間里有一個元素時返回區(qū)間為空時也返回。有的寫法寫if (left right)當(dāng)調(diào)用方不小心傳入空區(qū)間就會死循環(huán)或越界。建議一律寫?zhàn)B成習(xí)慣。合并循環(huán)里的邊界同樣要小心。while (i mid j right)的兩端邊界都取等號因為兩個子數(shù)組的元素都要被掃描到不能漏掉最后一個?？截惢卦瓟?shù)組時循環(huán)也是for (int idx left; idx right; idx)從 left 到 right不是從 0 開始也不是到 n-1 結(jié)束。5.2 mid 計算的防溢出寫法mid left ((right - left) 1)這個寫法我是強烈推薦的。老寫法(left right) / 2在 left 和 right 都是 2^31 量級時可能溢出成負(fù)數(shù)結(jié)果完全錯誤。雖然普通刷題數(shù)據(jù)一般不會觸發(fā)但工程代碼里數(shù)組索引完全可能很大一次溢出就是隱蔽的 bug調(diào)試成本極高。新寫法把減法優(yōu)先算了永遠不會溢出。還有一個小細節(jié)右移一位需要加括號因為運算符優(yōu)先級里右移低于加減法。寫成left (right - left) 1會變成(left right - left) 1實際等于right 1直接整段邏輯錯亂。5.3 臨時數(shù)組的復(fù)用與性能我見過很多初學(xué)者喜歡在 merge 函數(shù)內(nèi)部寫vectorint temp(right - left 1);邏輯沒錯但性能很差。每次合并都觸發(fā)一次內(nèi)存分配遞歸的每一層都會做很多次分配總分配次數(shù)是 O(n) 級別而內(nèi)存分配本身是個昂貴操作。正確的做法是在mergeSort外層初始化一整個temp長度等于原數(shù)組長度然后遞歸過程中所有區(qū)間合并共用這塊空間。因為合并操作是串行的同一個位置不會同時被兩個合并使用安全得很。實測對 100 萬元素的數(shù)組排序復(fù)用臨時數(shù)組的版本比每次新建的版本快一倍以上這個優(yōu)化是白賺的。5.4 相等元素順序與穩(wěn)定性歸并合并時if (arr[i] arr[j])決定了穩(wěn)定性。寫成會變成不穩(wěn)定排序雖然對純數(shù)值排序結(jié)果沒影響但如果你排序的是一個對象數(shù)組按某個字段排序穩(wěn)定性和不穩(wěn)定性的結(jié)果可能完全不同。舉個例子先按時間排序再按優(yōu)先級排序穩(wěn)定排序能讓相同優(yōu)先級的元素保留原時間順序不穩(wěn)定排序則可能打亂。我在實際開發(fā)中確實遇到過一次這個需求。按訂單創(chuàng)建時間排好序后需要再按用戶等級分組排序同時保留組內(nèi)的時間順序。如果手寫的歸并排序用的是分組后時間順序就亂了排查半天才發(fā)現(xiàn)是穩(wěn)定性寫錯了。5.5 數(shù)據(jù)溢出的隱蔽炸彈歸并的統(tǒng)計類問題里溢出的坑集中出現(xiàn)在兩個地方逆序?qū)?shù)量和小和累加值。逆序?qū)?shù)量最大是 n(n-1)/2n10^5 時就達到約 5 × 10^9必須用long long。小和問題的累加值更夸張如果一個元素值是 10^9它在最壞情況下可能被累加 n 次總和的量級是 10^14連 int 的一個零頭都裝不下。不僅變量類型要注意乘法的中間結(jié)果也要轉(zhuǎn)類型。arr[i] * (right - j 1)如果兩個操作數(shù)都是 int乘法結(jié)果直接溢出賦值給 long long 也救不回來。正確寫法是(long long)arr[i] * (right - j 1)先把一邊轉(zhuǎn)成 long long整個表達式自動提升為 long long 運算。我在實際解題中多次因為這些問題返工。分治本身不難難的是各種邊界和類型細節(jié)。寫完代碼后一定自己構(gòu)造幾組數(shù)據(jù)測一下空數(shù)組、單元素、全部相等、完全逆序、完全有序。這些邊界案例跑一遍比你在編譯器里反復(fù)看代碼管用得多。最后再分享一個小技巧調(diào)試分治代碼時最好加一個打印函數(shù)把每層遞歸處理的區(qū)間 [left, mid, right] 和合并后的數(shù)組打印出來。這樣你能直觀看到遞歸是否按預(yù)期拆解合并是否真的有序。我過去調(diào)試歸并二進制轉(zhuǎn)儲數(shù)據(jù)時靠這個手段十分鐘就定位到了問題省去了兩小時的懷疑人生。