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