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