排序這塊東西平時(shí)寫業(yè)務(wù)代碼的人很少自己動(dòng)手調(diào)個(gè)庫函數(shù)就完事了。但只要經(jīng)歷過幾次凌晨被叫起來查問題或者被丟到資源吃緊的環(huán)境里跑程序就會開始琢磨底層到底發(fā)生了什么。我這次聊的是快速排序的非遞歸寫法——這個(gè)系列前面三篇把遞歸版實(shí)現(xiàn)、基準(zhǔn)選擇策略、小區(qū)間優(yōu)化都過了一遍這一篇專門解決“把遞歸干掉”這件事。標(biāo)題里寫了個(gè)“4”說明它不是入門默認(rèn)你已經(jīng)知道快排為什么平均是 O(n log n)也知道最壞為什么退化成 O(n2)。為什么值得單獨(dú)用一篇講非遞歸因?yàn)檫f歸快排和迭代快排看起來只是寫法差異實(shí)際上在?？臻g、可中斷性、調(diào)試成本上是兩套完全不同的東西。我自己第一次改這個(gè)版本是因?yàn)槟硞€(gè)日志處理模塊在排序 50 萬條記錄時(shí)會偶發(fā)崩潰日志里看不出任何異常換成非遞歸加顯式棧之后穩(wěn)定跑了兩年。這篇內(nèi)容適合三類人正在啃算法課、想搞清楚系統(tǒng)棧到底存了什么的學(xué)生需要在受限環(huán)境里跑排序的開發(fā)以及已經(jīng)寫出來能跑、但總擔(dān)心邊界和棧深度的讀者。代碼我統(tǒng)一用 C但思路和 Java、Python、Go 完全通用語言只是皮。1. 為什么要把快排從遞歸改成非遞歸1.1 遞歸快排真正的風(fēng)險(xiǎn)點(diǎn)在哪遞歸版快排的代碼短、邏輯干凈教科書上基本都是那個(gè)樣子選基準(zhǔn)、劃分、左右兩半各自遞歸。絕大多數(shù)情況下它跑得很好以至于很多人根本不覺得這里面有風(fēng)險(xiǎn)。但風(fēng)險(xiǎn)確實(shí)存在只是被“數(shù)據(jù)量不大”“棧空間夠用”這兩個(gè)前提遮住了。第一類風(fēng)險(xiǎn)是棧深度不可控。遞歸的調(diào)用棧由運(yùn)行時(shí)替你管理你沒法設(shè)置它的大小也沒法在中途檢查“還剩多少”。標(biāo)準(zhǔn)快排在最壞情況下每次劃分都極不均勻比如數(shù)組已經(jīng)有序而基準(zhǔn)固定取第一個(gè)元素遞歸深度會退化到 n 層。n 等于 10? 的時(shí)候每層棧幀哪怕只占 64 字節(jié)加起來也要 64MB默認(rèn)配置基本直接崩。我遇到過在一塊嵌入式板子上排序二十幾萬條記錄程序不是算錯(cuò)是直接復(fù)位——棧溢出觸發(fā)了硬件異常。第二類風(fēng)險(xiǎn)是遞歸進(jìn)去就出不來。業(yè)務(wù)上經(jīng)常有這種需求排序要分批做中間讓出 CPU 給別的任務(wù)或者排序過程要能被中斷、能匯報(bào)進(jìn)度。遞歸寫法一旦進(jìn)去就得跑完才返回想做協(xié)作式調(diào)度非常別扭。非遞歸把狀態(tài)放在堆上自己管隨時(shí)可以停下來保存現(xiàn)場、下次接著跑。第三類風(fēng)險(xiǎn)是可觀測性差。遞歸深了以后調(diào)試器里棧幀幾十層想知道“現(xiàn)在到底在處理哪個(gè)區(qū)間”非常費(fèi)勁顯式棧就不一樣你把棧內(nèi)容打出來里面就是待處理的區(qū)間列表一眼就能看出卡在哪一段。這一點(diǎn)在排查“排完整體看著對、局部區(qū)間沒排好”這類詭異問題時(shí)特別有用我后面第 5 章會詳細(xì)講。1.2 顯式棧方案與遞歸的等價(jià)性拆解要改造成功得先想清楚一件事遞歸快排的調(diào)用棧里到底存了什么答案比你想象的少。函數(shù)返回地址、參數(shù)、局部變量看著一堆但真正決定“下一步干什么”的信息只有一樣——待處理區(qū)間的兩個(gè)端點(diǎn)?；鶞?zhǔn)、臨時(shí)變量、循環(huán)計(jì)數(shù)器在劃分結(jié)束的那一瞬間全部作廢了不需要保存。這個(gè)“狀態(tài)壓縮”是快排能優(yōu)雅改成迭代的關(guān)鍵。換成帶回溯的搜索類算法比如八皇后、圖著色狀態(tài)復(fù)雜得多改成迭代得自己造一臺狀態(tài)機(jī)那才叫痛苦?？炫艣]有這個(gè)問題一個(gè)存區(qū)間的數(shù)組就完全等價(jià)。等價(jià)關(guān)系可以這么理解遞歸是運(yùn)行時(shí)替你維護(hù)一個(gè)棧每層壓入“返回后繼續(xù)處理右半段”這層意思非遞歸是你自己維護(hù)一個(gè)數(shù)組顯式地壓入“右半段還沒處理”。前者你只能相信它不出問題后者你可以數(shù)、可以打印、可以斷言、可以限制上限。1.3 什么場景值得上非遞歸不是所有場合都值得改。給你一張我自己整理的判斷表按實(shí)際情況對號入座場景特征建議原因數(shù)據(jù)量小于十萬跑在桌面/服務(wù)器保持遞歸代碼短維護(hù)成本低棧深度撐得住數(shù)據(jù)量百萬級且輸入可能有序必須非遞歸或加隨機(jī)基準(zhǔn)極端輸入下遞歸深度無法預(yù)估運(yùn)行在資源受限環(huán)境強(qiáng)烈建議非遞歸顯式棧可以定長預(yù)分配不占運(yùn)行棧需要分批、可中斷執(zhí)行必須非遞歸遞歸無法保存中間狀態(tài)返回排序邏輯本身在熱路徑被頻繁調(diào)用建議非遞歸省掉函數(shù)調(diào)用開銷實(shí)測有 3%~8% 提升教學(xué)、面試、一次性腳本遞歸可讀性優(yōu)先別過度設(shè)計(jì)那點(diǎn)性能差異是怎么來的省掉了每次調(diào)用的壓棧、跳轉(zhuǎn)、返回但增加了顯式數(shù)組的讀寫。兩者大致抵消非遞歸略占優(yōu)因?yàn)閿?shù)組讀寫是順序的、緩存友好而函數(shù)調(diào)用會污染指令緩存。別指望靠這個(gè)提速一倍那是想多了。2. 核心設(shè)計(jì)棧里到底該存什么2.1 存區(qū)間下標(biāo)的經(jīng)典方案最直接的方案是壓入一對下標(biāo)。這里有個(gè)小分歧存左閉右閉的(lo, hi)還是存起點(diǎn)加長度(lo, len)。兩種都對我偏好前者因?yàn)楹徒炭茣系倪f歸參數(shù)完全一致改成迭代時(shí)不需要做任何坐標(biāo)換算少一層心算就少一類錯(cuò)誤。用長度的話每次劃分后要算(lo, p - lo)和(p 1, hi - p)寫起來啰嗦而且hi - lo和hi - lo 1差一個(gè) 1 的地方特別容易錯(cuò)。閉區(qū)間寫法里某一段非空的條件就是lo hi空區(qū)間根本不入棧——這個(gè)判斷簡單到不會寫錯(cuò)。用一個(gè)結(jié)構(gòu)體數(shù)組還是兩個(gè)并行數(shù)組小規(guī)模我傾向兩個(gè)int數(shù)組并行避免結(jié)構(gòu)體對齊帶來的額外填充緩存行利用率也高一點(diǎn)。當(dāng)然這點(diǎn)差異在絕大多數(shù)業(yè)務(wù)里可以忽略別在這上面花太多心思。一個(gè)更省空間的變體是既然hi可以由lo加長度推出來而長度在排序過程中只會變小那確實(shí)能用更少的位數(shù)編碼。但這類優(yōu)化屬于“我已經(jīng)很閑了”級別除非你的棧真的是瓶頸否則沒必要。2.2 只壓較小區(qū)間加循環(huán)處理大區(qū)間這一節(jié)是全篇最重要的部分也是決定你寫出來的是“假非遞歸”深度仍然是 O(n)還是“真非遞歸”深度 O(log n)的分水嶺。樸素的做法是劃分完左右兩段都壓棧。代碼看起來對稱漂亮問題是最壞情況下棧里會堆積 O(n) 個(gè)區(qū)間——比如輸入已經(jīng)有序、每次劃分只能切掉一個(gè)元素時(shí)每層都壓一個(gè)只含一個(gè)元素的區(qū)間棧長直接線性增長。你從遞歸棧溢出改成了自己的數(shù)組溢出問題只是從 A 換成了 B。正確解法是尾遞歸消除每次劃分完先處理較短的那一段把較長的那一段壓棧。為什么這樣管用因?yàn)檠h(huán)變量代表“當(dāng)前正在處理的區(qū)間”它在不斷變小而棧里存的每一個(gè)區(qū)間長度至少是上一層處理區(qū)間的一半以上。既然每壓一次棧規(guī)模至少翻倍那棧里最多就log?(n)個(gè)元素。推導(dǎo)過程寫清楚一點(diǎn)設(shè)當(dāng)前區(qū)間長度 m劃分后左段長 a、右段長 b滿足 a b m ? 1扣掉基準(zhǔn)本身占的一位。我們壓入較長的那段處理較短的那段。那么下一次循環(huán)處理的區(qū)間長度不超過 (m ? 1)/2。也就是說循環(huán)每轉(zhuǎn)一圈工作區(qū)間至少減半一次。從 n 減到 1最多需要log?(n)輪而每一輪最多往棧里加一個(gè)元素因此棧的峰值深度不超過log?(n) 1。順帶一個(gè)好處較短的那段先處理它的數(shù)據(jù)大概率還在 CPU 緩存里局部性更好。這個(gè)收益在百萬級數(shù)據(jù)上實(shí)測能看出一點(diǎn)差別雖然不大。2.3 棧容量上界推導(dǎo)與定長預(yù)分配有了上面的結(jié)論棧容量就可以算死了。log?(n)在 n 取 232約 43 億時(shí)是 32加 1 是 33。就算你排序 2?? 個(gè)元素現(xiàn)實(shí)中不可能也才 65。所以開一個(gè)長度 64 的定長int數(shù)組永遠(yuǎn)不會溢出。這是我很喜歡的一個(gè)工程細(xì)節(jié)整個(gè)快排迭代版可以做到零動(dòng)態(tài)內(nèi)存分配。不用std::vector、不用new、不用malloc排序過程里一次堆操作都沒有。對于那些“排序中途絕不能失敗”“不能拋異?！钡膱龊媳热缧盘柼幚怼?shí)時(shí)控制這一點(diǎn)比性能更有價(jià)值。不過定長預(yù)分配有個(gè)前提必須是“壓大處理小”策略。如果你改成兩邊都壓棧或者壓小處理大64 就完全不夠用了。所以這個(gè)常量和策略是綁定的寫注釋的時(shí)候一定要說明白不然下一個(gè)人改兩行代碼棧就悄悄溢出了。我自己習(xí)慣在代碼里加一句斷言assert(top STACK_CAPACITY stack overflow: check push-smaller strategy);斷言在調(diào)試時(shí)能第一時(shí)間抓住問題在發(fā)布版里編譯掉不留開銷。3. 劃分環(huán)節(jié)的工程化改造3.1 三數(shù)取中與小區(qū)間切換閾值迭代框架搭好之后性能瓶頸就全落在劃分函數(shù)上。基準(zhǔn)選擇依然是重點(diǎn)固定取首元素的策略在已排序或逆序輸入下會退化成 O(n2)這個(gè)坑遞歸版會踩非遞歸版一樣會踩。三數(shù)取中是最劃算的改進(jìn)代價(jià)是三次比較加一次交換收益是把極端輸入下的劃分質(zhì)量拉回正常水平。具體做法是比較首、中、尾三個(gè)位置的值把中位數(shù)換到首位置當(dāng)基準(zhǔn)。注意這里有個(gè)容易寫錯(cuò)的點(diǎn)三數(shù)取中不是取平均值也不是簡單取中間位置而是真的把三個(gè)值排序后取中間那個(gè)。小區(qū)間切換閾值是另一個(gè)必加的優(yōu)化。數(shù)組長度小于某個(gè)門檻時(shí)直接走插入排序不再劃分。原因有三個(gè)小數(shù)組上插入排序的常數(shù)因子遠(yuǎn)小于快排沒有函數(shù)調(diào)用、沒有遞歸、分支預(yù)測友好快排在長度只有幾個(gè)元素時(shí)劃分本身就沒什么收益反而白白做了一堆比較插入排序是穩(wěn)定的順序訪問緩存命中率高。門檻取多少市面上的實(shí)現(xiàn)從 8 到 32 都有。我在第 4 章給了一組實(shí)測數(shù)據(jù)結(jié)論是16 到 24 之間差別很小取 24 稍微穩(wěn)一點(diǎn)。別糾結(jié)這個(gè)數(shù)字差幾個(gè)元素對整體性能的影響在 1% 以內(nèi)比你在其他地方隨手浪費(fèi)的多得多。3.2 Hoare 與 Lomuto 的取舍劃分算法有兩套主流寫法很多人在這一步直接抄錯(cuò)了。Lomuto 劃分思路直觀以末尾元素為基準(zhǔn)用一個(gè)指針從左往右掃把小于基準(zhǔn)的往左邊挪。代碼短、好理解、適合教學(xué)。缺點(diǎn)是交換次數(shù)多每個(gè)小元素都可能觸發(fā)一次交換而且遇到大量重復(fù)元素時(shí)退化嚴(yán)重——全是相等元素時(shí)它會把相等的都丟到一邊劃分極不均勻。Hoare 劃分是原始版本兩個(gè)指針從兩端往中間夾左邊找大于等于基準(zhǔn)的右邊找小于等于基準(zhǔn)的找到就交換。交換次數(shù)平均只有 Lomuto 的三分之一左右而且最終基準(zhǔn)落在中間附近劃分天然更均衡。我選擇 Hoare但必須提醒幾個(gè)坑它的返回值語義是“左段的右端點(diǎn)”不是“基準(zhǔn)的最終位置”。用閉區(qū)間的話劃分結(jié)果是[lo, p]和[p 1, hi]兩段都非空所以不會死循環(huán)。很多人照著某個(gè)博客寫成[lo, p - 1]和[p, hi]然后遞歸無限下去本質(zhì)上就是把語義搞混了。還有一個(gè)邊界安全的問題用do { i; } while (a[i] pivot)這種寫法第一下自增之后立刻讀a[i]看著嚇人。它之所以安全是因?yàn)榛鶞?zhǔn)值本身就在數(shù)組里當(dāng)哨兵——pivot取的是a[lo]右指針j向左掃到lo時(shí)必然停下a[lo] pivot不滿足 pivot此時(shí)i不可能越界。但如果你為了“優(yōu)化”把基準(zhǔn)單獨(dú)拿出來、把a(bǔ)[lo]換成別的值這個(gè)哨兵就沒了越界立刻發(fā)生。我踩過這個(gè)坑改完跑小數(shù)據(jù)沒事跑大數(shù)據(jù)偶發(fā)崩潰定位了很久。3.3 重復(fù)元素處理三路劃分的適用邊界普通二路劃分有個(gè)隱蔽的弱點(diǎn)數(shù)組里如果有大量與基準(zhǔn)相等的元素這些相等元素會被隨機(jī)分到左右兩邊下一層還要繼續(xù)處理它們白做功。極端情況是全部元素相等二路劃分每次都只切掉一個(gè)直接退化成 O(n2)。業(yè)務(wù)數(shù)據(jù)里這種情況比想象中常見。按狀態(tài)字段排序、按等級分組、按布爾標(biāo)記排序取值域都很小重復(fù)率極高。這時(shí)候該上三路劃分荷蘭國旗問題一趟掃描把數(shù)組分成 基準(zhǔn)、 基準(zhǔn)、 基準(zhǔn)三段中間那段直接歸位不再入棧。代價(jià)是三路劃分的常數(shù)比二路大每次比較要做兩次判斷。所以策略是如果數(shù)據(jù)重復(fù)率低二路更快重復(fù)率高三路完勝。怎么判斷如果提前知道數(shù)據(jù)特征就用對應(yīng)的不確定的話二路加三數(shù)取中已經(jīng)夠用只有明確知道取值域很小才上三路。三路劃分在迭代框架里的寫法要小心劃分完得到lt和gt兩個(gè)下標(biāo)左段是[lo, lt - 1]右段是[gt 1, hi]。兩段都可能為空壓棧前必須判空否則空區(qū)間進(jìn)棧后循環(huán)里lo hi直接讀越界。4. 完整實(shí)現(xiàn)與逐段代碼解析4.1 迭代版快速排序的完整代碼下面這份是我自己項(xiàng)目里用的版本注釋寫得比較密可以直接抄。核心結(jié)構(gòu)是外層循環(huán)彈棧內(nèi)層while處理當(dāng)前區(qū)間直到長度低于閾值最后統(tǒng)一走插入排序。#include cassert #include algorithm namespace sortx { constexpr int INSERTION_THRESHOLD 24; // 小區(qū)間切換閾值 constexpr int STACK_CAPACITY 64; // 壓大處理小 深度 log2(n)1 // 閉區(qū)間 [lo, hi] 的插入排序 inline void insertionSort(int* a, int lo, int hi) { for (int i lo 1; i hi; i) { int key a[i]; int j i - 1; while (j lo a[j] key) { a[j 1] a[j]; --j; } a[j 1] key; } } // 三數(shù)取中把中位數(shù)換到 lo 位置當(dāng)基準(zhǔn) inline void medianToFirst(int* a, int lo, int hi) { int mid lo ((hi - lo) 1); if (a[mid] a[lo]) std::swap(a[mid], a[lo]); if (a[hi] a[lo]) std::swap(a[hi], a[lo]); if (a[hi] a[mid]) std::swap(a[hi], a[mid]); std::swap(a[lo], a[mid]); // 中位數(shù)就位 } // Hoare 劃分返回左段的右端點(diǎn) p劃分結(jié)果 [lo, p] 與 [p1, hi] // 前置條件hi - lo 2且 a[lo] 已是三數(shù)取中的結(jié)果 inline int partitionHoare(int* a, int lo, int hi) { const int pivot a[lo]; int i lo - 1; int j hi 1; while (true) { do { i; } while (a[i] pivot); do { --j; } while (a[j] pivot); if (i j) return j; std::swap(a[i], a[j]); } } void quickSort(int* a, int n) { if (n 2) return; int stackLo[STACK_CAPACITY]; int stackHi[STACK_CAPACITY]; int top 0; stackLo[top] 0; stackHi[top] n - 1; top; while (top 0) { --top; int lo stackLo[top]; int hi stackHi[top]; // 當(dāng)前區(qū)間一直劃分直到長度落到閾值以內(nèi) while (hi - lo 1 INSERTION_THRESHOLD) { int p partitionHoare(a, lo, hi); int leftLen p - lo 1; int rightLen hi - p; if (leftLen rightLen) { // 壓右段繼續(xù)處理左段 stackLo[top] p 1; stackHi[top] hi; top; assert(top STACK_CAPACITY); hi p; } else { // 壓左段繼續(xù)處理右段 stackLo[top] lo; stackHi[top] p; top; assert(top STACK_CAPACITY); lo p 1; } } insertionSort(a, lo, hi); } } } // namespace sortx4.2 關(guān)鍵變量與不變式說明這份代碼里有幾個(gè)不變式理解了它們你就能自己改、也不會改錯(cuò)。第一條棧里所有區(qū)間兩兩不相交且覆蓋所有尚未排序的元素。這條保證了正確性——把所有區(qū)間處理完整個(gè)數(shù)組就排好了。如果某次壓棧寫錯(cuò)坐標(biāo)區(qū)間會重疊同一段被排兩次結(jié)果可能是對的白做功或者漏掉某段結(jié)果錯(cuò)但很難發(fā)現(xiàn)。第二條top的峰值不超過log?(n) 1。這條保證了空間安全也是定長數(shù)組能用的依據(jù)。你在調(diào)試時(shí)可以直接在循環(huán)里打印top正常數(shù)據(jù)下它應(yīng)該長期維持在 2 到 30 之間如果看到它一直往上漲比如超過 40說明策略寫反了壓的是小區(qū)間。第三條內(nèi)層while退出時(shí)lo到hi的區(qū)間長度必然不超過閾值。這條是插入排序正確性的前提——插入排序處理的就是這個(gè)殘留的小數(shù)組。如果某次劃分后你忘了更新lo或hi這個(gè)殘留區(qū)間就是錯(cuò)的插入排序會把本來排好的部分?jǐn)噥y。第四條partitionHoare返回的p滿足lo p hi。左邊不等于hi是因?yàn)橹辽僖粢粋€(gè)元素給右段pivot本身在左段否則右段為空、pivot落到右段的邊界上循環(huán)就亂了p不小于lo是因?yàn)樽蠖沃辽俸鶞?zhǔn)一個(gè)元素。這兩個(gè)邊界條件如果被破壞內(nèi)層while就會陷入死循環(huán)而且是很隱蔽的那種。4.3 閾值標(biāo)定與實(shí)測記錄閾值這個(gè)參數(shù)我做過一輪簡單的標(biāo)定環(huán)境是常見的 x86 筆記本編譯器開 -O2數(shù)據(jù)是隨機(jī)打散的 32 位整數(shù)每組跑 20 次取中位數(shù)閾值100 萬元素耗時(shí)1000 萬元素耗時(shí)備注862 ms780 ms劃分次數(shù)偏多收益不明顯1658 ms726 ms接近最優(yōu)2457 ms718 ms我的默認(rèn)值3259 ms735 ms開始下滑插入排序的 O(k2) 拖后腿6466 ms812 ms明顯變慢結(jié)論很平淡16 到 32 都能用24 是我的舒適區(qū)。這里真正想說的不是這個(gè)數(shù)字而是標(biāo)定這件事本身值得做。很多參數(shù)在網(wǎng)上流傳的“最佳值”都是別人在特定硬件、特定編譯器、特定數(shù)據(jù)分布下調(diào)出來的你直接抄過來可能差得遠(yuǎn)?；ǘ昼妼憘€(gè)基準(zhǔn)測試比翻十篇博客靠譜。順帶說一個(gè)實(shí)測中發(fā)現(xiàn)的細(xì)節(jié)對近乎有序的數(shù)據(jù)只有少量元素錯(cuò)位閾值取大一點(diǎn)反而更好因?yàn)榇藭r(shí)劃分本來就均勻插入排序處理長序列的效率比多次劃分高。但如果數(shù)據(jù)是隨機(jī)的閾值取大就會因?yàn)?O(k2) 而吃虧。所以如果你的數(shù)據(jù)特征明確可以針對性調(diào)整不確定就用 24別在這上面耗太久。5. 常見問題與排查實(shí)錄5.1 死循環(huán)與棧溢出的三類典型癥狀癥狀一程序卡住不動(dòng)CPU 占用 100%但沒有任何輸出。十有八九是partitionHoare返回的p越界了導(dǎo)致內(nèi)層while反復(fù)處理同一個(gè)區(qū)間。檢查點(diǎn)劃分結(jié)果到底是[lo, p] / [p1, hi]還是[lo, p-1] / [p, hi]兩種寫法對應(yīng)不同的返回值語義混用必死。我的建議是選定一種之后在注釋里把語義寫死改代碼的人一看就不敢亂動(dòng)。癥狀二數(shù)據(jù)量小時(shí)一切正常數(shù)據(jù)量一大就崩。先查棧容量和壓棧策略。把top打個(gè)日志出來正常應(yīng)該穩(wěn)定在一個(gè)小數(shù)字上波動(dòng)如果看到它單調(diào)遞增到幾十、上百那就是兩邊都壓?；蛘邏盒√幚泶罅?。還有一種可能是assert被關(guān)掉了NDEBUG 定義了溢出被靜默吃掉表現(xiàn)成別的亂象。癥狀三排序結(jié)果大部分正確局部區(qū)間沒排好。這種最磨人。通常是壓棧時(shí)坐標(biāo)寫錯(cuò)比如該壓p 1寫成了p導(dǎo)致某段被重復(fù)處理、另一段被漏掉。排查方法很土但有效在小數(shù)組上比如 20 個(gè)元素加斷言每次彈出區(qū)間后檢查lo hi且區(qū)間不重疊跑幾百組隨機(jī)數(shù)據(jù)問題立刻暴露。5.2 排查速查表現(xiàn)象最可能的原因處理辦法徹底卡死無輸出劃分返回值語義與使用方不一致統(tǒng)一約定并寫注釋加區(qū)間非空斷言大數(shù)據(jù)崩潰小數(shù)據(jù)正常棧深度 O(n) 或定長數(shù)組不夠檢查是否“壓大處理小”打印 top 曲線結(jié)果局部亂序入棧坐標(biāo)錯(cuò)位區(qū)間重疊或遺漏小規(guī)模隨機(jī)數(shù)據(jù)加重疊斷言復(fù)現(xiàn)全體相等時(shí)極慢二路劃分對重復(fù)元素退化換三路劃分或在檢測到重復(fù)時(shí)切換已排序輸入極慢基準(zhǔn)固定取首元素上三數(shù)取中或隨機(jī)化基準(zhǔn)排序結(jié)果尾部有垃圾值插入排序hi參數(shù)傳錯(cuò)檢查內(nèi)層循環(huán)退出后lo/hi是否正確換臺機(jī)器就變慢閾值不適配當(dāng)前硬件重新跑標(biāo)定別迷信固定值5.3 用對拍驗(yàn)證正確性算法改造最怕的是“看起來對”。我現(xiàn)在的習(xí)慣是寫完任何排序都拿std::sort跑對拍生成隨機(jī)長度0 到 500、隨機(jī)內(nèi)容含大量重復(fù)值、全相同、已排序、逆序四種極端分布的數(shù)組跑一千組逐元素比對。這個(gè)習(xí)慣幫我抓到過一個(gè)很隱蔽的 bug三路劃分版本里當(dāng)整個(gè)區(qū)間全部相等時(shí)lt停在lo、gt停在hi左右兩段都為空壓棧前我忘了判空空區(qū)間進(jìn)棧后彈出時(shí)lo hi插入排序的循環(huán)條件i hi不成立直接跳過看起來沒事但下一次彈出的區(qū)間坐標(biāo)已經(jīng)錯(cuò)位了。這種問題在常規(guī)隨機(jī)數(shù)據(jù)下根本不出現(xiàn)只有全相等才觸發(fā)。對拍的另一個(gè)價(jià)值是測邊界長度為 0、1、2、3 的數(shù)組全相同、只有兩個(gè)元素逆序、只有最后一個(gè)元素錯(cuò)位。這些用例手寫不了幾條但用隨機(jī)生成加std::sort對比幾百行代碼就能覆蓋得相當(dāng)全。我建議你在改任何一個(gè)排序?qū)崿F(xiàn)之后第一件事就是把這套對拍搭起來別靠肉眼。最后分享一個(gè)我自己的小技巧迭代版快排調(diào)試的時(shí)候把那個(gè)定長棧數(shù)組的前top個(gè)元素打印出來格式化成[lo, hi]的列表和遞歸版的調(diào)用棧對比著看兩者應(yīng)該完全一致順序可能不同。這個(gè)對比能讓你在十分鐘內(nèi)確認(rèn)自己的迭代改造是不是真的等價(jià)比逐行讀代碼快得多。這個(gè)內(nèi)容往下還能擴(kuò)展的方向是把顯式棧換成一個(gè)可以序列化的結(jié)構(gòu)做到排序中途存檔、跨進(jìn)程續(xù)跑這個(gè)我在分布式場景里用過一次比重跑一遍整個(gè)排序省事不少。