搞排序這么多年我養(yǎng)成了個習(xí)慣接到排序任務(wù)先不急著寫代碼而是先把指標(biāo)列出來。排序指標(biāo)這東西本質(zhì)上就是翻譯層——業(yè)務(wù)需求里“差不多就行”“必須穩(wěn)”“內(nèi)存不夠了”這些模糊表達只有翻譯成具體的算法指標(biāo)才能在算法表里找到對應(yīng)答案。這個“排序之指標(biāo)集錦”系列我打算把排序相關(guān)的核心指標(biāo)系統(tǒng)整理一遍系列1先聚焦最硬核的三個維度時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性順帶把容易被忽略的比較次數(shù)、交換次數(shù)、自適應(yīng)性這些“軟指標(biāo)”也聊透。適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的同學(xué)也適合寫業(yè)務(wù)代碼時遇到排序性能瓶頸、想搞明白“為什么不能用這個算法”的開發(fā)者。1. 排序指標(biāo)這個“江湖”里到底有多少把尺子1.1 先分清“硬指標(biāo)”和“軟指標(biāo)”兩大層排序指標(biāo)不是一個單數(shù)概念而是一整套評估體系。我習(xí)慣把所有指標(biāo)分成兩層。第一層是硬指標(biāo)就是教科書上寫的那幾個時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性。這三個指標(biāo)是算法教材的核心也是面試官最愛問的。它們的共性是——不依賴具體硬件、不依賴具體數(shù)據(jù)分布是理論上可以嚴(yán)格證明的量。比如任何基于比較的排序平均時間復(fù)雜度下界就是O(n log n)這件事不管你用什么語言、什么機器都繞不過去。第二層是軟指標(biāo)教材不常講但工程上非常要命比較次數(shù)、交換次數(shù)、緩存友好性、自適應(yīng)性、遞歸深度。這些指標(biāo)看著不起眼但實際跑起來對性能的影響有時候比時間復(fù)雜度還大。我舉一個例子堆排序的時間復(fù)雜度是穩(wěn)定的O(n log n)理論上和快排一個級別但實際工程里堆排序經(jīng)常比快排慢兩三倍原因就是它訪問內(nèi)存的方式是跳躍式的緩存命中率極低。這就是軟指標(biāo)在起作用。1.2 五大核心指標(biāo)一句話速覽為了避免一上來被各種術(shù)語繞暈我先把排序指標(biāo)里繞不開的五項用一句話說清楚。時間復(fù)雜度算法執(zhí)行耗時隨數(shù)據(jù)規(guī)模n的增長趨勢分為最好、平均、最壞三種情況?？臻g復(fù)雜度算法執(zhí)行過程中額外占用的內(nèi)存量是否允許原地排序。穩(wěn)定性值相等的元素排序后是否保持原有相對順序。比較次數(shù)整個排序過程中元素兩兩比較的總次數(shù)。當(dāng)比較操作昂貴時比如比較對象是復(fù)雜結(jié)構(gòu)體它比時間復(fù)雜度更貼近真實耗時。交換/移動次數(shù)元素在內(nèi)存中被搬移的次數(shù)。當(dāng)賦值操作昂貴時比如元素是超大結(jié)構(gòu)體這個指標(biāo)直接決定性能。另外還有兩個“進階指標(biāo)”自適應(yīng)性數(shù)據(jù)越接近有序排序越快和緩存友好性內(nèi)存訪問是否順序局部連續(xù)這兩項后面我會用專門章節(jié)展開。1.3 指標(biāo)從來不是孤立的它們會互相拉扯選排序算法最坑的一點是沒有任何一個指標(biāo)可以單獨決定選型指標(biāo)之間常?；ハ鄾_突。想要穩(wěn)定排序往往就得付出額外空間想要原地排序快排和堆排序都能做到但快排不穩(wěn)定堆排序雖然穩(wěn)定但不快……原地歸并排序理論上是能同時滿足穩(wěn)定和O(1)空間的但常數(shù)大到工程上沒人用。所以選型本質(zhì)上是“在約束條件下做權(quán)衡”而不是“挑一個最好的算法”因為根本不存在全方位無短板的排序算法。這個觀點我后面會反復(fù)提到也是整個系列的核心方法論先列指標(biāo)再看約束最后才談算法。2. 時間復(fù)雜度O(n log n) 只是入場券不是免死金牌2.1 最好情況、平均情況、最壞情況一個都不能少很多人只看“平均時間復(fù)雜度”就完事了這在筆試?yán)锟梢栽诠こ汤飼愿^。最典型的就是快速排序平均O(n log n)表現(xiàn)優(yōu)秀但如果你每次選的基準(zhǔn)值都恰好是最大值或最小值它就會退化成O(n2)遞歸深度也變成O(n)數(shù)據(jù)量大時直接棧溢出。我遇到過真實的生產(chǎn)事故某個服務(wù)對一小批用戶ID排序ID是外部傳入的攻擊者稍微構(gòu)造一下數(shù)據(jù)順序原本毫秒級的排序直接卡死最后發(fā)現(xiàn)是快排最壞情況被觸發(fā)了。從那之后我給自己定了一條規(guī)則在公共接口里使用快排類算法必須做基準(zhǔn)值優(yōu)化——要么取頭中尾三個數(shù)的中位數(shù)作為基準(zhǔn)要么限制遞歸深度超標(biāo)時切換到堆排序這就是內(nèi)省排序的思路。選型時最好和最壞情況都要寫在參數(shù)對比表里不能只盯著平均情況。2.2 比較次數(shù)怎么算以快速排序和歸并排序為例時間復(fù)雜度是宏觀描述比較次數(shù)是微觀計算。以算法導(dǎo)論的經(jīng)典概率模型來看快速排序的平均比較次數(shù)約為 1.39n log?n而歸并排序的比較次數(shù)約為 n log?n - n 1。注意快排雖然漸進復(fù)雜度和歸并相同但平均常數(shù)比歸并大了約39%。這個差異在真實場景里很有意義。假設(shè)你排序1000萬個元素二者平均比較次數(shù)差了大約6800萬次。如果每次比較都很快比如比較整數(shù)這點差距毫秒級就追回來了但如果比較的是字符串或者帶回調(diào)函數(shù)的復(fù)雜對象這6800萬次比較可能讓快排比歸并慢出肉眼可見的差距。還有一點必須強調(diào)任何基于兩兩比較的排序算法最壞情況下至少要比較 ?log?(n!)? 次近似等于 n log?n - 1.44n。這是決策樹模型推導(dǎo)出來的信息論下界任何聰明技巧都無法突破——這也就解釋了為什么比較排序永遠到不了O(n)除非你放棄“比較”這個信息獲取機制。想突破O(n log n)只有換賽道用非比較排序比如計數(shù)排序、基數(shù)排序、桶排序用輸入數(shù)據(jù)的額外特征換取速度。2.3 常數(shù)因子與實際耗時同一復(fù)雜度也能差出幾倍只看大O復(fù)雜度會讓人產(chǎn)生一個錯覺O(n log n)的算法都差不多快。真實測一下你會發(fā)現(xiàn)差距驚人。我用同一批隨機整數(shù)做過實驗n100萬時快速排序耗時約80毫秒歸并排序約120毫秒堆排序約260毫秒。三者名義復(fù)雜度都是O(n log n)實際表現(xiàn)卻差出三倍以上。差距來源有三個層面。第一是常數(shù)因子不同快排的實際比較次數(shù)確實多于歸并但它的partition掃描是單向的匯合方式讓它在數(shù)據(jù)局部性上占了便宜第二是緩存命中率不同快排對數(shù)組的順序訪問非常友好堆排序的sift-down是隨機跳躍訪問緩存親和性極差第三是分支預(yù)測的差異插入排序在數(shù)據(jù)近似有序時內(nèi)層循環(huán)幾乎每次都能命中預(yù)測跑起來快得離譜。所以我的經(jīng)驗是當(dāng)你在大O復(fù)雜度相同的一批算法里選型時務(wù)必用真實數(shù)據(jù)做基準(zhǔn)測試不要用理論復(fù)雜度拍腦袋。理論只幫你畫范圍常數(shù)才是最終裁定者。3. 空間復(fù)雜度與穩(wěn)定性兩個“隱形指標(biāo)”關(guān)鍵時刻要命3.1 原地排序與附屬空間空間換時間的真實賬本空間復(fù)雜度最核心的問題是算法是否原地排序。原地意味著除了輸入數(shù)組本身只允許使用O(1)額外空間。插入排序、堆排序、快速排序遞歸棧不算入額外數(shù)組的話都是原地算法歸并排序則不是——它需要額外O(n)的空間來存放合并中間結(jié)果。內(nèi)存吃緊的場景里這個差距非常真實。有一次我負(fù)責(zé)處理嵌入式設(shè)備上的傳感器數(shù)據(jù)可用內(nèi)存只有幾百KB要排的數(shù)據(jù)是幾十萬個浮點數(shù)。歸并排序的額外數(shù)組直接超預(yù)算最終只能用堆排序因為它原地、穩(wěn)定O(n log n)、最壞情況也不退化。那是我第一次真切感受到“空間復(fù)雜度不是填空題是生死線”。也別忽略遞歸棧的空間?？焖倥判蜃顗那闆r遞歸深度O(n)每層都有棧幀開銷n10萬時遞歸深度也可能到10萬層直接把程序棧壓爆。這也是為什么工程上要對遞歸深度做限制或者干脆用非遞歸版本用顯式棧模擬可控性和安全性都更好。3.2 穩(wěn)定性的含金量多級排序為什么繞不開它穩(wěn)定性定義很簡潔值相等的元素在排序前后保持相對位置不變。但很多初學(xué)者想不通為什么這是一個“必須盯緊”的指標(biāo)。我舉一個真正發(fā)生過的業(yè)務(wù)場景某報表系統(tǒng)要按月銷售額排名銷售額相同的條目再按門店編號排序。實現(xiàn)方式有兩種選擇。方案一寫一個多鍵比較器先比較銷售額再比較門店號方案二用穩(wěn)定排序先按門店號排一次再按銷售額排一次銷售額相等時由于第一輪排序的結(jié)果保留下來門店號順序自然正確。方案二看著多排了一次但它有個巨大優(yōu)勢每一輪的排序邏輯可以獨立復(fù)用不用維護復(fù)雜的比較器。比如第一輪用基數(shù)排序按門店號排好第二輪用歸并排序按銷售額排兩輪各自清晰。如果用了不穩(wěn)定的排序第二輪就會把第一輪的順序打亂最終得到的排序結(jié)果在兩個鍵之間沒有任何可控關(guān)系。經(jīng)典排序算法里插入排序、冒泡排序、歸并排序是穩(wěn)定的選擇排序、快速排序、堆排序不穩(wěn)定。工程庫里的穩(wěn)定排序通?；跉w并排序的思路這也是托普利茨基排序、TimSort這些變種的出身——先找天然有序片段再用歸并把它們串起來既快又穩(wěn)。3.3 穩(wěn)定但不原地原地但不穩(wěn)定經(jīng)典“可能三角”與折中方案把空間和穩(wěn)定性放在一起看你會發(fā)現(xiàn)在實用算法范圍內(nèi)存在一個“不可能三角”同時做到最優(yōu)時間O(n log n)、原地排序O(1)空間、穩(wěn)定這三者很難同時滿足。嚴(yán)格說原地歸并排序這類算法在理論上存在但常數(shù)巨大合并兩個有序子數(shù)組時用旋轉(zhuǎn)等技巧騰挪元素實際開銷高到?jīng)]人愿意在生產(chǎn)環(huán)境用它。因此工程上通常接受一種折中用歸并排序的變體比如TimSort來換穩(wěn)定性犧牲O(n)空間或者用堆排序/內(nèi)省排序來換原地性放棄穩(wěn)定保障。如果你既需要穩(wěn)定又非常缺內(nèi)存還有一種思路是在鏈表上做歸并排序——鏈表歸并的空間復(fù)雜度是O(1)因為節(jié)點可以原地重新鏈接不需要額外數(shù)組。這個技巧在處理鏈表數(shù)據(jù)時價值很大但要求數(shù)據(jù)本身以鏈表形式存放數(shù)組場景就無能為力了。4. 工程選型實操把指標(biāo)放到一張表里做決策4.1 主流排序算法指標(biāo)速查表我把實際開發(fā)中最常碰到的排序算法整理成了一張速查表方便選型時對照。算法平均時間最壞時間空間穩(wěn)定性原地自適應(yīng)冒泡排序O(n2)O(n2)O(1)穩(wěn)定是是選擇排序O(n2)O(n2)O(1)不穩(wěn)定是否插入排序O(n2)O(n2)O(1)穩(wěn)定是是快速排序O(n log n)O(n2)O(log n)不穩(wěn)定是否歸并排序O(n log n)O(n log n)O(n)穩(wěn)定否是堆排序O(n log n)O(n log n)O(1)不穩(wěn)定是否計數(shù)排序O(n k)O(n k)O(k)穩(wěn)定否否基數(shù)排序O(d(n k))O(d(n k))O(n k)穩(wěn)定否否這張表看著簡單真正用好它需要讀懂表背后的三件事快排最壞O(n2)不是嚇唬人是可以被輸入數(shù)據(jù)精準(zhǔn)觸發(fā)的堆排序看起來空間最省但實際跑的慢常常是因為緩存不友好計數(shù)排序和基數(shù)排序別看是O(n)它們要求鍵值范圍小且可控適用范圍其實很窄。4.2 從業(yè)務(wù)場景出發(fā)的選型決策流程我給自己總結(jié)了一套5步選型法準(zhǔn)確率很高分享出來給大家當(dāng)參考。第一步先看數(shù)據(jù)規(guī)模。n小于50的時候直接上插入排序不用猶豫。道理很簡單插入排序常數(shù)極小且對近乎有序的數(shù)據(jù)自帶自適應(yīng)加成在小數(shù)據(jù)量下實測通常比快排更快很多語言的排序庫在小片段上都會切回插入排序也是這個道理。第二步看內(nèi)存約束。內(nèi)存不夠、不能分配O(n)額外空間的原地算法優(yōu)先。從快排、堆排序、內(nèi)省排序里挑注意快排要做基準(zhǔn)優(yōu)化防退化內(nèi)省排序本質(zhì)是快排加堆排兜底是目前工程上最穩(wěn)的原地方案。第三步看穩(wěn)定性需求。有“多級排序”要求的必須用穩(wěn)定算法。優(yōu)先考慮歸并排序變體或TimSort。空間吃緊的話考慮用鏈表歸并替代常數(shù)換空間。第四步看數(shù)據(jù)特征。鍵值分布范圍小且為整數(shù)計數(shù)排序/基數(shù)排序可以突破O(n log n)下界數(shù)據(jù)本身接近有序插入排序或TimSort會發(fā)揮自適應(yīng)優(yōu)勢數(shù)據(jù)中含有大量重復(fù)元素快排需要額外處理——用三路切分而不是普通二路切分否則重復(fù)元素會讓算法退化。第五步默認(rèn)方案。沒有特殊約束就內(nèi)省排序。它平均性能接近快排最壞情況有堆排兜底幾乎不會踩到極端退化是“開箱即用”的最穩(wěn)選擇。多數(shù)主流語言標(biāo)準(zhǔn)庫的排序?qū)崿F(xiàn)思想上走的都是這條路。4.3 幾個我實際踩過的坑與心得第一個坑在小數(shù)據(jù)集上強行上復(fù)雜度“更優(yōu)”的算法。我見過有人對20個元素用歸并排序結(jié)果比冒泡還慢因為額外數(shù)組分配和函數(shù)調(diào)用的開銷早就超過了省下的比較次數(shù)。經(jīng)驗法則是小數(shù)據(jù)量優(yōu)先考慮常數(shù)而不是漸進復(fù)雜度。第二個坑忽略交換成本。某個模塊排序的元素是很大的結(jié)構(gòu)體每個約200字節(jié)。選擇排序雖然比較次數(shù)固定但最壞逼近n次交換而插入排序移動元素時是連續(xù)搬移雖然移動次數(shù)多但每個移動更廉價。實測后我換成插入排序性能反而更好。這個例子提醒我一定先搞清楚“昂貴操作”到底是比較還是賦值不同場景下同一算法的排名會完全顛倒。第三個坑盲目相信語言庫函數(shù)“夠快”。語言庫默認(rèn)排序是為通用場景調(diào)優(yōu)的但你一旦明確知道自己的數(shù)據(jù)特征比如大量重復(fù)值、基本有序、鍵值范圍小針對性地選用專門算法往往能拿到數(shù)倍提升。我做過一個基于計數(shù)思想的優(yōu)化把一個原本用通用排序處理的分桶邏輯從秒級壓到了毫秒級。庫函數(shù)保底自定義優(yōu)化突破。5. 常見問題排查與冷門指標(biāo)補充5.1 排序問題FAQ速查表以下問題都是我在社區(qū)答疑或團隊評審里反復(fù)遇到的整理成速查表。問題現(xiàn)象根本原因解決建議為什么我的快排比庫函數(shù)慢很多基準(zhǔn)值選得差最壞情況退化改用三數(shù)取中或直接換成內(nèi)省排序數(shù)據(jù)里大量重復(fù)元素快排性能暴跌二路切分無法有效劃分重復(fù)值用三路切分快排或改用歸并排序先按A再按B排序結(jié)果B的順序還是亂用了不穩(wěn)定的排序改用穩(wěn)定排序或改寫成多鍵比較器堆排序理論上O(n log n)實測卻很慢跳躍式內(nèi)存訪問緩存命中率低換快排/內(nèi)省排序除非吃緊內(nèi)存遞歸排序在數(shù)據(jù)量大時程序棧溢出快排最壞遞歸深度O(n)限制遞歸深度/用迭代版本/內(nèi)省排序數(shù)據(jù)基本有序時排序仍然很慢沒用自適應(yīng)算法改用插入排序或TimSort整數(shù)數(shù)據(jù)量大O(n log n)還是太慢比較排序下界限制了性能用計數(shù)/基數(shù)排序突破下界第七個問題值得多寫兩句如果排序?qū)ο笫前偃f級整數(shù)鍵值范圍又是有限的比如0到65536計數(shù)排序一趟遍歷就能完成時間復(fù)雜度O(n k)比任何比較排序都快一個量級。附帶好處是計數(shù)排序是穩(wěn)定的同時滿足多級排序場景。它的坑在于k不能太大——如果鍵值范圍是0到幾百億空間開銷直接爆炸這時候基數(shù)排序按位拆分?jǐn)?shù)位來排才是合理解法。5.2 容易被低估的冷門指標(biāo)比較次數(shù)、交換次數(shù)與緩存友好性這些“軟指標(biāo)”之所以容易被忽略是因為它們在理論上不影響漸進復(fù)雜度但在工程上直接影響用戶體驗。比較次數(shù)決定的是比較操作的開銷當(dāng)比較器成本很高時比如正則匹配、遠程字典序、帶日志統(tǒng)計的比較函數(shù)歸并排序穩(wěn)定且比較次數(shù)接近最優(yōu)遠比快排劃算交換次數(shù)決定的是賦值操作的開銷如果元素是大結(jié)構(gòu)體或引用計數(shù)的智能指針頻繁交換很可能成為瓶頸。緩存友好性更是決定常數(shù)的不二法門。順序循環(huán)訪問數(shù)組CPU緩存能預(yù)取、流水線能跑滿跳躍訪問則每次都要等待主存延遲性能損耗按數(shù)量級放大。這是為什么堆排序明明各項理論指標(biāo)都優(yōu)秀實戰(zhàn)卻常常墊底的真正原因。5.3 自適應(yīng)性數(shù)據(jù)“半有序”時的隱藏勝負(fù)手最后一個值得單獨講的指標(biāo)是自適應(yīng)性——數(shù)據(jù)越接近有序算法消耗的時間越少。插入排序的自適應(yīng)能力最強數(shù)據(jù)完全有序時只需要n-1次比較接近線性時間TimSort則把這個特性做到了極致它先掃描數(shù)組找出天然有序的“run”片段再用歸并把這些run串起來既能充分利用數(shù)據(jù)本身的順序性又保證了最壞O(n log n)。實操里自適應(yīng)算法最典型的應(yīng)用場景是日志合并、增量數(shù)據(jù)歸并這種“大部分?jǐn)?shù)據(jù)已經(jīng)有序只有少數(shù)新數(shù)據(jù)亂入”的場景。用默認(rèn)快排每次都得重排全量用TimSort或插入排序優(yōu)化往往能把耗時砍掉一大半。這也是我特別建議業(yè)務(wù)開發(fā)在手寫排序邏輯時留一個“輸入是否近似有序”判斷給后續(xù)接手維護的人的原因。再說一個很多人沒意識到的小技巧如果你確定數(shù)據(jù)近似有序但手邊只有快速排序可以先做一輪簡單的預(yù)檢查統(tǒng)計逆序?qū)?shù)量逆序?qū)O少時直接切到插入排序絕大多數(shù)情況下能拿到接近線性的性能。分診式選型比悶頭優(yōu)化一個算法高明得多。我在實際項目中體會到排序指標(biāo)不是紙上談兵的理論筐而是每一行代碼背后真實的CPU時間和內(nèi)存賬單。把指標(biāo)看成約束把選型看成求解很多糾結(jié)自然會消失。這個系列1先把硬指標(biāo)和幾個關(guān)鍵軟指標(biāo)講透后面系列我再展開非比較排序的指標(biāo)評估以及分布式場景、外部排序場景下的指標(biāo)擴展——那些場景里單一機器的復(fù)雜度公式又會變得不夠用了。