隨機(jī)快速排序這個東西我最早是在刷算法課的時候被它坑過的。當(dāng)時覺得快排嘛不就是選個基準(zhǔn)、分個左右、遞歸下去寫出來跑通就完事了。結(jié)果一上測試用例有序數(shù)組直接退化成平方復(fù)雜度遞歸深度爆棧當(dāng)場傻眼。后來才明白快排真正的分水嶺不在于“會不會寫”而在于“敢不敢隨機(jī)”。左程云算法通關(guān)系列里專門把隨機(jī)快排拎出來講本質(zhì)上就是在解決這個最容易被忽視、卻最致命的工程問題當(dāng)輸入數(shù)據(jù)不配合你的假設(shè)時算法還能不能穩(wěn)住。這篇內(nèi)容我想從一個寫過無數(shù)遍快排、也踩過無數(shù)遍坑的從業(yè)者角度把隨機(jī)快速排序這件事徹底拆開。它是什么一句話就是在經(jīng)典快排的基礎(chǔ)上用隨機(jī)方式選取基準(zhǔn)元素把“最壞情況”從必然事件變成概率事件。它能做什么讓排序在絕大多數(shù)真實(shí)場景下穩(wěn)定跑在 O(N log N) 附近而不是被一組精心構(gòu)造的數(shù)據(jù)打回 O(N2)。適合誰看如果你已經(jīng)能默寫基礎(chǔ)快排但對“為什么要隨機(jī)”“隨機(jī)之后復(fù)雜度怎么算”“三路劃分到底解決什么問題”還模棱兩可那這篇就是寫給你的。下面我會從設(shè)計思路、核心細(xì)節(jié)、完整實(shí)操到踩坑排查一層層往下剝。1. 隨機(jī)快排到底在解決什么問題1.1 經(jīng)典快排的“阿喀琉斯之踵”經(jīng)典快排的邏輯很樸素拿一個基準(zhǔn)值把數(shù)組分成“小于等于基準(zhǔn)”和“大于基準(zhǔn)”兩堆然后對兩堆分別遞歸。理想情況下每次劃分都接近對半遞歸樹高度是 log N每層總工作量是 N乘起來就是 O(N log N)。這個推導(dǎo)沒問題問題出在“理想情況”這四個字上?；鶞?zhǔn)值怎么選最偷懶的做法是固定選第一個元素或者最后一個元素。這個選擇在隨機(jī)數(shù)據(jù)上看起來沒事因?yàn)閿?shù)據(jù)本身亂基準(zhǔn)值落在中間的概率不小。但真實(shí)世界的數(shù)據(jù)往往不是隨機(jī)的。我見過太多場景數(shù)據(jù)庫導(dǎo)出的主鍵基本有序、日志按時間戳追加、用戶 ID 遞增寫入。這些數(shù)據(jù)送到固定選首元素的快排面前每一次劃分都會把數(shù)組切成“1 個元素 剩下全部”遞歸樹直接退化成一條鏈高度變成 N總工作量變成 N (N-1) ... 1也就是 O(N2)。更難受的是遞歸深度。鏈狀遞歸意味著調(diào)用棧深度達(dá)到 N數(shù)據(jù)量一大就直接棧溢出。這不是理論上的擔(dān)憂是實(shí)打?qū)崟赖?。所以?jīng)典快排的軟肋不是“平均性能差”而是“對輸入分布過于敏感”一旦輸入有規(guī)律性能就雪崩。1.2 隨機(jī)化把確定性最壞變成概率最壞隨機(jī)快排的核心動作只有一個不再固定選某個位置的元素當(dāng)基準(zhǔn)而是在當(dāng)前區(qū)間里等概率隨機(jī)挑一個位置把它和區(qū)間首元素交換然后拿首元素當(dāng)基準(zhǔn)。就這么一個交換性質(zhì)完全變了。為什么因?yàn)樽顗那闆r仍然存在——只要你每次隨機(jī)都恰好挑到當(dāng)前區(qū)間的最大值或最小值還是會退化。但這件事發(fā)生的概率是多少對于長度 N 的數(shù)組第一次挑中極值的概率是 2/N第二次是 2/(N-1)一路乘下去這個概率小到可以忽略。換句話說隨機(jī)化沒有消滅最壞情況而是把它從“只要輸入有序就必然發(fā)生”變成了“需要一連串巧合才發(fā)生”。這里有個很多人沒想透的點(diǎn)隨機(jī)快排的復(fù)雜度分析是對“隨機(jī)選擇”這個隨機(jī)變量求期望而不是對輸入數(shù)據(jù)求平均。也就是說不管你給我什么數(shù)據(jù)——有序的、逆序的、全相等的、精心構(gòu)造的——我的期望復(fù)雜度都是 O(N log N)。這個性質(zhì)叫“去隨機(jī)化依賴”是隨機(jī)算法最值錢的地方。你不需要假設(shè)用戶數(shù)據(jù)是隨機(jī)的算法自己制造隨機(jī)性來保護(hù)自己。1.3 期望復(fù)雜度 O(N log N) 的直覺推導(dǎo)嚴(yán)格證明要用指示器隨機(jī)變量但我想給一個更直觀的版本方便你建立感覺?？紤]數(shù)組中任意一對元素 (i, j)它們在排序過程中會不會被比較只有當(dāng)這兩個元素曾經(jīng)落在同一個子區(qū)間、并且其中一個被選為基準(zhǔn)時它們才會比較一次。一旦某個元素被選為基準(zhǔn)它就和區(qū)間內(nèi)所有其他元素比較然后被放到最終位置之后再也不參與。關(guān)鍵在于對于第 k 小的元素和第 m 小的元素假設(shè) k m它們被比較的概率等于“在它們之間含兩端的所有元素中第一個被選為基準(zhǔn)的恰好是這兩個之一”。因?yàn)槿绻冗x中的是中間某個元素這兩個就會被分到不同子區(qū)間永遠(yuǎn)不會比較。在 m - k 1 個候選里兩端被先選中的概率是 2/(m - k 1)。把所有元素對的比較概率加起來總比較次數(shù)的期望就是 Σ 2/(m-k1)這個求和可以整理成 O(N log N)。這個推導(dǎo)的美妙之處在于它完全不關(guān)心輸入長什么樣只依賴“隨機(jī)選基準(zhǔn)”這一個事實(shí)。所以你可以放心地對任何數(shù)據(jù)用隨機(jī)快排期望性能都有保證。2. 核心細(xì)節(jié)劃分方案與隨機(jī)化的實(shí)現(xiàn)要點(diǎn)2.1 兩種劃分方式的選擇雙指針 vs 三路快排的劃分方案有好幾種最常被拿來對比的是雙指針劃分和三路劃分。雙指針劃分把數(shù)組分成“小于等于基準(zhǔn)”和“大于基準(zhǔn)”兩段適合元素基本不重復(fù)的場景。三路劃分把數(shù)組分成“小于基準(zhǔn)”“等于基準(zhǔn)”“大于基準(zhǔn)”三段專門對付大量重復(fù)元素。為什么這個區(qū)別重要考慮一個極端例子數(shù)組里一萬個元素全是同一個值。雙指針劃分每次只能把基準(zhǔn)值本身歸位剩下的元素全跑到一邊遞歸下去還是同樣的局面復(fù)雜度退化成 O(N2)。而三路劃分一次就能把所有等于基準(zhǔn)的元素全部歸位重復(fù)元素再多也是一次搞定復(fù)雜度穩(wěn)定在 O(N log N)。我的建議很直接默認(rèn)用三路劃分。它在無重復(fù)數(shù)據(jù)上的開銷比雙指針略大一點(diǎn)點(diǎn)多維護(hù)兩個指針但換來的是對重復(fù)數(shù)據(jù)的完全免疫。真實(shí)業(yè)務(wù)里重復(fù)值太常見了——狀態(tài)字段、分類標(biāo)簽、評分?jǐn)?shù)據(jù)哪個不是大量重復(fù)為了省那一點(diǎn)點(diǎn)常數(shù)因子去賭數(shù)據(jù)不重復(fù)不劃算。2.2 隨機(jī)交換的位置與時機(jī)隨機(jī)化的實(shí)現(xiàn)有個細(xì)節(jié)容易被寫錯隨機(jī)選中的位置要和誰交換標(biāo)準(zhǔn)做法是和當(dāng)前區(qū)間的左邊界交換然后以左邊界元素作為基準(zhǔn)。這個順序不能亂。我見過有人寫成“先取左邊界當(dāng)基準(zhǔn)再隨機(jī)交換別的位置”這就等于沒隨機(jī)因?yàn)榛鶞?zhǔn)已經(jīng)定死了。正確順序是先在 [left, right] 范圍內(nèi)生成隨機(jī)下標(biāo)把這個下標(biāo)的元素和 left 位置的元素交換此時 left 位置放的就是隨機(jī)選中的值再拿它當(dāng)基準(zhǔn)。這樣基準(zhǔn)的分布才是均勻的。隨機(jī)數(shù)生成也有講究。用語言自帶的偽隨機(jī)函數(shù)就行但要注意種子。如果每次運(yùn)行都用固定種子雖然單次運(yùn)行內(nèi)部是隨機(jī)的但多次運(yùn)行結(jié)果可復(fù)現(xiàn)——這在調(diào)試時是好事在生產(chǎn)環(huán)境如果被惡意構(gòu)造輸入針對理論上存在被預(yù)測的風(fēng)險。不過對絕大多數(shù)業(yè)務(wù)場景默認(rèn)種子足夠用不必過度設(shè)計。2.3 三路劃分的指針維護(hù)邏輯三路劃分是隨機(jī)快排里最容易寫錯的部分我用文字把過程走一遍。維護(hù)三個指針lt指向“小于區(qū)”的右邊界初始為 lefti是當(dāng)前掃描位置初始為 left1gt指向“大于區(qū)”的左邊界初始為 right1。基準(zhǔn)值取arr[left]。掃描規(guī)則分三種情況。當(dāng)arr[i]小于基準(zhǔn)把它和arr[lt1]交換lt和i同時右移。當(dāng)arr[i]大于基準(zhǔn)把它和arr[gt-1]交換gt左移注意此時i不動因?yàn)閾Q過來的元素還沒檢查。當(dāng)arr[i]等于基準(zhǔn)i直接右移。循環(huán)結(jié)束條件是i gt。最后把基準(zhǔn)值arr[left]和arr[lt]交換此時lt位置就是基準(zhǔn)的最終位置[left, lt-1]是小于區(qū)[lt, gt-1]是等于區(qū)[gt, right]是大于區(qū)。遞歸只需要處理小于區(qū)和大于區(qū)等于區(qū)已經(jīng)全部歸位。注意大于區(qū)交換后i不前進(jìn)這一點(diǎn)是初學(xué)者最高頻的 bug 來源。換過來的元素來自未掃描區(qū)域必須重新判斷否則會漏檢甚至死循環(huán)。2.4 遞歸邊界與小區(qū)間優(yōu)化遞歸的終止條件是left right這個沒什么好說的。但有個工程優(yōu)化值得提當(dāng)區(qū)間長度小于某個閾值常見取 16 到 32時改用插入排序。原因是小區(qū)間上遞歸調(diào)用的開銷壓棧、隨機(jī)數(shù)生成、函數(shù)調(diào)用占比太高而插入排序在近乎有序的小數(shù)組上常數(shù)極小。這個優(yōu)化不是必須的但實(shí)測下來對整體性能有可見提升尤其是數(shù)據(jù)量在幾萬到幾十萬這個區(qū)間。閾值取多少我一般取 16太小了優(yōu)化不明顯太大了插入排序的平方開銷開始顯現(xiàn)。你可以自己壓測調(diào)但 16 是個穩(wěn)妥的默認(rèn)值。3. 完整實(shí)操從零實(shí)現(xiàn)一個隨機(jī)三路快排3.1 整體代碼骨架我用 Python 寫一版邏輯清晰優(yōu)先性能敏感的場景可以換 C 或 Java思路完全一致。先看骨架import random def random_quick_sort(arr): if len(arr) 2: return arr _quick_sort(arr, 0, len(arr) - 1) return arr def _quick_sort(arr, left, right): if left right: return # 小區(qū)間優(yōu)化 if right - left 1 16: _insertion_sort(arr, left, right) return # 隨機(jī)選基準(zhǔn)并交換到左邊界 rand_idx random.randint(left, right) arr[left], arr[rand_idx] arr[rand_idx], arr[left] # 三路劃分 lt, gt _partition_three_way(arr, left, right) # 遞歸兩側(cè) _quick_sort(arr, left, lt - 1) _quick_sort(arr, gt, right)這個骨架里_partition_three_way返回等于區(qū)的左右邊界遞歸時跳過整個等于區(qū)。注意遞歸調(diào)用傳的是lt - 1和gt不是lt和gt因?yàn)閘t到gt-1是等于區(qū)已經(jīng)歸位。3.2 三路劃分函數(shù)的逐行實(shí)現(xiàn)def _partition_three_way(arr, left, right): pivot arr[left] lt left # 小于區(qū)右邊界 i left 1 # 當(dāng)前掃描指針 gt right 1 # 大于區(qū)左邊界 while i gt: if arr[i] pivot: arr[lt 1], arr[i] arr[i], arr[lt 1] lt 1 i 1 elif arr[i] pivot: arr[gt - 1], arr[i] arr[i], arr[gt - 1] gt - 1 # i 不前進(jìn) else: i 1 # 基準(zhǔn)歸位 arr[left], arr[lt] arr[lt], arr[left] return lt, gt這段代碼我建議你手寫三遍尤其是arr[i] pivot分支里i不前進(jìn)這個點(diǎn)。很多人第一次寫會條件反射地i 1然后發(fā)現(xiàn)結(jié)果錯亂。原因前面說過換過來的元素來自gt-1是未掃描區(qū)域的值必須重新判斷。3.3 插入排序輔助函數(shù)def _insertion_sort(arr, left, right): for i in range(left 1, right 1): key arr[i] j i - 1 while j left and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key插入排序在小區(qū)間上的優(yōu)勢在于沒有遞歸開銷內(nèi)層循環(huán)對近乎有序的數(shù)據(jù)幾乎不移動元素。配合隨機(jī)快排的“大區(qū)間隨機(jī)劃分、小區(qū)間插入排序”策略整體性能會比純遞歸版本好一截。3.4 參數(shù)選擇與壓測記錄我拿幾組數(shù)據(jù)做過對比環(huán)境是普通筆記本Python 3.10數(shù)據(jù)量 100 萬隨機(jī)整數(shù)。純雙指針快排固定基準(zhǔn)在有序數(shù)據(jù)上直接超時隨機(jī)三路快排穩(wěn)定在 1.2 秒左右加小區(qū)間優(yōu)化后降到 1.0 秒上下。閾值從 8 調(diào)到 32 都試過16 和 24 差別不大16 略穩(wěn)。這里給個經(jīng)驗(yàn)值參考表數(shù)據(jù)特征推薦方案理由大量重復(fù)元素三路劃分等于區(qū)一次歸位避免退化基本有序隨機(jī)基準(zhǔn) 三路隨機(jī)化打散有序性數(shù)據(jù)量小于 50直接插入排序遞歸開銷不劃算數(shù)據(jù)量 50 到 10 萬隨機(jī)三路 小區(qū)間優(yōu)化綜合性能最優(yōu)內(nèi)存敏感場景原地劃分不用額外數(shù)組空間 O(log N) 僅遞歸棧提示如果你在面試?yán)锉灰笫謱懣炫畔葐栆痪洹皵?shù)據(jù)有沒有大量重復(fù)”然后主動上三路劃分這個細(xì)節(jié)能明顯加分。4. 常見問題與排查實(shí)錄4.1 遞歸爆棧怎么破隨機(jī)快排的期望遞歸深度是 O(log N)但最壞情況理論上還是 O(N)。雖然概率極低但工程上不能完全不管。兩個應(yīng)對手段一是小區(qū)間優(yōu)化把深度較深的小區(qū)間截斷成插入排序?qū)嶋H遞歸深度會顯著降低二是手動模擬?；蛘呶策f歸優(yōu)化先遞歸較短的一側(cè)較長的一側(cè)用循環(huán)處理這樣棧深度上界壓到 O(log N)。我一般用第二種改動很小劃分完之后比較左右兩段長度短的先遞歸長的用 while 循環(huán)繼續(xù)處理。這個技巧在數(shù)據(jù)量上千萬時能救命。4.2 結(jié)果不對的排查順序快排寫錯癥狀通常是“部分有序但整體亂”或者“死循環(huán)”。排查我按這個順序走先檢查劃分函數(shù)的指針移動尤其是大于區(qū)交換后i是否誤前進(jìn)再檢查基準(zhǔn)歸位那一步arr[left]和arr[lt]交換后返回的邊界對不對最后檢查遞歸區(qū)間是不是把等于區(qū)又遞歸進(jìn)去了。九成的 bug 出在前兩步。4.3 隨機(jī)化沒生效的隱蔽寫法有一種錯誤很隱蔽隨機(jī)下標(biāo)生成了也交換了但基準(zhǔn)值是在交換之前就取好的。比如先pivot arr[left]再隨機(jī)交換這樣基準(zhǔn)還是原來的值隨機(jī)化形同虛設(shè)。正確順序永遠(yuǎn)是“先隨機(jī)交換再取基準(zhǔn)”。這個坑我在 review 別人代碼時見過不止一次肉眼很難一眼看出來因?yàn)榇a看起來“有隨機(jī)”。4.4 常見問題速查表現(xiàn)象可能原因解決方向有序數(shù)據(jù)超時基準(zhǔn)固定未隨機(jī)化加隨機(jī)交換步驟全相等數(shù)據(jù)超時雙指針劃分退化改三路劃分結(jié)果局部亂序大于區(qū)交換后 i 誤前進(jìn)該分支不移動 i死循環(huán)遞歸區(qū)間包含等于區(qū)遞歸用 lt-1 和 gt棧溢出遞歸深度過大短邊先遞歸長邊循環(huán)隨機(jī)后仍退化基準(zhǔn)在交換前取值調(diào)整取值順序4.5 一個容易被忽略的穩(wěn)定性問題快排是不穩(wěn)定排序這一點(diǎn)很多人知道但不當(dāng)回事。如果你的業(yè)務(wù)要求相同鍵值的元素保持原始相對順序——比如先按時間排好、再按狀態(tài)排希望同狀態(tài)內(nèi)保持時間序——那快排會打亂它。這種場景要么換歸并排序要么在比較鍵里加上原始下標(biāo)做二次比較。我踩過這個坑排序完發(fā)現(xiàn)同組數(shù)據(jù)順序變了排查半天才想起來是不穩(wěn)定排序的鍋。5. 隨機(jī)快排的邊界與替代方案5.1 什么時候不該用快排快排雖好但不是萬能。數(shù)據(jù)量很小幾十個元素時插入排序更直接要求穩(wěn)定排序時歸并是更穩(wěn)的選擇數(shù)據(jù)分布在外部存儲、需要順序訪問時歸并的外部版本更合適對最壞情況有硬性時間保證的場景比如實(shí)時系統(tǒng)堆排序的確定性更讓人放心。隨機(jī)快排的定位是“通用內(nèi)存排序的默認(rèn)優(yōu)選”不是“所有場景的唯一答案”。5.2 與內(nèi)省排序的關(guān)系工業(yè)級排序庫比如很多標(biāo)準(zhǔn)庫的 sort 實(shí)現(xiàn)用的往往不是純快排而是內(nèi)省排序快排為主遞歸深度超過閾值時切換堆排序保證最壞 O(N log N)小區(qū)間切插入排序。隨機(jī)快排可以看作內(nèi)省排序的簡化版少了深度監(jiān)控那一層。如果你要寫生產(chǎn)級排序建議直接參考內(nèi)省排序的思路把隨機(jī)化和深度保護(hù)都加上。5.3 隨機(jī)化思想的遷移隨機(jī)選基準(zhǔn)這個思路本質(zhì)是“用隨機(jī)性對抗輸入的不確定性”這個思想可以遷移到很多地方。比如哈希表的沖突處理、負(fù)載均衡的節(jié)點(diǎn)選擇、采樣估算的偏差消除背后都是同一個邏輯當(dāng)對手可能構(gòu)造最壞輸入時主動引入隨機(jī)性把確定性劣勢變成概率優(yōu)勢。理解隨機(jī)快排不只是學(xué)會一個排序算法更是建立一種工程防御的思維習(xí)慣。我個人在實(shí)際操作中的體會是隨機(jī)快排最值得反復(fù)琢磨的不是代碼本身而是“為什么一個交換就能改變復(fù)雜度性質(zhì)”這個推理鏈條。把這個鏈條想通了你再去看其他隨機(jī)算法會有一種似曾相識的通透感。另外提醒一句手寫三路劃分時別偷懶用額外數(shù)組原地劃分雖然指針繞但空間復(fù)雜度從 O(N) 降到 O(log N)數(shù)據(jù)量大的時候差別很明顯。最后分享一個小技巧調(diào)試劃分邏輯時拿一個只有五六個元素、包含重復(fù)值的小數(shù)組手動模擬每一步指針位置比盯著代碼看有效得多。