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