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