現(xiàn)：顯式棧與棧深度控制優(yōu)化)
排序這塊東西平時(shí)寫業(yè)務(wù)代碼的人很少自己動(dòng)手調(diào)個(gè)庫(kù)函數(shù)就完事了。但只要經(jīng)歷過幾次凌晨被叫起來查問題或者被丟到資源吃緊的環(huán)境里跑程序就會(huì)開始琢磨底層到底發(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í)會(huì)偶發(fā)崩潰日志里看不出任何異常換成非遞歸加顯式棧之后穩(wěn)定跑了兩年。這篇內(nèi)容適合三類人正在啃算法課、想搞清楚系統(tǒng)棧到底存了什么的學(xué)生需要在受限環(huán)境里跑排序的開發(fā)以及已經(jīng)寫出來能跑、但總擔(dān)心邊界和棧深度的讀者。代碼我統(tǒng)一用 C但思路和 Java、Python、Go 完全通用語(yǔ)言只是皮。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è)元素遞歸深度會(huì)退化到 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)場(chǎng)、下次接著跑。第三類風(fēng)險(xiǎn)是可觀測(cè)性差。遞歸深了以后調(diào)試器里棧幀幾十層想知道“現(xiàn)在到底在處理哪個(gè)區(qū)間”非常費(fèi)勁顯式棧就不一樣你把棧內(nèi)容打出來里面就是待處理的區(qū)間列表一眼就能看出卡在哪一段。這一點(diǎn)在排查“排完整體看著對(duì)、局部區(qū)間沒排好”這類詭異問題時(shí)特別有用我后面第 5 章會(huì)詳細(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)狀態(tài)機(jī)那才叫痛苦。快排沒有這個(gè)問題一個(gè)存區(qū)間的數(shù)組就完全等價(jià)。等價(jià)關(guān)系可以這么理解遞歸是運(yùn)行時(shí)替你維護(hù)一個(gè)棧每層壓入“返回后繼續(xù)處理右半段”這層意思非遞歸是你自己維護(hù)一個(gè)數(shù)組顯式地壓入“右半段還沒處理”。前者你只能相信它不出問題后者你可以數(shù)、可以打印、可以斷言、可以限制上限。1.3 什么場(chǎng)景值得上非遞歸不是所有場(chǎng)合都值得改。給你一張我自己整理的判斷表按實(shí)際情況對(duì)號(hào)入座場(chǎng)景特征建議原因數(shù)據(jù)量小于十萬跑在桌面/服務(wù)器保持遞歸代碼短維護(hù)成本低棧深度撐得住數(shù)據(jù)量百萬級(jí)且輸入可能有序必須非遞歸或加隨機(jī)基準(zhǔn)極端輸入下遞歸深度無法預(yù)估運(yùn)行在資源受限環(huán)境強(qiáng)烈建議非遞歸顯式?？梢远ㄩL(zhǎng)預(yù)分配不占運(yùn)行棧需要分批、可中斷執(zhí)行必須非遞歸遞歸無法保存中間狀態(tài)返回排序邏輯本身在熱路徑被頻繁調(diào)用建議非遞歸省掉函數(shù)調(diào)用開銷實(shí)測(cè)有 3%~8% 提升教學(xué)、面試、一次性腳本遞歸可讀性優(yōu)先別過度設(shè)計(jì)那點(diǎn)性能差異是怎么來的省掉了每次調(diào)用的壓棧、跳轉(zhuǎn)、返回但增加了顯式數(shù)組的讀寫。兩者大致抵消非遞歸略占優(yōu)因?yàn)閿?shù)組讀寫是順序的、緩存友好而函數(shù)調(diào)用會(huì)污染指令緩存。別指望靠這個(gè)提速一倍那是想多了。2. 核心設(shè)計(jì)棧里到底該存什么2.1 存區(qū)間下標(biāo)的經(jīng)典方案最直接的方案是壓入一對(duì)下標(biāo)。這里有個(gè)小分歧存左閉右閉的(lo, hi)還是存起點(diǎn)加長(zhǎng)度(lo, len)。兩種都對(duì)我偏好前者因?yàn)楹徒炭茣系倪f歸參數(shù)完全一致改成迭代時(shí)不需要做任何坐標(biāo)換算少一層心算就少一類錯(cuò)誤。用長(zhǎng)度的話每次劃分后要算(lo, p - lo)和(p 1, hi - p)寫起來啰嗦而且hi - lo和hi - lo 1差一個(gè) 1 的地方特別容易錯(cuò)。閉區(qū)間寫法里某一段非空的條件就是lo hi空區(qū)間根本不入棧——這個(gè)判斷簡(jiǎn)單到不會(huì)寫錯(cuò)。用一個(gè)結(jié)構(gòu)體數(shù)組還是兩個(gè)并行數(shù)組小規(guī)模我傾向兩個(gè)int數(shù)組并行避免結(jié)構(gòu)體對(duì)齊帶來的額外填充緩存行利用率也高一點(diǎn)。當(dāng)然這點(diǎn)差異在絕大多數(shù)業(yè)務(wù)里可以忽略別在這上面花太多心思。一個(gè)更省空間的變體是既然hi可以由lo加長(zhǎng)度推出來而長(zhǎng)度在排序過程中只會(huì)變小那確實(shí)能用更少的位數(shù)編碼。但這類優(yōu)化屬于“我已經(jīng)很閑了”級(jí)別除非你的棧真的是瓶頸否則沒必要。2.2 只壓較小區(qū)間加循環(huán)處理大區(qū)間這一節(jié)是全篇最重要的部分也是決定你寫出來的是“假非遞歸”深度仍然是 O(n)還是“真非遞歸”深度 O(log n)的分水嶺。樸素的做法是劃分完左右兩段都?jí)簵！４a看起來對(duì)稱漂亮問題是最壞情況下棧里會(huì)堆積 O(n) 個(gè)區(qū)間——比如輸入已經(jīng)有序、每次劃分只能切掉一個(gè)元素時(shí)每層都?jí)阂粋€(gè)只含一個(gè)元素的區(qū)間棧長(zhǎng)直接線性增長(zhǎng)。你從遞歸棧溢出改成了自己的數(shù)組溢出問題只是從 A 換成了 B。正確解法是尾遞歸消除每次劃分完先處理較短的那一段把較長(zhǎng)的那一段壓棧。為什么這樣管用因?yàn)檠h(huán)變量代表“當(dāng)前正在處理的區(qū)間”它在不斷變小而棧里存的每一個(gè)區(qū)間長(zhǎng)度至少是上一層處理區(qū)間的一半以上。既然每壓一次棧規(guī)模至少翻倍那棧里最多就log?(n)個(gè)元素。推導(dǎo)過程寫清楚一點(diǎn)設(shè)當(dāng)前區(qū)間長(zhǎng)度 m劃分后左段長(zhǎng) a、右段長(zhǎng) b滿足 a b m ? 1扣掉基準(zhǔn)本身占的一位。我們壓入較長(zhǎng)的那段處理較短的那段。那么下一次循環(huán)處理的區(qū)間長(zhǎng)度不超過 (m ? 1)/2。也就是說循環(huán)每轉(zhuǎn)一圈工作區(qū)間至少減半一次。從 n 減到 1最多需要log?(n)輪而每一輪最多往棧里加一個(gè)元素因此棧的峰值深度不超過log?(n) 1。順帶一個(gè)好處較短的那段先處理它的數(shù)據(jù)大概率還在 CPU 緩存里局部性更好。這個(gè)收益在百萬級(jí)數(shù)據(jù)上實(shí)測(cè)能看出一點(diǎn)差別雖然不大。2.3 棧容量上界推導(dǎo)與定長(zhǎng)預(yù)分配有了上面的結(jié)論棧容量就可以算死了。log?(n)在 n 取 232約 43 億時(shí)是 32加 1 是 33。就算你排序 2?? 個(gè)元素現(xiàn)實(shí)中不可能也才 65。所以開一個(gè)長(zhǎng)度 64 的定長(zhǎng)int數(shù)組永遠(yuǎn)不會(huì)溢出。這是我很喜歡的一個(gè)工程細(xì)節(jié)整個(gè)快排迭代版可以做到零動(dòng)態(tài)內(nèi)存分配。不用std::vector、不用new、不用malloc排序過程里一次堆操作都沒有。對(duì)于那些“排序中途絕不能失敗”“不能拋異?！钡膱?chǎng)合比如信號(hào)處理、實(shí)時(shí)控制這一點(diǎn)比性能更有價(jià)值。不過定長(zhǎng)預(yù)分配有個(gè)前提必須是“壓大處理小”策略。如果你改成兩邊都?jí)簵；蛘邏盒√幚泶?4 就完全不夠用了。所以這個(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)固定取首元素的策略在已排序或逆序輸入下會(huì)退化成 O(n2)這個(gè)坑遞歸版會(huì)踩非遞歸版一樣會(huì)踩。三數(shù)取中是最劃算的改進(jìn)代價(jià)是三次比較加一次交換收益是把極端輸入下的劃分質(zhì)量拉回正常水平。具體做法是比較首、中、尾三個(gè)位置的值把中位數(shù)換到首位置當(dāng)基準(zhǔn)。注意這里有個(gè)容易寫錯(cuò)的點(diǎn)三數(shù)取中不是取平均值也不是簡(jiǎn)單取中間位置而是真的把三個(gè)值排序后取中間那個(gè)。小區(qū)間切換閾值是另一個(gè)必加的優(yōu)化。數(shù)組長(zhǎng)度小于某個(gè)門檻時(shí)直接走插入排序不再劃分。原因有三個(gè)小數(shù)組上插入排序的常數(shù)因子遠(yuǎn)小于快排沒有函數(shù)調(diào)用、沒有遞歸、分支預(yù)測(cè)友好快排在長(zhǎng)度只有幾個(gè)元素時(shí)劃分本身就沒什么收益反而白白做了一堆比較插入排序是穩(wěn)定的順序訪問緩存命中率高。門檻取多少市面上的實(shí)現(xiàn)從 8 到 32 都有。我在第 4 章給了一組實(shí)測(cè)數(shù)據(jù)結(jié)論是16 到 24 之間差別很小取 24 稍微穩(wěn)一點(diǎn)。別糾結(jié)這個(gè)數(shù)字差幾個(gè)元素對(duì)整體性能的影響在 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í)它會(huì)把相等的都丟到一邊劃分極不均勻。Hoare 劃分是原始版本兩個(gè)指針從兩端往中間夾左邊找大于等于基準(zhǔn)的右邊找小于等于基準(zhǔn)的找到就交換。交換次數(shù)平均只有 Lomuto 的三分之一左右而且最終基準(zhǔn)落在中間附近劃分天然更均衡。我選擇 Hoare但必須提醒幾個(gè)坑它的返回值語(yǔ)義是“左段的右端點(diǎn)”不是“基準(zhǔn)的最終位置”。用閉區(qū)間的話劃分結(jié)果是[lo, p]和[p 1, hi]兩段都非空所以不會(huì)死循環(huán)。很多人照著某個(gè)博客寫成[lo, p - 1]和[p, hi]然后遞歸無限下去本質(zhì)上就是把語(yǔ)義搞混了。還有一個(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)相等的元素這些相等元素會(huì)被隨機(jī)分到左右兩邊下一層還要繼續(xù)處理它們白做功。極端情況是全部元素相等二路劃分每次都只切掉一個(gè)直接退化成 O(n2)。業(yè)務(wù)數(shù)據(jù)里這種情況比想象中常見。按狀態(tài)字段排序、按等級(jí)分組、按布爾標(biāo)記排序取值域都很小重復(fù)率極高。這時(shí)候該上三路劃分荷蘭國(guó)旗問題一趟掃描把數(shù)組分成 基準(zhǔn)、 基準(zhǔn)、 基準(zhǔn)三段中間那段直接歸位不再入棧。代價(jià)是三路劃分的常數(shù)比二路大每次比較要做兩次判斷。所以策略是如果數(shù)據(jù)重復(fù)率低二路更快重復(fù)率高三路完勝。怎么判斷如果提前知道數(shù)據(jù)特征就用對(duì)應(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ū)間直到長(zhǎng)度低于閾值最后統(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ū)間一直劃分直到長(zhǎng)度落到閾值以內(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è)不變式理解了它們你就能自己改、也不會(huì)改錯(cuò)。第一條棧里所有區(qū)間兩兩不相交且覆蓋所有尚未排序的元素。這條保證了正確性——把所有區(qū)間處理完整個(gè)數(shù)組就排好了。如果某次壓棧寫錯(cuò)坐標(biāo)區(qū)間會(huì)重疊同一段被排兩次結(jié)果可能是對(duì)的白做功或者漏掉某段結(jié)果錯(cuò)但很難發(fā)現(xiàn)。第二條top的峰值不超過log?(n) 1。這條保證了空間安全也是定長(zhǎng)數(shù)組能用的依據(jù)。你在調(diào)試時(shí)可以直接在循環(huán)里打印top正常數(shù)據(jù)下它應(yīng)該長(zhǎng)期維持在 2 到 30 之間如果看到它一直往上漲比如超過 40說明策略寫反了壓的是小區(qū)間。第三條內(nèi)層while退出時(shí)lo到hi的區(qū)間長(zhǎng)度必然不超過閾值。這條是插入排序正確性的前提——插入排序處理的就是這個(gè)殘留的小數(shù)組。如果某次劃分后你忘了更新lo或hi這個(gè)殘留區(qū)間就是錯(cuò)的插入排序會(huì)把本來排好的部分?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ì)陷入死循環(huán)而且是很隱蔽的那種。4.3 閾值標(biāo)定與實(shí)測(cè)記錄閾值這個(gè)參數(shù)我做過一輪簡(jiǎn)單的標(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)測(cè)試比翻十篇博客靠譜。順帶說一個(gè)實(shí)測(cè)中發(fā)現(xiàn)的細(xì)節(jié)對(duì)近乎有序的數(shù)據(jù)只有少量元素錯(cuò)位閾值取大一點(diǎn)反而更好因?yàn)榇藭r(shí)劃分本來就均勻插入排序處理長(zhǎng)序列的效率比多次劃分高。但如果數(shù)據(jù)是隨機(jī)的閾值取大就會(huì)因?yàn)?O(k2) 而吃虧。所以如果你的數(shù)據(jù)特征明確可以針對(duì)性調(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]兩種寫法對(duì)應(yīng)不同的返回值語(yǔ)義混用必死。我的建議是選定一種之后在注釋里把語(yǔ)義寫死改代碼的人一看就不敢亂動(dòng)。癥狀二數(shù)據(jù)量小時(shí)一切正常數(shù)據(jù)量一大就崩。先查棧容量和壓棧策略。把top打個(gè)日志出來正常應(yīng)該穩(wěn)定在一個(gè)小數(shù)字上波動(dòng)如果看到它單調(diào)遞增到幾十、上百那就是兩邊都?jí)簵；蛘邏盒√幚泶罅?。還有一種可能是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)象最可能的原因處理辦法徹底卡死無輸出劃分返回值語(yǔ)義與使用方不一致統(tǒng)一約定并寫注釋加區(qū)間非空斷言大數(shù)據(jù)崩潰小數(shù)據(jù)正常棧深度 O(n) 或定長(zhǎng)數(shù)組不夠檢查是否“壓大處理小”打印 top 曲線結(jié)果局部亂序入棧坐標(biāo)錯(cuò)位區(qū)間重疊或遺漏小規(guī)模隨機(jī)數(shù)據(jù)加重疊斷言復(fù)現(xiàn)全體相等時(shí)極慢二路劃分對(duì)重復(fù)元素退化換三路劃分或在檢測(cè)到重復(fù)時(shí)切換已排序輸入極慢基準(zhǔn)固定取首元素上三數(shù)取中或隨機(jī)化基準(zhǔn)排序結(jié)果尾部有垃圾值插入排序hi參數(shù)傳錯(cuò)檢查內(nèi)層循環(huán)退出后lo/hi是否正確換臺(tái)機(jī)器就變慢閾值不適配當(dāng)前硬件重新跑標(biāo)定別迷信固定值5.3 用對(duì)拍驗(yàn)證正確性算法改造最怕的是“看起來對(duì)”。我現(xiàn)在的習(xí)慣是寫完任何排序都拿std::sort跑對(duì)拍生成隨機(jī)長(zhǎng)度0 到 500、隨機(jī)內(nèi)容含大量重復(fù)值、全相同、已排序、逆序四種極端分布的數(shù)組跑一千組逐元素比對(duì)。這個(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ā)。對(duì)拍的另一個(gè)價(jià)值是測(cè)邊界長(zhǎng)度為 0、1、2、3 的數(shù)組全相同、只有兩個(gè)元素逆序、只有最后一個(gè)元素錯(cuò)位。這些用例手寫不了幾條但用隨機(jī)生成加std::sort對(duì)比幾百行代碼就能覆蓋得相當(dāng)全。我建議你在改任何一個(gè)排序?qū)崿F(xiàn)之后第一件事就是把這套對(duì)拍搭起來別靠肉眼。最后分享一個(gè)我自己的小技巧迭代版快排調(diào)試的時(shí)候把那個(gè)定長(zhǎng)棧數(shù)組的前top個(gè)元素打印出來格式化成[lo, hi]的列表和遞歸版的調(diào)用棧對(duì)比著看兩者應(yīng)該完全一致順序可能不同。這個(gè)對(duì)比能讓你在十分鐘內(nèi)確認(rèn)自己的迭代改造是不是真的等價(jià)比逐行讀代碼快得多。這個(gè)內(nèi)容往下還能擴(kuò)展的方向是把顯式棧換成一個(gè)可以序列化的結(jié)構(gòu)做到排序中途存檔、跨進(jìn)程續(xù)跑這個(gè)我在分布式場(chǎng)景里用過一次比重跑一遍整個(gè)排序省事不少。 快速排序非遞歸實(shí)現(xiàn)：顯式棧與棧深度控制優(yōu)化
排序這塊東西平時(shí)寫業(yè)務(wù)代碼的人很少自己動(dòng)手調(diào)個(gè)庫(kù)函數(shù)就完事了。但只要經(jīng)歷過幾次凌晨被叫起來查問題或者被丟到資源吃緊的環(huán)境里跑程序就會(huì)開始琢磨底層到底發(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í)會(huì)偶發(fā)崩潰日志里看不出任何異常換成非遞歸加顯式棧之后穩(wěn)定跑了兩年。這篇內(nèi)容適合三類人正在啃算法課、想搞清楚系統(tǒng)棧到底存了什么的學(xué)生需要在受限環(huán)境里跑排序的開發(fā)以及已經(jīng)寫出來能跑、但總擔(dān)心邊界和棧深度的讀者。代碼我統(tǒng)一用 C但思路和 Java、Python、Go 完全通用語(yǔ)言只是皮。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è)元素遞歸深度會(huì)退化到 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)場(chǎng)、下次接著跑。第三類風(fēng)險(xiǎn)是可觀測(cè)性差。遞歸深了以后調(diào)試器里棧幀幾十層想知道“現(xiàn)在到底在處理哪個(gè)區(qū)間”非常費(fèi)勁顯式棧就不一樣你把棧內(nèi)容打出來里面就是待處理的區(qū)間列表一眼就能看出卡在哪一段。這一點(diǎn)在排查“排完整體看著對(duì)、局部區(qū)間沒排好”這類詭異問題時(shí)特別有用我后面第 5 章會(huì)詳細(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)狀態(tài)機(jī)那才叫痛苦。快排沒有這個(gè)問題一個(gè)存區(qū)間的數(shù)組就完全等價(jià)。等價(jià)關(guān)系可以這么理解遞歸是運(yùn)行時(shí)替你維護(hù)一個(gè)棧每層壓入“返回后繼續(xù)處理右半段”這層意思非遞歸是你自己維護(hù)一個(gè)數(shù)組顯式地壓入“右半段還沒處理”。前者你只能相信它不出問題后者你可以數(shù)、可以打印、可以斷言、可以限制上限。1.3 什么場(chǎng)景值得上非遞歸不是所有場(chǎng)合都值得改。給你一張我自己整理的判斷表按實(shí)際情況對(duì)號(hào)入座場(chǎng)景特征建議原因數(shù)據(jù)量小于十萬跑在桌面/服務(wù)器保持遞歸代碼短維護(hù)成本低棧深度撐得住數(shù)據(jù)量百萬級(jí)且輸入可能有序必須非遞歸或加隨機(jī)基準(zhǔn)極端輸入下遞歸深度無法預(yù)估運(yùn)行在資源受限環(huán)境強(qiáng)烈建議非遞歸顯式?？梢远ㄩL(zhǎng)預(yù)分配不占運(yùn)行棧需要分批、可中斷執(zhí)行必須非遞歸遞歸無法保存中間狀態(tài)返回排序邏輯本身在熱路徑被頻繁調(diào)用建議非遞歸省掉函數(shù)調(diào)用開銷實(shí)測(cè)有 3%~8% 提升教學(xué)、面試、一次性腳本遞歸可讀性優(yōu)先別過度設(shè)計(jì)那點(diǎn)性能差異是怎么來的省掉了每次調(diào)用的壓棧、跳轉(zhuǎn)、返回但增加了顯式數(shù)組的讀寫。兩者大致抵消非遞歸略占優(yōu)因?yàn)閿?shù)組讀寫是順序的、緩存友好而函數(shù)調(diào)用會(huì)污染指令緩存。別指望靠這個(gè)提速一倍那是想多了。2. 核心設(shè)計(jì)棧里到底該存什么2.1 存區(qū)間下標(biāo)的經(jīng)典方案最直接的方案是壓入一對(duì)下標(biāo)。這里有個(gè)小分歧存左閉右閉的(lo, hi)還是存起點(diǎn)加長(zhǎng)度(lo, len)。兩種都對(duì)我偏好前者因?yàn)楹徒炭茣系倪f歸參數(shù)完全一致改成迭代時(shí)不需要做任何坐標(biāo)換算少一層心算就少一類錯(cuò)誤。用長(zhǎng)度的話每次劃分后要算(lo, p - lo)和(p 1, hi - p)寫起來啰嗦而且hi - lo和hi - lo 1差一個(gè) 1 的地方特別容易錯(cuò)。閉區(qū)間寫法里某一段非空的條件就是lo hi空區(qū)間根本不入棧——這個(gè)判斷簡(jiǎn)單到不會(huì)寫錯(cuò)。用一個(gè)結(jié)構(gòu)體數(shù)組還是兩個(gè)并行數(shù)組小規(guī)模我傾向兩個(gè)int數(shù)組并行避免結(jié)構(gòu)體對(duì)齊帶來的額外填充緩存行利用率也高一點(diǎn)。當(dāng)然這點(diǎn)差異在絕大多數(shù)業(yè)務(wù)里可以忽略別在這上面花太多心思。一個(gè)更省空間的變體是既然hi可以由lo加長(zhǎng)度推出來而長(zhǎng)度在排序過程中只會(huì)變小那確實(shí)能用更少的位數(shù)編碼。但這類優(yōu)化屬于“我已經(jīng)很閑了”級(jí)別除非你的棧真的是瓶頸否則沒必要。2.2 只壓較小區(qū)間加循環(huán)處理大區(qū)間這一節(jié)是全篇最重要的部分也是決定你寫出來的是“假非遞歸”深度仍然是 O(n)還是“真非遞歸”深度 O(log n)的分水嶺。樸素的做法是劃分完左右兩段都?jí)簵！４a看起來對(duì)稱漂亮問題是最壞情況下棧里會(huì)堆積 O(n) 個(gè)區(qū)間——比如輸入已經(jīng)有序、每次劃分只能切掉一個(gè)元素時(shí)每層都?jí)阂粋€(gè)只含一個(gè)元素的區(qū)間棧長(zhǎng)直接線性增長(zhǎng)。你從遞歸棧溢出改成了自己的數(shù)組溢出問題只是從 A 換成了 B。正確解法是尾遞歸消除每次劃分完先處理較短的那一段把較長(zhǎng)的那一段壓棧。為什么這樣管用因?yàn)檠h(huán)變量代表“當(dāng)前正在處理的區(qū)間”它在不斷變小而棧里存的每一個(gè)區(qū)間長(zhǎng)度至少是上一層處理區(qū)間的一半以上。既然每壓一次棧規(guī)模至少翻倍那棧里最多就log?(n)個(gè)元素。推導(dǎo)過程寫清楚一點(diǎn)設(shè)當(dāng)前區(qū)間長(zhǎng)度 m劃分后左段長(zhǎng) a、右段長(zhǎng) b滿足 a b m ? 1扣掉基準(zhǔn)本身占的一位。我們壓入較長(zhǎng)的那段處理較短的那段。那么下一次循環(huán)處理的區(qū)間長(zhǎng)度不超過 (m ? 1)/2。也就是說循環(huán)每轉(zhuǎn)一圈工作區(qū)間至少減半一次。從 n 減到 1最多需要log?(n)輪而每一輪最多往棧里加一個(gè)元素因此棧的峰值深度不超過log?(n) 1。順帶一個(gè)好處較短的那段先處理它的數(shù)據(jù)大概率還在 CPU 緩存里局部性更好。這個(gè)收益在百萬級(jí)數(shù)據(jù)上實(shí)測(cè)能看出一點(diǎn)差別雖然不大。2.3 棧容量上界推導(dǎo)與定長(zhǎng)預(yù)分配有了上面的結(jié)論棧容量就可以算死了。log?(n)在 n 取 232約 43 億時(shí)是 32加 1 是 33。就算你排序 2?? 個(gè)元素現(xiàn)實(shí)中不可能也才 65。所以開一個(gè)長(zhǎng)度 64 的定長(zhǎng)int數(shù)組永遠(yuǎn)不會(huì)溢出。這是我很喜歡的一個(gè)工程細(xì)節(jié)整個(gè)快排迭代版可以做到零動(dòng)態(tài)內(nèi)存分配。不用std::vector、不用new、不用malloc排序過程里一次堆操作都沒有。對(duì)于那些“排序中途絕不能失敗”“不能拋異?！钡膱?chǎng)合比如信號(hào)處理、實(shí)時(shí)控制這一點(diǎn)比性能更有價(jià)值。不過定長(zhǎng)預(yù)分配有個(gè)前提必須是“壓大處理小”策略。如果你改成兩邊都?jí)簵；蛘邏盒√幚泶?4 就完全不夠用了。所以這個(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)固定取首元素的策略在已排序或逆序輸入下會(huì)退化成 O(n2)這個(gè)坑遞歸版會(huì)踩非遞歸版一樣會(huì)踩。三數(shù)取中是最劃算的改進(jìn)代價(jià)是三次比較加一次交換收益是把極端輸入下的劃分質(zhì)量拉回正常水平。具體做法是比較首、中、尾三個(gè)位置的值把中位數(shù)換到首位置當(dāng)基準(zhǔn)。注意這里有個(gè)容易寫錯(cuò)的點(diǎn)三數(shù)取中不是取平均值也不是簡(jiǎn)單取中間位置而是真的把三個(gè)值排序后取中間那個(gè)。小區(qū)間切換閾值是另一個(gè)必加的優(yōu)化。數(shù)組長(zhǎng)度小于某個(gè)門檻時(shí)直接走插入排序不再劃分。原因有三個(gè)小數(shù)組上插入排序的常數(shù)因子遠(yuǎn)小于快排沒有函數(shù)調(diào)用、沒有遞歸、分支預(yù)測(cè)友好快排在長(zhǎng)度只有幾個(gè)元素時(shí)劃分本身就沒什么收益反而白白做了一堆比較插入排序是穩(wěn)定的順序訪問緩存命中率高。門檻取多少市面上的實(shí)現(xiàn)從 8 到 32 都有。我在第 4 章給了一組實(shí)測(cè)數(shù)據(jù)結(jié)論是16 到 24 之間差別很小取 24 稍微穩(wěn)一點(diǎn)。別糾結(jié)這個(gè)數(shù)字差幾個(gè)元素對(duì)整體性能的影響在 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í)它會(huì)把相等的都丟到一邊劃分極不均勻。Hoare 劃分是原始版本兩個(gè)指針從兩端往中間夾左邊找大于等于基準(zhǔn)的右邊找小于等于基準(zhǔn)的找到就交換。交換次數(shù)平均只有 Lomuto 的三分之一左右而且最終基準(zhǔn)落在中間附近劃分天然更均衡。我選擇 Hoare但必須提醒幾個(gè)坑它的返回值語(yǔ)義是“左段的右端點(diǎn)”不是“基準(zhǔn)的最終位置”。用閉區(qū)間的話劃分結(jié)果是[lo, p]和[p 1, hi]兩段都非空所以不會(huì)死循環(huán)。很多人照著某個(gè)博客寫成[lo, p - 1]和[p, hi]然后遞歸無限下去本質(zhì)上就是把語(yǔ)義搞混了。還有一個(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)相等的元素這些相等元素會(huì)被隨機(jī)分到左右兩邊下一層還要繼續(xù)處理它們白做功。極端情況是全部元素相等二路劃分每次都只切掉一個(gè)直接退化成 O(n2)。業(yè)務(wù)數(shù)據(jù)里這種情況比想象中常見。按狀態(tài)字段排序、按等級(jí)分組、按布爾標(biāo)記排序取值域都很小重復(fù)率極高。這時(shí)候該上三路劃分荷蘭國(guó)旗問題一趟掃描把數(shù)組分成 基準(zhǔn)、 基準(zhǔn)、 基準(zhǔn)三段中間那段直接歸位不再入棧。代價(jià)是三路劃分的常數(shù)比二路大每次比較要做兩次判斷。所以策略是如果數(shù)據(jù)重復(fù)率低二路更快重復(fù)率高三路完勝。怎么判斷如果提前知道數(shù)據(jù)特征就用對(duì)應(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ū)間直到長(zhǎng)度低于閾值最后統(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ū)間一直劃分直到長(zhǎng)度落到閾值以內(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è)不變式理解了它們你就能自己改、也不會(huì)改錯(cuò)。第一條棧里所有區(qū)間兩兩不相交且覆蓋所有尚未排序的元素。這條保證了正確性——把所有區(qū)間處理完整個(gè)數(shù)組就排好了。如果某次壓棧寫錯(cuò)坐標(biāo)區(qū)間會(huì)重疊同一段被排兩次結(jié)果可能是對(duì)的白做功或者漏掉某段結(jié)果錯(cuò)但很難發(fā)現(xiàn)。第二條top的峰值不超過log?(n) 1。這條保證了空間安全也是定長(zhǎng)數(shù)組能用的依據(jù)。你在調(diào)試時(shí)可以直接在循環(huán)里打印top正常數(shù)據(jù)下它應(yīng)該長(zhǎng)期維持在 2 到 30 之間如果看到它一直往上漲比如超過 40說明策略寫反了壓的是小區(qū)間。第三條內(nèi)層while退出時(shí)lo到hi的區(qū)間長(zhǎng)度必然不超過閾值。這條是插入排序正確性的前提——插入排序處理的就是這個(gè)殘留的小數(shù)組。如果某次劃分后你忘了更新lo或hi這個(gè)殘留區(qū)間就是錯(cuò)的插入排序會(huì)把本來排好的部分?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ì)陷入死循環(huán)而且是很隱蔽的那種。4.3 閾值標(biāo)定與實(shí)測(cè)記錄閾值這個(gè)參數(shù)我做過一輪簡(jiǎn)單的標(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)測(cè)試比翻十篇博客靠譜。順帶說一個(gè)實(shí)測(cè)中發(fā)現(xiàn)的細(xì)節(jié)對(duì)近乎有序的數(shù)據(jù)只有少量元素錯(cuò)位閾值取大一點(diǎn)反而更好因?yàn)榇藭r(shí)劃分本來就均勻插入排序處理長(zhǎng)序列的效率比多次劃分高。但如果數(shù)據(jù)是隨機(jī)的閾值取大就會(huì)因?yàn)?O(k2) 而吃虧。所以如果你的數(shù)據(jù)特征明確可以針對(duì)性調(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]兩種寫法對(duì)應(yīng)不同的返回值語(yǔ)義混用必死。我的建議是選定一種之后在注釋里把語(yǔ)義寫死改代碼的人一看就不敢亂動(dòng)。癥狀二數(shù)據(jù)量小時(shí)一切正常數(shù)據(jù)量一大就崩。先查棧容量和壓棧策略。把top打個(gè)日志出來正常應(yīng)該穩(wěn)定在一個(gè)小數(shù)字上波動(dòng)如果看到它單調(diào)遞增到幾十、上百那就是兩邊都?jí)簵；蛘邏盒√幚泶罅?。還有一種可能是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)象最可能的原因處理辦法徹底卡死無輸出劃分返回值語(yǔ)義與使用方不一致統(tǒng)一約定并寫注釋加區(qū)間非空斷言大數(shù)據(jù)崩潰小數(shù)據(jù)正常棧深度 O(n) 或定長(zhǎng)數(shù)組不夠檢查是否“壓大處理小”打印 top 曲線結(jié)果局部亂序入棧坐標(biāo)錯(cuò)位區(qū)間重疊或遺漏小規(guī)模隨機(jī)數(shù)據(jù)加重疊斷言復(fù)現(xiàn)全體相等時(shí)極慢二路劃分對(duì)重復(fù)元素退化換三路劃分或在檢測(cè)到重復(fù)時(shí)切換已排序輸入極慢基準(zhǔn)固定取首元素上三數(shù)取中或隨機(jī)化基準(zhǔn)排序結(jié)果尾部有垃圾值插入排序hi參數(shù)傳錯(cuò)檢查內(nèi)層循環(huán)退出后lo/hi是否正確換臺(tái)機(jī)器就變慢閾值不適配當(dāng)前硬件重新跑標(biāo)定別迷信固定值5.3 用對(duì)拍驗(yàn)證正確性算法改造最怕的是“看起來對(duì)”。我現(xiàn)在的習(xí)慣是寫完任何排序都拿std::sort跑對(duì)拍生成隨機(jī)長(zhǎng)度0 到 500、隨機(jī)內(nèi)容含大量重復(fù)值、全相同、已排序、逆序四種極端分布的數(shù)組跑一千組逐元素比對(duì)。這個(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ā)。對(duì)拍的另一個(gè)價(jià)值是測(cè)邊界長(zhǎng)度為 0、1、2、3 的數(shù)組全相同、只有兩個(gè)元素逆序、只有最后一個(gè)元素錯(cuò)位。這些用例手寫不了幾條但用隨機(jī)生成加std::sort對(duì)比幾百行代碼就能覆蓋得相當(dāng)全。我建議你在改任何一個(gè)排序?qū)崿F(xiàn)之后第一件事就是把這套對(duì)拍搭起來別靠肉眼。最后分享一個(gè)我自己的小技巧迭代版快排調(diào)試的時(shí)候把那個(gè)定長(zhǎng)棧數(shù)組的前top個(gè)元素打印出來格式化成[lo, hi]的列表和遞歸版的調(diào)用棧對(duì)比著看兩者應(yīng)該完全一致順序可能不同。這個(gè)對(duì)比能讓你在十分鐘內(nèi)確認(rèn)自己的迭代改造是不是真的等價(jià)比逐行讀代碼快得多。這個(gè)內(nèi)容往下還能擴(kuò)展的方向是把顯式棧換成一個(gè)可以序列化的結(jié)構(gòu)做到排序中途存檔、跨進(jìn)程續(xù)跑這個(gè)我在分布式場(chǎng)景里用過一次比重跑一遍整個(gè)排序省事不少。