歸并排序這個(gè)題目我在帶新人和做代碼評(píng)審時(shí)反復(fù)講過很多遍。它看起來只是“分而治之”四個(gè)字但真到動(dòng)手寫遞歸版的分裂邊界、非遞歸版的步長控制、合并時(shí)的臨時(shí)數(shù)組管理每一處都能讓人卡上半天。更現(xiàn)實(shí)的是很多人學(xué)完歸并排序回頭連冒泡和選擇都寫不利索面試時(shí)被要求手寫一個(gè)基礎(chǔ)排序反而慌了神。這篇內(nèi)容就是把這幾個(gè)排序放在一起講透歸并排序的遞歸與非遞歸兩套實(shí)現(xiàn)怎么落地、各自的坑在哪順帶把冒泡和選擇這兩個(gè)“看起來最簡(jiǎn)單”的排序講清楚它們真正的價(jià)值與局限。適合正在啃數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)的同學(xué)、準(zhǔn)備面試需要手寫排序的開發(fā)者以及想給團(tuán)隊(duì)做一次排序?qū)ｎ}分享的工程師參考。讀完你至少能做到不看資料寫出穩(wěn)定的歸并排序遞歸版理解非遞歸版為什么能省掉遞歸棧并且清楚什么場(chǎng)景下冒泡和選擇反而不該被嫌棄。1. 整體設(shè)計(jì)思路與方案選型拆解1.1 為什么把這三個(gè)排序放在一起講排序算法成百上千單獨(dú)拎出歸并、冒泡、選擇這三個(gè)不是隨意拼盤。它們恰好構(gòu)成了一條從“入門直覺”到“分治思維”的認(rèn)知階梯。冒泡和選擇是大多數(shù)人接觸的第一批算法邏輯直白到用生活場(chǎng)景就能解釋清楚而歸并排序則是第一次真正引入“分治”和“額外空間換效率”的思想。把三者放在一起能看清一個(gè)核心問題同樣是排序?yàn)槭裁从械乃惴ㄊ?O(n2)有的能壓到 O(n log n)差距到底出在哪個(gè)環(huán)節(jié)。從教學(xué)和實(shí)際使用的角度看冒泡排序的價(jià)值在于它極其適合用來理解“比較與交換”這個(gè)最基礎(chǔ)的操作模型以及“穩(wěn)定性”這個(gè)概念——冒泡是穩(wěn)定的選擇是不穩(wěn)定的這個(gè)差異在講歸并的穩(wěn)定性時(shí)能形成很好的對(duì)照。歸并排序則是穩(wěn)定排序里效率最高的一檔O(n log n) 的時(shí)間復(fù)雜度加上穩(wěn)定特性讓它在需要保持相等元素原始順序的場(chǎng)景里非常有用。三者串起來講讀者對(duì)“穩(wěn)定性”“時(shí)間復(fù)雜度”“空間換時(shí)間”這幾個(gè)概念的理解會(huì)立體得多。我在實(shí)際帶人時(shí)發(fā)現(xiàn)一個(gè)現(xiàn)象直接上歸并排序很多人能背出代碼但說不清為什么歸并是穩(wěn)定的而先講透冒泡的穩(wěn)定性來源相等時(shí)不交換再講歸并合并時(shí)“左邊先取”的規(guī)則穩(wěn)定性這個(gè)概念就落地了。所以這個(gè)組合不是湊數(shù)是有意為之的認(rèn)知路徑設(shè)計(jì)。1.2 遞歸版歸并的核心思路與選型理由歸并排序的本質(zhì)是“先分后合”。遞歸版的思路非常貼合這個(gè)描述把數(shù)組從中間劈成兩半分別對(duì)左右兩半遞歸排序最后把兩個(gè)有序的半?yún)^(qū)合并成一個(gè)有序整體。遞歸的終止條件是子數(shù)組長度小于等于 1此時(shí)天然有序。選擇遞歸實(shí)現(xiàn)作為第一套方案理由有三。第一遞歸的代碼結(jié)構(gòu)和“分治”的思維模型幾乎一一對(duì)應(yīng)可讀性極強(qiáng)讀者能直接從代碼看出算法在干什么。第二遞歸版把“分裂”這件事交給函數(shù)調(diào)用棧自動(dòng)管理不需要手動(dòng)計(jì)算區(qū)間邊界出錯(cuò)概率相對(duì)低。第三遞歸版是理解非遞歸版的基礎(chǔ)——非遞歸版本質(zhì)上就是把遞歸的“分裂順序”用循環(huán)手動(dòng)模擬出來先懂遞歸再懂非遞歸順序不能反。但遞歸版有個(gè)繞不開的問題遞歸深度是 log?n 級(jí)別雖然對(duì)絕大多數(shù)場(chǎng)景來說這個(gè)深度完全可接受一百萬數(shù)據(jù)也就二十層左右但在極端受限的嵌入式環(huán)境或者對(duì)?？臻g極其敏感的場(chǎng)合遞歸仍然是個(gè)需要考量的因素。這也是為什么非遞歸版有存在價(jià)值——它把這層遞歸棧徹底省掉了。1.3 非遞歸版歸并的設(shè)計(jì)動(dòng)機(jī)與實(shí)現(xiàn)取舍非遞歸版也叫迭代版歸并排序的核心洞察是遞歸版的分裂過程其實(shí)可以換一種順序來理解。遞歸是“從上往下分再從下往上合”而非遞歸可以直接“從下往上合”——先讓相鄰的長度為 1 的段兩兩合并得到長度為 2 的有序段再讓相鄰的長度為 2 的段兩兩合并得到長度為 4 的有序段依此類推直到段長度覆蓋整個(gè)數(shù)組。這個(gè)思路的關(guān)鍵在于用一個(gè)外層循環(huán)控制“當(dāng)前合并段長度”從 1 開始每次翻倍。相比遞歸版它省掉了函數(shù)調(diào)用?？臻g上只多了合并用的臨時(shí)數(shù)組。代價(jià)是邊界處理更繁瑣當(dāng)數(shù)組長度不是 2 的冪時(shí)最后一段可能湊不齊需要額外判斷右半段的實(shí)際結(jié)束位置防止數(shù)組越界。這個(gè)邊界問題是非遞歸版最容易翻車的地方后面會(huì)專門展開。選型上的取舍很清楚追求代碼簡(jiǎn)潔和思維直觀用遞歸版追求對(duì)?？臻g的極致控制或者在不允許深遞歸的環(huán)境里用非遞歸版。兩者時(shí)間復(fù)雜度都是 O(n log n)空間復(fù)雜度都是 O(n)臨時(shí)數(shù)組穩(wěn)定性也都保持。實(shí)際工程里遞歸版更常見非遞歸版更多出現(xiàn)在教學(xué)對(duì)比和特定約束場(chǎng)景中。1.4 冒泡與選擇的定位不是陪襯是對(duì)照組冒泡排序和選擇排序在這里不是湊數(shù)的配角。冒泡排序的每一輪把當(dāng)前未排序部分的最大值“冒”到末尾核心操作是相鄰比較交換選擇排序每一輪從未排序部分選出最小值放到已排序部分末尾核心操作是記錄最小值下標(biāo)后一次性交換。兩者都是 O(n2)但交換次數(shù)差異明顯冒泡在最壞情況下交換次數(shù)是 O(n2) 級(jí)別選擇排序的交換次數(shù)最多只有 n-1 次。這個(gè)差異在實(shí)際場(chǎng)景里有意義。當(dāng)元素交換的成本很高比如元素是很大的結(jié)構(gòu)體交換涉及大量?jī)?nèi)存拷貝選擇排序的“少交換”特性反而成了優(yōu)勢(shì)。而冒泡排序的穩(wěn)定性相等不交換和“提前退出”優(yōu)化某一輪沒有發(fā)生交換說明已有序也是它常被低估的地方。把這兩個(gè)和歸并放在一起讀者能建立一個(gè)更完整的判斷框架不是 O(n2) 就一無是處要看數(shù)據(jù)規(guī)模、交換成本、穩(wěn)定性需求這幾個(gè)維度。2. 核心細(xì)節(jié)解析與實(shí)操要點(diǎn)2.1 歸并排序的合并環(huán)節(jié)整個(gè)算法的勝負(fù)手歸并排序真正干活的地方在合并merge這一步分裂只是把問題拆小。合并的邏輯是給定兩個(gè)已經(jīng)有序的相鄰子數(shù)組用兩個(gè)指針分別指向它們的起始位置每次比較兩個(gè)指針指向的元素把較小的那個(gè)放進(jìn)臨時(shí)數(shù)組并移動(dòng)對(duì)應(yīng)指針直到其中一個(gè)子數(shù)組被取完再把另一個(gè)子數(shù)組剩余部分整體追加到臨時(shí)數(shù)組末尾。這里有個(gè)細(xì)節(jié)必須講清楚“較小者先取”這個(gè)規(guī)則正是歸并排序穩(wěn)定性的來源。當(dāng)左右兩個(gè)子數(shù)組出現(xiàn)相等元素時(shí)我們?nèi)∽筮吥莻€(gè)這就保證了原本在左邊的相等元素在合并后依然在左邊相對(duì)順序不變。如果把規(guī)則改成“較小者先取相等時(shí)取右邊”排序結(jié)果依然正確但穩(wěn)定性就破壞了。這個(gè)點(diǎn)很多人寫代碼時(shí)沒意識(shí)到隨手寫成還是直接決定了穩(wěn)定性值得單獨(dú)記一筆。合并的另一個(gè)要點(diǎn)是臨時(shí)數(shù)組的使用。常見做法是每次合并都申請(qǐng)一個(gè)和待合并區(qū)間等長的臨時(shí)數(shù)組合并完再拷貝回原數(shù)組。這個(gè)做法簡(jiǎn)單但有個(gè)隱患頻繁申請(qǐng)釋放內(nèi)存有開銷。更優(yōu)的做法是全程只申請(qǐng)一個(gè)和原數(shù)組等長的輔助數(shù)組每次合并復(fù)用它合并時(shí)先把數(shù)據(jù)拷到輔助數(shù)組再從輔助數(shù)組合并回原數(shù)組。這樣內(nèi)存申請(qǐng)只發(fā)生一次對(duì)大數(shù)組更友好。我實(shí)測(cè)下來百萬級(jí)數(shù)據(jù)下這個(gè)優(yōu)化能省下可觀的時(shí)間。def merge(arr, temp, left, mid, right): # 把待合并區(qū)間拷貝到臨時(shí)數(shù)組 for i in range(left, right 1): temp[i] arr[i] i, j left, mid 1 k left while i mid and j right: # 相等時(shí)取左邊保證穩(wěn)定性 if temp[i] temp[j]: arr[k] temp[i] i 1 else: arr[k] temp[j] j 1 k 1 # 左半剩余 while i mid: arr[k] temp[i] i 1 k 1 # 右半剩余 while j right: arr[k] temp[j] j 1 k 1上面這段代碼里temp[i] temp[j]的就是穩(wěn)定性的關(guān)鍵。另外注意兩個(gè)收尾的 while 循環(huán)其實(shí)只需要處理其中一個(gè)——因?yàn)榱硪粋€(gè)子數(shù)組必然已經(jīng)取完但為了代碼對(duì)稱和可讀性兩個(gè)都寫上也無妨實(shí)際只會(huì)執(zhí)行一個(gè)。2.2 遞歸版的分裂邊界mid 怎么算不出錯(cuò)遞歸版歸并的分裂邏輯看起來簡(jiǎn)單mid (left right) // 2然后遞歸處理[left, mid]和[mid1, right]。但這里有個(gè)經(jīng)典陷阱當(dāng)left和right都很大時(shí)left right可能溢出在 C/C 這類語言里Python 不用擔(dān)心但換語言就踩坑。穩(wěn)妥的寫法是mid left (right - left) // 2用減法代替加法規(guī)避溢出。另一個(gè)容易錯(cuò)的地方是遞歸終止條件。終止條件應(yīng)該是left right而不是left right。因?yàn)楫?dāng)left right時(shí)區(qū)間只有一個(gè)元素天然有序直接返回即可。如果寫成left right單元素區(qū)間還會(huì)繼續(xù)分裂導(dǎo)致mid計(jì)算后出現(xiàn)[left, mid]為空或死循環(huán)的問題。這個(gè)細(xì)節(jié)我在代碼評(píng)審里見過不止一次屬于“看起來對(duì)但邊界一跑就崩”的典型。遞歸版的完整結(jié)構(gòu)如下注意分裂和合并的調(diào)用順序def merge_sort_recursive(arr, temp, left, right): if left right: return mid left (right - left) // 2 merge_sort_recursive(arr, temp, left, mid) merge_sort_recursive(arr, temp, mid 1, right) merge(arr, temp, left, mid, right)調(diào)用時(shí)傳入left0, rightlen(arr)-1temp是預(yù)先申請(qǐng)好的等長輔助數(shù)組。這個(gè)結(jié)構(gòu)清晰體現(xiàn)了“先遞歸排左半再遞歸排右半最后合并”的分治順序。2.3 非遞歸版的步長控制從 1 開始翻倍非遞歸版的核心是一個(gè)外層循環(huán)控制當(dāng)前要合并的段長度width從 1 開始每輪翻倍直到width n。每一輪里從左到右掃描把相鄰的兩個(gè)長度為width的段合并。這里的關(guān)鍵是計(jì)算每對(duì)段的邊界左段起點(diǎn)left i左段終點(diǎn)mid min(i width - 1, n - 1)右段起點(diǎn)mid 1右段終點(diǎn)right min(i 2 * width - 1, n - 1)用min兜底是為了處理數(shù)組長度不是 2 的冪的情況。比如數(shù)組長度 5當(dāng)width 4時(shí)第一對(duì)段是[0,3]和[4,4]右段只有一個(gè)元素right必須被截?cái)嗟?4否則越界。這個(gè)邊界處理是非遞歸版最容易出 bug 的地方我見過不少人在這里數(shù)組越界或者漏合并最后一段。def merge_sort_iterative(arr): n len(arr) temp [0] * n width 1 while width n: i 0 while i n: left i mid min(i width - 1, n - 1) right min(i 2 * width - 1, n - 1) if mid right: # 只有右段存在才需要合并 merge(arr, temp, left, mid, right) i 2 * width width * 2注意if mid right這個(gè)判斷當(dāng)mid right時(shí)說明右段為空只剩左段此時(shí)無需合并直接跳過。這個(gè)判斷能避免對(duì)單段做無意義的合并操作也防止merge函數(shù)里出現(xiàn)mid1 right的異常情況。2.4 冒泡排序的兩個(gè)關(guān)鍵優(yōu)化點(diǎn)冒泡排序的基礎(chǔ)版是雙重循環(huán)外層控制輪數(shù)內(nèi)層相鄰比較交換。但基礎(chǔ)版有兩個(gè)明顯可優(yōu)化點(diǎn)值得單獨(dú)說。第一個(gè)是提前退出如果某一輪內(nèi)層循環(huán)沒有發(fā)生任何交換說明整個(gè)數(shù)組已經(jīng)有序可以直接跳出外層循環(huán)。這個(gè)優(yōu)化讓冒泡在最好情況已有序下時(shí)間復(fù)雜度降到 O(n)而不是死板地跑滿 O(n2)。實(shí)現(xiàn)上用一個(gè)布爾標(biāo)記記錄本輪是否交換即可。第二個(gè)是縮小內(nèi)層邊界每一輪結(jié)束后末尾已經(jīng)排好一個(gè)元素下一輪內(nèi)層循環(huán)的右邊界可以減一。這個(gè)優(yōu)化不改變復(fù)雜度但能減少約一半的比較次數(shù)實(shí)測(cè)對(duì)小數(shù)組有可感知的提升。def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False # 每輪右邊界收縮已排好的尾部不再比較 for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: breakarr[j] arr[j 1]這個(gè)嚴(yán)格大于號(hào)是冒泡穩(wěn)定性的保證——相等時(shí)不交換相對(duì)順序不變。如果寫成相等元素會(huì)被交換穩(wěn)定性就沒了。這個(gè)細(xì)節(jié)和歸并合并時(shí)的是同一類問題值得對(duì)照記憶。2.5 選擇排序的交換策略與不穩(wěn)定性來源選擇排序的思路是每輪從未排序區(qū)間選出最小值和未排序區(qū)間的第一個(gè)元素交換。它的交換次數(shù)最多 n-1 次這是它相對(duì)冒泡的最大優(yōu)勢(shì)。但選擇排序是不穩(wěn)定的原因在于那個(gè)“交換”動(dòng)作當(dāng)最小值被交換到前面時(shí)可能把原本在前面的相等元素甩到后面去。舉個(gè)具體例子數(shù)組[5a, 5b, 2]用 a、b 區(qū)分兩個(gè) 5。第一輪選出最小值 2和第一個(gè)位置的 5a 交換得到[2, 5b, 5a]。原本 5a 在 5b 前面交換后 5a 跑到了 5b 后面穩(wěn)定性被破壞。這個(gè)例子很能說明問題選擇排序的不穩(wěn)定不是理論上的邊角情況而是交換策略的必然結(jié)果。def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i]if min_idx ! i這個(gè)判斷是減少無意義交換的小優(yōu)化——如果最小值本來就在當(dāng)前位置就不用交換。這個(gè)判斷對(duì)穩(wěn)定性沒有幫助該破壞還是破壞但能省掉一些自交換操作。2.6 三個(gè)排序的復(fù)雜度與特性對(duì)照把關(guān)鍵指標(biāo)拉成一張表對(duì)照著看更清楚排序算法平均時(shí)間最壞時(shí)間最好時(shí)間空間穩(wěn)定性交換次數(shù)歸并排序遞歸/非遞歸O(n log n)O(n log n)O(n log n)O(n)穩(wěn)定O(n log n)冒泡排序O(n2)O(n2)O(n)優(yōu)化后O(1)穩(wěn)定O(n2)選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定O(n)這張表里最值得琢磨的是“交換次數(shù)”這一列。選擇排序雖然時(shí)間復(fù)雜度和冒泡一樣是 O(n2)但交換次數(shù)只有 O(n)當(dāng)交換成本遠(yuǎn)高于比較成本時(shí)選擇排序的實(shí)際表現(xiàn)可能反超冒泡。這個(gè)視角在純理論教學(xué)里經(jīng)常被忽略但在實(shí)際工程判斷里很有用。3. 實(shí)操過程與核心環(huán)節(jié)實(shí)現(xiàn)3.1 從零搭建一個(gè)可復(fù)用的歸并排序模塊我習(xí)慣把歸并排序封裝成一個(gè)對(duì)外只暴露一個(gè)入口函數(shù)的模塊內(nèi)部把遞歸版和非遞歸版都保留通過參數(shù)切換。這樣既方便對(duì)比測(cè)試也方便在不同場(chǎng)景下選用。模塊結(jié)構(gòu)大致是一個(gè)merge輔助函數(shù)、一個(gè)遞歸版實(shí)現(xiàn)、一個(gè)非遞歸版實(shí)現(xiàn)、一個(gè)統(tǒng)一入口。統(tǒng)一入口的設(shè)計(jì)要點(diǎn)是入口函數(shù)負(fù)責(zé)申請(qǐng)臨時(shí)數(shù)組只申請(qǐng)一次然后根據(jù)參數(shù)決定走遞歸還是非遞歸路徑。這樣臨時(shí)數(shù)組的管理集中在一處兩個(gè)實(shí)現(xiàn)共享避免重復(fù)申請(qǐng)。參數(shù)上用一個(gè)布爾值recursiveTrue控制默認(rèn)走遞歸版因?yàn)檫f歸版更常用。def merge_sort(arr, recursiveTrue): if len(arr) 1: return arr temp [0] * len(arr) if recursive: merge_sort_recursive(arr, temp, 0, len(arr) - 1) else: merge_sort_iterative(arr) return arr這里有個(gè)小設(shè)計(jì)入口函數(shù)先判斷l(xiāng)en(arr) 1直接返回避免對(duì)空數(shù)組或單元素?cái)?shù)組做無謂的臨時(shí)數(shù)組申請(qǐng)和遞歸調(diào)用。這個(gè)短路判斷在批量處理小數(shù)組時(shí)能省下不少開銷。3.2 遞歸版完整實(shí)現(xiàn)與逐行注釋把前面拆開的片段組裝成完整可運(yùn)行的遞歸版逐行注釋關(guān)鍵點(diǎn)def merge_sort_recursive(arr, temp, left, right): # 終止條件區(qū)間長度 1天然有序 if left right: return # 防溢出的中點(diǎn)計(jì)算 mid left (right - left) // 2 # 遞歸排序左半?yún)^(qū) merge_sort_recursive(arr, temp, left, mid) # 遞歸排序右半?yún)^(qū) merge_sort_recursive(arr, temp, mid 1, right) # 合并兩個(gè)有序半?yún)^(qū) merge(arr, temp, left, mid, right)這段代碼的執(zhí)行順序值得在腦子里過一遍以[38, 27, 43, 3]為例第一次調(diào)用left0, right3, mid1先遞歸[0,1]再遞歸[2,3]然后合并。遞歸[0,1]時(shí)mid0先遞歸[0,0]返回再遞歸[1,1]返回然后合并[0,0]和[1,1]得到[27,38]。右半?yún)^(qū)同理得到[3,43]。最后合并[27,38]和[3,43]得到[3,27,38,43]。這個(gè)手動(dòng)推演的過程建議每個(gè)初學(xué)者都走一遍走通了遞歸版的執(zhí)行流就徹底清楚了。3.3 非遞歸版完整實(shí)現(xiàn)與邊界驗(yàn)證非遞歸版的完整實(shí)現(xiàn)前面已經(jīng)給出核心循環(huán)這里補(bǔ)充一個(gè)容易忽略的細(xì)節(jié)外層width循環(huán)的終止條件是width n而不是width n。因?yàn)楫?dāng)width n時(shí)整個(gè)數(shù)組已經(jīng)作為一個(gè)整體有序無需再合并。如果寫成width n會(huì)多跑一輪無意義的循環(huán)雖然結(jié)果正確但浪費(fèi)。邊界驗(yàn)證我習(xí)慣用幾個(gè)特殊長度的數(shù)組來測(cè)長度 1直接返回、長度 2一輪合并、長度 3非 2 的冪驗(yàn)證min截?cái)?、長度 5驗(yàn)證width4時(shí)的截?cái)?、長度 82 的冪驗(yàn)證完整合并。這幾個(gè)長度覆蓋了非遞歸版的主要邊界情況跑通基本就沒大問題了。# 邊界測(cè)試用例 test_cases [ [], [1], [2, 1], [3, 1, 2], [5, 4, 3, 2, 1], [8, 7, 6, 5, 4, 3, 2, 1], ] for case in test_cases: original case[:] merge_sort(case, recursiveFalse) assert case sorted(original), ffailed on {original}這段測(cè)試代碼用sorted作為標(biāo)準(zhǔn)答案對(duì)照覆蓋了空數(shù)組、單元素、非 2 的冪、逆序等典型情況。我建議任何實(shí)現(xiàn)排序算法的人都養(yǎng)成寫這種對(duì)照測(cè)試的習(xí)慣比肉眼檢查靠譜得多。3.4 冒泡與選擇的完整實(shí)現(xiàn)及測(cè)試對(duì)照冒泡和選擇的完整實(shí)現(xiàn)前面已給出這里補(bǔ)充測(cè)試對(duì)照的思路。三個(gè)排序可以用同一組測(cè)試數(shù)據(jù)跑結(jié)果都應(yīng)該等于sorted的結(jié)果。但要注意穩(wěn)定性無法通過簡(jiǎn)單的值比較驗(yàn)證需要構(gòu)造帶標(biāo)記的元素來測(cè)。驗(yàn)證穩(wěn)定性的方法是把元素包裝成(值, 原始下標(biāo))的元組排序后檢查相同值的元素其原始下標(biāo)是否保持遞增。歸并和冒泡應(yīng)該通過選擇應(yīng)該失敗。這個(gè)測(cè)試能直觀暴露選擇排序的不穩(wěn)定性比純理論解釋有說服力得多。def check_stability(sort_func, arr): # 包裝成 (值, 原始下標(biāo)) wrapped [(v, i) for i, v in enumerate(arr)] sort_func(wrapped) # 檢查相同值的原始下標(biāo)是否遞增 for k in range(1, len(wrapped)): if wrapped[k][0] wrapped[k-1][0]: if wrapped[k][1] wrapped[k-1][1]: return False return True用[5, 5, 2]這類含重復(fù)元素的數(shù)組去跑歸并和冒泡返回True選擇返回False。這個(gè)測(cè)試寫一次就能長期復(fù)用是理解穩(wěn)定性最直接的手段。3.5 性能實(shí)測(cè)不同規(guī)模下的表現(xiàn)對(duì)比理論復(fù)雜度是一回事實(shí)測(cè)是另一回事。我用隨機(jī)整數(shù)數(shù)組做了幾組對(duì)比規(guī)模從 1000 到 100000記錄大致耗時(shí)趨勢(shì)具體數(shù)值因機(jī)器而異這里只談相對(duì)關(guān)系。規(guī)模 1000 時(shí)三個(gè)排序的差距還不算夸張歸并明顯最快冒泡和選擇都在毫秒級(jí)。規(guī)模到 10000 時(shí)差距開始拉開冒泡和選擇的耗時(shí)增長到歸并的幾十倍。規(guī)模到 100000 時(shí)冒泡和選擇已經(jīng)慢到不適合實(shí)際使用歸并依然在可接受范圍內(nèi)。這個(gè)實(shí)測(cè)結(jié)果和理論預(yù)期一致但親眼看到 O(n2) 和 O(n log n) 在數(shù)據(jù)量增大時(shí)的分化對(duì)理解復(fù)雜度很有幫助。另一個(gè)值得實(shí)測(cè)的點(diǎn)是遞歸版和非遞歸版的對(duì)比。在 Python 環(huán)境下兩者耗時(shí)非常接近非遞歸版略快一點(diǎn)點(diǎn)省了函數(shù)調(diào)用開銷但差距在噪聲范圍內(nèi)。這說明對(duì)于常規(guī)場(chǎng)景選哪個(gè)主要看代碼可讀性和環(huán)境約束性能不是決定因素。4. 常見問題與排查技巧實(shí)錄4.1 歸并排序結(jié)果正確但順序“看起來不對(duì)”這個(gè)問題通常不是 bug而是對(duì)穩(wěn)定性的誤解。有人用含重復(fù)元素的數(shù)組測(cè)試發(fā)現(xiàn)相同元素的相對(duì)順序和預(yù)期不符就以為排序錯(cuò)了。實(shí)際上只要最終值有序排序就是正確的穩(wěn)定性是額外屬性不是正確性要求。如果確實(shí)需要穩(wěn)定性檢查合并時(shí)的比較符號(hào)是不是取左邊以及遞歸/非遞歸的分裂邊界有沒有把相等元素分到錯(cuò)誤的一側(cè)。排查方法是構(gòu)造帶下標(biāo)的包裝元素排序后檢查相同值的下標(biāo)順序。如果下標(biāo)亂了說明穩(wěn)定性被破壞回頭查比較符號(hào)。這個(gè)排查思路前面 3.4 節(jié)已經(jīng)給了代碼直接拿來用即可。4.2 非遞歸版數(shù)組越界或漏排最后一段這是非遞歸版最高頻的問題根源在邊界計(jì)算。典型癥狀是數(shù)組長度不是 2 的冪時(shí)程序拋越界異?；蛘咦詈髱讉€(gè)元素沒被正確排序。排查步驟先打印每輪的width、left、mid、right看right有沒有超過n-1再檢查if mid right這個(gè)判斷有沒有漏掉導(dǎo)致對(duì)空右段調(diào)用了合并。一個(gè)實(shí)用的調(diào)試技巧是把merge函數(shù)開頭加上邊界斷言assert 0 left mid right len(arr)。這個(gè)斷言能在越界發(fā)生的第一時(shí)間定位問題比等到后面數(shù)組訪問報(bào)錯(cuò)再回溯要高效得多。上線前把斷言去掉即可不影響性能。4.3 遞歸深度過大導(dǎo)致棧溢出雖然歸并的遞歸深度只有 log?n常規(guī)數(shù)據(jù)量下不會(huì)出問題但在某些對(duì)棧空間限制嚴(yán)格的環(huán)境里或者數(shù)據(jù)量極大比如上億時(shí)仍可能觸發(fā)棧溢出。排查方法是先確認(rèn)遞歸深度可以在遞歸函數(shù)里維護(hù)一個(gè)深度計(jì)數(shù)器打印最大深度。如果確實(shí)超限切換到非遞歸版即可非遞歸版沒有遞歸棧開銷。另一個(gè)容易混淆的點(diǎn)是歸并的遞歸深度是 log?n不是 n。有人看到遞歸就擔(dān)心 O(n) 深度其實(shí)歸并是二分遞歸深度是對(duì)數(shù)級(jí)。這個(gè)認(rèn)知能避免不必要的恐慌也能幫助判斷什么時(shí)候真的需要換非遞歸版。4.4 冒泡排序“優(yōu)化后反而更慢”提前退出優(yōu)化在已有序或接近有序的數(shù)組上效果顯著但在完全逆序的數(shù)組上swapped標(biāo)記每輪都是True判斷本身成了額外開銷理論上會(huì)略慢于不優(yōu)化的版本。不過這個(gè)開銷極小實(shí)際測(cè)下來差異在噪聲范圍內(nèi)不值得為此糾結(jié)。真正需要注意的是不要為了“優(yōu)化”而引入復(fù)雜的邏輯冒泡的提前退出已經(jīng)足夠簡(jiǎn)單再復(fù)雜的優(yōu)化收益遞減。4.5 常見問題速查表問題現(xiàn)象可能原因排查方向解決方式歸并結(jié)果值有序但相同元素順序亂合并時(shí)比較符號(hào)寫反檢查是否寫成或改為相等取左邊非遞歸版越界right未用min截?cái)啻蛴∶枯嗊吔缰导觤in(..., n-1)非遞歸版漏排尾部mid right判斷缺失檢查最后一段是否被跳過補(bǔ)上判斷或調(diào)整循環(huán)遞歸版死循環(huán)終止條件寫成left right檢查單元素區(qū)間是否繼續(xù)分裂改為left right選擇排序結(jié)果對(duì)但穩(wěn)定性測(cè)試失敗交換破壞相等元素順序構(gòu)造帶下標(biāo)元素測(cè)試屬預(yù)期行為需穩(wěn)定則換算法大數(shù)組歸并內(nèi)存占用高每次合并都申請(qǐng)臨時(shí)數(shù)組檢查臨時(shí)數(shù)組申請(qǐng)位置改為全程復(fù)用單個(gè)輔助數(shù)組4.6 幾個(gè)踩過坑才記住的實(shí)操心得第一個(gè)心得臨時(shí)數(shù)組一定要在入口處申請(qǐng)一次不要在 merge 里反復(fù)申請(qǐng)。我早期寫歸并就是在 merge 里temp []小數(shù)據(jù)看不出問題數(shù)據(jù)一大內(nèi)存分配的開銷就顯現(xiàn)出來了。改成全程復(fù)用一個(gè)輔助數(shù)組后性能提升明顯。這個(gè)改動(dòng)很小但收益很實(shí)在。第二個(gè)心得測(cè)試排序算法一定要用帶重復(fù)元素的數(shù)組。全不相同的數(shù)組測(cè)不出穩(wěn)定性問題也測(cè)不出相等元素處理的邊界。我習(xí)慣用[3, 1, 3, 2, 1, 2]這種含重復(fù)的短數(shù)組做快速驗(yàn)證能同時(shí)覆蓋值排序和穩(wěn)定性兩個(gè)維度。第三個(gè)心得非遞歸版的width循環(huán)建議從 1 開始而不是從 2 開始。有人為了“優(yōu)化”直接從 2 開始前提是先把相鄰兩個(gè)元素手動(dòng)排好這樣代碼更復(fù)雜且容易漏掉長度為 1 的初始段。從 1 開始雖然多跑一輪但邏輯統(tǒng)一不容易出錯(cuò)。性能差異可以忽略正確性優(yōu)先。第四個(gè)心得遞歸版和非遞歸版共用同一個(gè) merge 函數(shù)。這樣合并邏輯只寫一遍兩個(gè)版本的差異只在“怎么分裂/怎么控制步長”對(duì)比學(xué)習(xí)時(shí)能更聚焦于兩者的本質(zhì)區(qū)別。共用 merge 也保證了兩個(gè)版本的排序結(jié)果和穩(wěn)定性完全一致減少維護(hù)成本。5. 場(chǎng)景化選型建議與延伸思考5.1 什么場(chǎng)景該用歸并什么場(chǎng)景冒泡選擇反而合適歸并排序的適用場(chǎng)景很明確數(shù)據(jù)量較大、需要穩(wěn)定排序、對(duì)最壞情況時(shí)間復(fù)雜度有要求。比如對(duì)一批帶時(shí)間戳的記錄排序時(shí)間戳相同的記錄需要保持原始錄入順序這時(shí)候歸并的穩(wěn)定性就是剛需。再比如數(shù)據(jù)量在十萬級(jí)以上O(n2) 的算法已經(jīng)不可接受歸并的 O(n log n) 是基本門檻。冒泡和選擇并非一無是處。數(shù)據(jù)量很小比如幾十個(gè)元素時(shí)三者的實(shí)際耗時(shí)差異微乎其微這時(shí)候選代碼最簡(jiǎn)單的冒泡完全合理。元素交換成本極高時(shí)選擇排序的 O(n) 交換次數(shù)優(yōu)勢(shì)就體現(xiàn)出來了。還有一種情況是教學(xué)和面試冒泡和選擇的代碼短、邏輯直白適合用來考察對(duì)基礎(chǔ)循環(huán)和邊界處理的理解這個(gè)價(jià)值不該被“過時(shí)論”抹殺。5.2 從歸并延伸出去分治思想的復(fù)用歸并排序是分治思想最干凈的樣板分解、解決、合并三步清晰分離。理解了這個(gè)樣板很多其他算法都能套進(jìn)來。比如快速排序也是分治但它的“合并”是隱式的原地分區(qū)后自然有序重點(diǎn)在“分解”時(shí)的分區(qū)策略再比如歸并思想在外部排序里的應(yīng)用——數(shù)據(jù)大到內(nèi)存放不下時(shí)先分塊排序?qū)懟卮疟P再多路歸并本質(zhì)還是歸并的合并邏輯。我在實(shí)際項(xiàng)目里遇到過一個(gè)場(chǎng)景需要對(duì)多個(gè)已經(jīng)有序的數(shù)據(jù)源做合并輸出直接用歸并的合并環(huán)節(jié)就能搞定不需要完整排序。這說明歸并的 merge 函數(shù)本身就是一個(gè)可獨(dú)立復(fù)用的工具值得單獨(dú)掌握。把 merge 抽出來做成通用函數(shù)輸入兩個(gè)有序序列輸出一個(gè)有序序列這個(gè)抽象在很多數(shù)據(jù)處理場(chǎng)景里都能用上。5.3 給不同基礎(chǔ)讀者的練習(xí)路徑如果你是剛接觸排序的新手建議按這個(gè)順序練先手寫冒泡并加上提前退出優(yōu)化理解“比較交換”和“穩(wěn)定性”再手寫選擇理解“選最小值”和“交換破壞穩(wěn)定性”最后上歸并的遞歸版重點(diǎn)理解 merge 環(huán)節(jié)。每一步都寫測(cè)試對(duì)照sorted并用帶重復(fù)元素的數(shù)組驗(yàn)證穩(wěn)定性。如果你已經(jīng)能寫出歸并遞歸版下一步挑戰(zhàn)非遞歸版重點(diǎn)攻克邊界截?cái)鄦栴}。寫完后用長度 1、2、3、5、8 的數(shù)組逐一驗(yàn)證確保沒有越界和漏排。再進(jìn)一步嘗試把 merge 函數(shù)抽成獨(dú)立工具用它解決“合并兩個(gè)有序數(shù)組”這個(gè)經(jīng)典問題體會(huì)歸并思想的復(fù)用價(jià)值。如果你是在準(zhǔn)備面試重點(diǎn)練手寫歸并遞歸版和冒泡優(yōu)化版這兩個(gè)是高頻考點(diǎn)。非遞歸版理解思路即可手寫概率相對(duì)低。面試時(shí)如果被問到穩(wěn)定性能用“合并時(shí)相等取左邊”和“冒泡相等不交換”這兩個(gè)具體規(guī)則回答比背概念有說服力得多。5.4 一個(gè)容易被忽略的性能細(xì)節(jié)小數(shù)組切換插入排序工業(yè)級(jí)的歸并排序?qū)崿F(xiàn)里常見一個(gè)優(yōu)化當(dāng)子數(shù)組長度小于某個(gè)閾值比如 16 或 32時(shí)不再繼續(xù)遞歸分裂直接改用插入排序。原因是小數(shù)組上遞歸和合并的開銷相對(duì)較大而插入排序在小數(shù)組上常數(shù)因子小、實(shí)際更快。這個(gè)優(yōu)化能把歸并的整體性能再提升一截。這個(gè)優(yōu)化的思路值得借鑒算法選型不是非黑即白大框架用歸并保證 O(n log n)小局部用插入排序降低常數(shù)開銷兩者結(jié)合取長補(bǔ)短。我在實(shí)際實(shí)現(xiàn)里試過閾值取 16效果不錯(cuò)。閾值具體取多少需要實(shí)測(cè)不同語言、不同數(shù)據(jù)分布下最優(yōu)值會(huì)有差異但量級(jí)上十幾到幾十之間比較常見。這個(gè)細(xì)節(jié)也說明理論上的“最優(yōu)算法”和工程上的“最優(yōu)實(shí)現(xiàn)”之間往往還隔著一層常數(shù)優(yōu)化。最后分享一個(gè)我自己的習(xí)慣每次實(shí)現(xiàn)完一個(gè)排序我都會(huì)用同一組隨機(jī)數(shù)據(jù)和sorted對(duì)照跑一遍再用帶重復(fù)元素的數(shù)組驗(yàn)證穩(wěn)定性最后用幾個(gè)特殊長度0、1、2、3、5、8驗(yàn)證邊界。這套流程跑下來基本能覆蓋 90% 以上的常見 bug。排序算法看著簡(jiǎn)單但邊界和穩(wěn)定性這兩塊不實(shí)際跑測(cè)試是真的容易翻車。