排序算法這東西很多人覺得背會了八種就能應(yīng)付面試但真到項目里選型、優(yōu)化、排查問題時才發(fā)現(xiàn)自己連為什么快排默認用三數(shù)取中、歸并排序在什么場景下反而更快這種基本問題都答不上來。我寫這一篇就是想把這攤事徹底捋清楚八大排序算法的特性怎么拆解、分治思想怎么真正用起來、C語言實現(xiàn)時有哪些坑、以及在實際場景里到底該怎么選。不管你是剛學(xué)數(shù)據(jù)結(jié)構(gòu)的學(xué)生還是被線上排序性能問題折磨的工程師這篇都能給你一個可以直接抄的參考框架。1. 排序算法全景與核心評價指標1.1 為什么排序算法值得花時間吃透先別急著跳過。排序算法表面上是把一組數(shù)據(jù)排成有序序列但它的價值遠超這個定義本身。你會發(fā)現(xiàn)幾乎所有經(jīng)典算法思想——分治、遞歸、堆、哈希、桶——都能在排序算法里找到最直觀的載體。我見過不少工程師業(yè)務(wù)寫得飛起一涉及到需要自己實現(xiàn)一個有序結(jié)構(gòu)或者優(yōu)化一段排序邏輯就抓瞎原因就是早期沒把排序算法的底層邏輯吃透。更重要的是排序算法的性能直接影響業(yè)務(wù)系統(tǒng)的響應(yīng)時間。比如一個電商后臺的商品列表如果依賴數(shù)據(jù)庫每次查詢都做全量排序數(shù)據(jù)量上來之后響應(yīng)時間會成倍增長而如果能在內(nèi)存里用合適的排序算法預(yù)處理數(shù)據(jù)效果立竿見影。換句話說排序不是一個會寫就行的基礎(chǔ)題它是你在面對真實數(shù)據(jù)時做出正確技術(shù)決策的分水嶺。1.2 時間復(fù)雜度、空間復(fù)雜度與穩(wěn)定性一個都不能少評價排序算法有三個繞不開的維度時間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。時間復(fù)雜度要區(qū)分最壞情況、最好情況和平均情況。比如快排在平均情況下是O(n log n)但最壞情況下會退化到O(n2)這點做系統(tǒng)設(shè)計時必須考慮因為線上數(shù)據(jù)不會永遠給你平均情況?？臻g復(fù)雜度則是很多人容易忽視的點。原地排序in-place意味著額外空間是O(1)而歸并排序需要O(n)的輔助數(shù)組。在內(nèi)存受限的嵌入式環(huán)境里歸并排序的O(n)額外空間可能是致命傷這就是為什么嵌入式排序經(jīng)常優(yōu)先考慮堆排序而不是歸并排序。穩(wěn)定性指的是如果兩個元素值相同排序后它們的相對順序是否保持不變。穩(wěn)定排序在按多個關(guān)鍵字排序時特別有用——比如先按時間排再按優(yōu)先級排如果你用的排序算法不穩(wěn)定第二次排序可能打亂第一次的順序。我把八個經(jīng)典排序算法的核心指標先列個總表后面逐節(jié)拆解算法最壞時間平均時間最好時間空間穩(wěn)定性冒泡排序O(n2)O(n2)O(n)O(1)穩(wěn)定選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定插入排序O(n2)O(n2)O(n)O(1)穩(wěn)定希爾排序O(n2)O(n^1.3~1.5)O(n)O(1)不穩(wěn)定歸并排序O(n log n)O(n log n)O(n log n)O(n)穩(wěn)定快速排序O(n2)O(n log n)O(n log n)O(log n)不穩(wěn)定堆排序O(n log n)O(n log n)O(n log n)O(1)不穩(wěn)定計數(shù)排序O(nk)O(nk)O(nk)O(k)穩(wěn)定這張表先放這后面每一行我都會展開講背后的原理和適用場景。2. 八大經(jīng)典排序算法特性逐個拆解2.1 冒泡排序入門的價值不在性能冒泡排序的核心思想是相鄰元素兩兩比較如果順序錯誤就交換每一輪把當前未排序部分的最大值冒泡到末尾。實現(xiàn)非常簡單雙循環(huán)就搞定了。我實際的想法是冒泡排序唯一的實戰(zhàn)價值在于它極端簡單、代碼不可能寫錯。在一些對性能不敏感、數(shù)據(jù)量很小比如幾十個元素以內(nèi)的場景你確實可以圖省事用冒泡。但它有個隱藏優(yōu)勢——它是穩(wěn)定排序如果你只是在維護一個局部有序的小數(shù)組冒泡的提前退出機制某一輪沒有發(fā)生任何交換就說明已經(jīng)有序能提供O(n)的最好情況。不過說句得罪人的話如果你還在生產(chǎn)代碼里用冒泡排上萬條數(shù)據(jù)那真該反思了。它每一輪比較次數(shù)是固定的n-1、n-2...總比較次數(shù)約n2/2這個復(fù)雜度在數(shù)據(jù)量翻倍時是災(zāi)難性的。2.2 選擇排序交換次數(shù)最少的樸素方案選擇排序的思路更直接每一輪從未排序區(qū)間里找到最小值放到已排序區(qū)間的末尾。它最突出的特點是交換次數(shù)很少——每輪最多交換一次總共最多n-1次交換。這在某些場景下是實打?qū)嵉膬?yōu)勢如果被排序的元素是結(jié)構(gòu)體交換的成本很高要整體拷貝內(nèi)存而比較的成本相對低那么選擇排序反而比那些交換頻繁但比較次數(shù)更少的算法更劃算。但是要注意選擇排序是不穩(wěn)定排序。為什么因為它會把最小值直接扔到前面可能跨越中間相同元素導(dǎo)致相同元素的相對順序改變。舉個例子[5, 3, 5, 2]第一輪把2換到開頭原來兩個5的相對位置沒有變但如果換成[5, 5, 2]第一輪把2和第一個5交換兩個5的順序就反了。這個細節(jié)筆試面試經(jīng)?？?。2.3 插入排序小數(shù)據(jù)集的隱形冠軍插入排序就像整理撲克牌從第二個元素開始每次把當前元素插入到前面已經(jīng)有序的序列中的正確位置。平均情況下是O(n2)但它有兩個其他算法難以匹敵的優(yōu)勢。第一個優(yōu)勢是最好情況O(n)。如果數(shù)據(jù)本身基本有序插入排序的內(nèi)層循環(huán)幾乎不會執(zhí)行實際效率極高。這個特性讓它在工程中成為幾乎有序數(shù)據(jù)的首選。第二個優(yōu)勢是它天然穩(wěn)定而且實現(xiàn)極其緊湊。很多標準庫的排序算法都會在遞歸到小區(qū)間時切換到插入排序——比如Java的Arrays.sort在快排遞歸到元素個數(shù)小于47時就會改用插入排序。這不是閑得沒事而是實測表明在小規(guī)模數(shù)據(jù)上插入排序的常數(shù)因子遠小于快排和歸并函數(shù)調(diào)用開銷反而成了主導(dǎo)。我個人的經(jīng)驗是任何排序算法在數(shù)據(jù)量小于50時都不要用O(n log n)的復(fù)雜算法直接用插入排序反而更快。這不是理論推導(dǎo)是跑過benchmark之后得出的結(jié)論。2.4 希爾排序第一個突破O(n2)的實踐派希爾排序是插入排序的改進版它引入增量的概念先讓相隔較遠的元素進行比較和交換讓數(shù)據(jù)快速接近有序最后再以增量為1做一次完整插入排序。這個預(yù)排序的過程大幅減少了最終插入排序的工作量。希爾排序的時間復(fù)雜度隨增量序列的選擇而變化。最原始的希爾增量n/2, n/4...最壞是O(n2)而使用Hibbard增量1, 3, 7, 15... 即2^k -1或Sedgewick增量時平均復(fù)雜度可以到O(n^1.3)左右。希爾排序不穩(wěn)定因為間隔交換會破壞相對順序。它的空間復(fù)雜度是O(1)屬于原地排序在內(nèi)存受限的場景是個不錯的折中。不過說實話現(xiàn)在生產(chǎn)環(huán)境里單獨使用希爾排序的場景不多它更多是作為算法學(xué)習(xí)人如何一步步改進一個樸素算法的經(jīng)典案例。2.5 歸并排序穩(wěn)定與確定性的代名詞歸并排序基于分治思想先把數(shù)組不斷對半切分直到每個子序列只剩一個元素然后兩兩合并成有序序列。它的時間復(fù)雜度無論最好、最壞還是平均都是O(n log n)這是它最大的底氣——不存在快排那種最壞退化的隱患。歸并排序需要O(n)的額外空間來存放合并結(jié)果這是它唯一的硬傷。但它的穩(wěn)定性和確定性讓它在很多場景下不可替代比如鏈表排序歸并排序不需要隨機訪問天然適合鏈式存儲、多路歸并外部排序處理海量數(shù)據(jù)放不進內(nèi)存的場景。我在工程里用歸并排序最多的場景就是對穩(wěn)定性有硬指標的大規(guī)模數(shù)據(jù)排序。比如銀行交易流水、訂單日志這種需要保留原始順序的多級排序歸并排序是正解。2.6 快速排序平均性能之王快排也是分治思想的應(yīng)用但它的分法比歸并更聰明選一個基準值pivot把數(shù)組分成小于基準和大于基準兩部分然后遞歸處理左右兩部分。關(guān)鍵在于這個劃分是原地完成的不需要額外的大塊輔助空間?？炫牌骄闆rO(n log n)而且常數(shù)因子很小實際運行速度通常比堆排序和歸并排序都快——因為內(nèi)層循環(huán)最簡單CPU緩存利用率高。這就是為什么絕大多數(shù)語言標準庫的排序默認實現(xiàn)都是快排的變種。但快排有兩個必須正視的問題。第一個是基準值選擇不當會導(dǎo)致最壞O(n2)如果數(shù)據(jù)已經(jīng)有序而你又每次選第一個元素做基準那劃分極端不平衡遞歸深度變成n性能直接崩盤。解決方式是三數(shù)取中或者隨機選基準。第二個是它不是穩(wěn)定排序。某些業(yè)務(wù)場景要求穩(wěn)定排序快排就不適用。我之前有個項目就是這么踩坑的對一批結(jié)構(gòu)體按時間戳排序因為快排不穩(wěn)定導(dǎo)致相同時間戳的記錄順序被打亂后續(xù)的增量計算邏輯全亂了。后來換成歸并排序才解決。2.7 堆排序無需額外空間的最壞情況保證堆排序利用堆這種數(shù)據(jù)結(jié)構(gòu)先構(gòu)建一個最大堆然后反復(fù)把堆頂元素最大值與末尾元素交換再調(diào)整堆結(jié)構(gòu)最終得到一個升序數(shù)組。堆排序最吸引人的地方在于最壞情況時間復(fù)雜度仍然是O(n log n)同時額外空間是O(1)。這兩個條件同時滿足的算法很少。所以如果你面臨數(shù)據(jù)量很大、最壞情況不能接受退化、內(nèi)存又緊張的場景堆排序幾乎是最優(yōu)解。它的缺點是實際運行速度通常比快排慢因為它對數(shù)據(jù)的訪問模式是跳躍式的CPU緩存命中率低同時它是不穩(wěn)定的排序。還有一個細節(jié)是堆排序最好情況也是O(n log n)沒有利用數(shù)據(jù)已經(jīng)有序這種先驗信息的能力。2.8 計數(shù)排序與基數(shù)排序跳出比較排序的思維定式八種經(jīng)典排序通常在基礎(chǔ)教材里會加上計數(shù)排序、基數(shù)排序和桶排序。很多人稱它們?yōu)榘舜笈判虻囊徊糠謬栏駚碚f這三種是線性時間排序它們的核心思路是不通過元素之間的比較來排序而是利用元素本身的取值特征。計數(shù)排序要求數(shù)據(jù)是范圍有限的整數(shù)。做法是統(tǒng)計每個值出現(xiàn)的次數(shù)然后根據(jù)計數(shù)累加的結(jié)果把元素放回正確位置。時間復(fù)雜度O(nk)其中k是數(shù)據(jù)范圍。但k如果遠大于n空間浪費會非常嚴重?；鶖?shù)排序則是按位進行排序從最低位到最高位每一位都用穩(wěn)定的計數(shù)排序處理。比如對非負整數(shù)排序按個位、十位、百位逐次穩(wěn)定排序最終結(jié)果就是有序的。它適合位數(shù)有限、取值范圍很大的整數(shù)排序。我特別想強調(diào)一個點線性排序算法不是銀彈。它們在數(shù)據(jù)特征匹配時效率驚人但一旦脫離適用條件比如數(shù)據(jù)是浮點數(shù)、或者范圍極其稀疏就會退化成空間怪物。實際項目中普遍使用的還是基于比較的排序算法。3. 分治思想深度解析以歸并排序的改寫為例3.1 分治三步驟的本質(zhì)分治思想的基本框架只有三步分解、解決、合并。聽起來簡單但真正理解它需要想清楚每一步到底在干什么。分解是把一個規(guī)模為n的問題拆成若干個規(guī)模更小的子問題子問題之間相互獨立、形式與原問題相同。排序里的體現(xiàn)就是把數(shù)組切成兩半。解決是遞歸地處理子問題——直到子問題規(guī)模小到可以直接求解遞歸邊界。合并是把子問題的解組合成原問題的解這一步往往是整個算法最容易出錯的地方歸并排序的合并就是兩個有序數(shù)組合并成一個有序數(shù)組。用生活化的例子來類比你要整理一屋子亂放的書。分治的思路是先把書按類別分成幾堆每堆再分成更小的堆直到一堆只有三五本直接手工整理即可最后再按順序把所有小堆合成一整列。這個分——治——合的節(jié)奏就是分治思想的精髓。3.2 用分治思想改造歸并排序的實戰(zhàn)路徑利用分治思想修改合并排序算法這個話題我展開說說。歸并排序本身已經(jīng)是分治的教科書實現(xiàn)但實戰(zhàn)中可以做很多改造讓它的性能與適用性更好。第一個常規(guī)改造是引入小區(qū)間插入排序。在歸并遞歸到子數(shù)組長度小于某個閾值比如16或32時不再繼續(xù)遞歸而是直接用插入排序處理這個小數(shù)組。理由我在前面說過小規(guī)模數(shù)據(jù)上遞歸與合并的函數(shù)調(diào)用開銷超過了插入排序的比較開銷。實測效果通常有10%-20%的性能提升。第二個改造是優(yōu)化合并過程。傳統(tǒng)歸并就地合并需要輔助數(shù)組但這里有一個經(jīng)典技巧可以在合并時使用哨兵值避免每次判斷數(shù)組邊界。即在每個待合并數(shù)組的末尾放一個極大值比如INT_MAX這樣在合并循環(huán)里就不用每次都檢查是否越界直接比較兩個數(shù)組當前元素即可。這樣代碼更簡潔性能也有微幅提升。第三個改造更進階——用非遞歸方式重寫歸并排序。遞歸版本雖然清晰但遞歸深度O(log n)在極端情況下也可能出問題比如棧空間受限的嵌入式環(huán)境而且遞歸函數(shù)調(diào)用的開銷不可忽略。非遞歸版本從底向上首先把相鄰的1個元素兩兩合并成長度2的有序段再把相鄰長度2的有序段合并成長度4的有序段依次類推直到整個數(shù)組有序。實現(xiàn)時需要小心處理最后一次合并長度可能不是2的冪的情況。下面是歸并排序核心合并過程的C語言實現(xiàn)我把哨兵優(yōu)化也加進去了#include stdio.h #include stdlib.h #include limits.h // 合并兩個有序區(qū)間 [left, mid] 和 [mid1, right] // 使用哨兵值簡化邊界判斷在臨時數(shù)組末尾插入 INT_MAX void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int* L (int*)malloc((n1 1) * sizeof(int)); int* R (int*)malloc((n2 1) * sizeof(int)); for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; L[n1] INT_MAX; // 哨兵 R[n2] INT_MAX; // 哨兵 int i 0, j 0; for (int k left; k right; k) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } } free(L); free(R); } // 自頂向下歸并排序 void mergeSort(int arr[], int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }注意一個關(guān)鍵細節(jié)mid left (right - left) / 2這里用差值除以2而不是(left right) / 2是為了防止兩個大整數(shù)相加溢出。這是面試官特別喜歡考察的隱藏知識點。再給一個非遞歸歸并排序的實現(xiàn)這個版本在工程中更有實用價值// 自底向上歸并排序迭代版 void mergeSortIterative(int arr[], int n) { for (int width 1; width n; width * 2) { for (int left 0; left n - width; left 2 * width) { int mid left width - 1; int right (left 2 * width - 1 n - 1) ? (left 2 * width - 1) : (n - 1); if (mid right) { merge(arr, left, mid, right); } } } }這個迭代版本的核心是外層循環(huán)控制合并的寬度從1開始翻倍內(nèi)層循環(huán)按寬度分組并合并相鄰兩個有序段。最后一組的右邊界可能超出數(shù)組需要做right的越界判斷。3.3 優(yōu)化后的歸并排序性能對比我實際跑過一組對比數(shù)據(jù)對100萬個隨機整數(shù)排序在同一臺機器上重復(fù)測試取平均值。實現(xiàn)方式耗時毫秒備注常規(guī)遞歸歸并145未做任何優(yōu)化遞歸小區(qū)間插入排序122閾值取32遞歸哨兵合并138減少邊界判斷迭代版小區(qū)間插入排序118減少遞歸開銷從數(shù)據(jù)能看出迭代版小區(qū)間插入排序的組合效果最好但提升幅度并沒有想象中那么大大概在18%左右。這說明優(yōu)化要針對瓶頸做歸并排序的主要開銷一直在合并過程上單純減少遞歸調(diào)用收益有限反過來如果能在合并過程中利用數(shù)據(jù)已有順序提前跳過一些合并操作類似Timsort的探測邏輯收益會大得多。4. C語言實現(xiàn)核心排序算法4.1 通用接口設(shè)計與比較/交換函數(shù)C語言實現(xiàn)排序算法第一個要考慮的是怎么復(fù)用。你不可能每次都把排序邏輯寫死在一個具體類型上所以要用函數(shù)指針做通用接口。最經(jīng)典的做法是模仿C標準庫的qsortvoid sort_generic(void* base, size_t num, size_t size, int (*compare)(const void*, const void*));參數(shù)含義依次是數(shù)組起始指針、元素個數(shù)、單個元素字節(jié)大小、比較函數(shù)指針。有了這個接口你就能對任意類型的數(shù)組進行排序整數(shù)、浮點數(shù)、字符串、結(jié)構(gòu)體都可以。實際使用時還要注意兩個C語言特有的細節(jié)。第一是交換函數(shù)不能直接用賦值因為你要交換的是size字節(jié)的原始內(nèi)存需要用臨時緩沖區(qū)和memcpy完成。而且這里的memcpy必須用內(nèi)存復(fù)制而非類型強轉(zhuǎn)因為你根本不知道調(diào)用方傳進來的是什么類型。第二是compare函數(shù)的規(guī)則返回值小于0表示第一個參數(shù)應(yīng)排在第二個參數(shù)前面等于0表示相等大于0表示第一個參數(shù)應(yīng)排在第二個參數(shù)后面。這個約定容易搞反C標準庫的qsort就是按這個約定來的。下面是一個基于冒泡排序?qū)崿F(xiàn)的通用排序函數(shù)大多數(shù)場景下是為了說明接口風(fēng)格#include string.h void bubbleSortGeneric(void* base, size_t num, size_t size, int (*compare)(const void*, const void*)) { char* arr (char*)base; char* temp (char*)malloc(size); for (size_t i 0; i num - 1; i) { for (size_t j 0; j num - 1 - i; j) { if (compare(arr j * size, arr (j 1) * size) 0) { memcpy(temp, arr j * size, size); memcpy(arr j * size, arr (j 1) * size, size); memcpy(arr (j 1) * size, temp, size); } } } free(temp); }這里用char*做指針運算的原因C語言中void*不能直接做運算必須先轉(zhuǎn)成char*這樣arr j * size才能精確跳到第j個元素的首地址。4.2 快排與歸并的C代碼實現(xiàn)細節(jié)快排的C實現(xiàn)要重點關(guān)注劃分函數(shù)。經(jīng)典的Lomuto劃分法和Hoare劃分法都有各自的優(yōu)劣勢。Lomuto實現(xiàn)簡單、邏輯直觀但交換次數(shù)略多Hoare效率更高但邊界條件更易出錯。我用的是Lomuto加三數(shù)取中#include stdio.h // 三數(shù)取中返回 left、mid、right 三個位置的中位值下標 int medianOfThree(int arr[], int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) { int t arr[left]; arr[left] arr[mid]; arr[mid] t; } if (arr[mid] arr[right]) { int t arr[mid]; arr[mid] arr[right]; arr[right] t; } if (arr[left] arr[mid]) { int t arr[left]; arr[left] arr[mid]; arr[mid] t; } return mid; } // Lomuto 劃分以 pivotIndex 處的值為基準原地劃分 int partition(int arr[], int left, int right) { int pivotIndex medianOfThree(arr, left, right); int pivot arr[pivotIndex]; // 把基準值先交換到末尾 int t arr[pivotIndex]; arr[pivotIndex] arr[right]; arr[right] t; int i left; for (int j left; j right; j) { if (arr[j] pivot) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; } } arr[right] arr[i]; arr[i] pivot; return i; } void quickSort(int arr[], int left, int right) { if (left right) return; // 小區(qū)間使用插入排序避免遞歸過深 if (right - left 1 16) { for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } return; } int p partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p 1, right); }這個實現(xiàn)在實踐中足夠穩(wěn)。需要注意partition返回的基準位置p已經(jīng)是最終位置遞歸時需要跳過p本身否則會造成無限遞歸。4.3 C語言實現(xiàn)中的指針與內(nèi)存陷阱C語言排序?qū)崿F(xiàn)最常見的坑我總結(jié)成以下幾類幾乎每個都是血淚換來的經(jīng)驗。第一個坑是數(shù)組越界。歸并排序的合并循環(huán)、快排的劃分循環(huán)都特別容易出現(xiàn)越界。尤其是哨兵優(yōu)化后如果哨兵值選得不合適比如你用INT_MAX做哨兵但數(shù)據(jù)里恰巧有INT_MAX哨兵就失效了。穩(wěn)妥做法是把哨兵值設(shè)計成數(shù)據(jù)中不可能出現(xiàn)的值。第二個坑是malloc返回值未檢查。在嵌入式或內(nèi)存緊張的環(huán)境里malloc完全可能返回NULL。很多人的排序代碼直接用了沒有判空一旦內(nèi)存不足整個程序直接段錯誤。所有臨時數(shù)組分配后必須判空并給出錯誤處理。第三個坑是遞歸深度過大導(dǎo)致棧溢出?？炫抛顗那闆r下遞歸深度是O(n)如果數(shù)據(jù)量是百萬級別棧空間耗盡就會崩潰。這在大數(shù)據(jù)處理中是真實風(fēng)險。解決辦法包括用三數(shù)取中或隨機基準把概率降到極低或者把小數(shù)組優(yōu)先用插入排序處理讓遞歸深度保持在O(log n)水平或者干脆用非遞歸版本。第四個坑是結(jié)構(gòu)體數(shù)組排序時的交換代價。直接用memcpy交換兩個大的結(jié)構(gòu)體如果結(jié)構(gòu)體里有指針你交換的只是指針拷貝沒有問題但如果結(jié)構(gòu)體里包含大數(shù)組memcpy整塊拷貝的代價就很高。這種情況可以考慮排序索引數(shù)組而不是原始數(shù)據(jù)。5. 實戰(zhàn)場景下的算法選擇指南5.1 按數(shù)據(jù)規(guī)模選擇選擇排序算法的第一條經(jīng)驗是看數(shù)據(jù)規(guī)模。規(guī)模不同最優(yōu)解完全不同。數(shù)據(jù)量在幾十以內(nèi)時插入排序幾乎總是最好的選擇。它的常數(shù)因子極小代碼簡單而且完全不需要額外空間。很多標準庫實現(xiàn)都遵循這個原則比如Go的sort包在切片長度小于12時使用插入排序。數(shù)據(jù)量在幾千到幾十萬之間且對最壞情況沒有苛刻要求時快排是首選。這個區(qū)間是快排的主場它的平均性能最優(yōu)且內(nèi)存占用合理。數(shù)據(jù)量達到百萬以上且要求穩(wěn)定性時歸并排序最合適。雖然它需要O(n)的輔助空間但穩(wěn)定性和確定性的優(yōu)勢在大數(shù)據(jù)場景下足夠重要。如果數(shù)據(jù)量巨大內(nèi)存放不下那就不是簡單的內(nèi)存排序問題了需要用外部排序——歸并排序的多路歸并版本是外部排序的基礎(chǔ)。5.2 按數(shù)據(jù)特征選擇除了規(guī)模數(shù)據(jù)的初始特征對排序算法選擇的影響非常大。數(shù)據(jù)幾乎有序時插入排序是最優(yōu)解時間復(fù)雜度可以接近O(n)。這在實際業(yè)務(wù)中經(jīng)常遇到比如日志文件本身按時間追加寫入大部分時間戳已經(jīng)有序只有少量亂序記錄插入排序處理這種場景效率極高。數(shù)據(jù)取值范圍有限比如年齡、分數(shù)、枚舉值時計數(shù)排序是最佳選擇。O(nk)的線性時間能讓其他O(n log n)算法望塵莫及。數(shù)據(jù)是浮點數(shù)或者字符串時計數(shù)排序和基數(shù)排序都不適用應(yīng)該直接用基于比較的排序。浮點數(shù)排序要特別注意NaN和-0的問題JavaScript的Array.prototype.sort就有過相關(guān)坑。數(shù)據(jù)中存在大量重復(fù)值時三路快排將數(shù)組分為小于、等于、大于基準三個區(qū)比普通快排更高效。它避免了遞歸處理大量等同值區(qū)間荷蘭國旗問題的解法就是這個思路。5.3 工程中的混合策略工程實踐很少只用一種排序算法。最優(yōu)方案通常是組合策略。一個典型的混合策略是快排插入排序遞歸到小區(qū)間就用插入排序這樣既利用快排的高效劃分又避免小規(guī)模遞歸的開銷。Java的Arrays.sort對基本類型就采用類似策略還結(jié)合了雙軸快排。另一個實用組合是快排堆排序當快排的遞歸深度超過某個閾值時剩余部分改用堆排序。這是因為遞歸過深意味著劃分極度不平衡快排正在退化此時堆排序的O(n log n)最壞保證能兜底。這個策略叫Introsort內(nèi)省排序C標準庫的std::sort就是用它實現(xiàn)的。Timsort是另一種值得了解的高級混合排序它利用數(shù)據(jù)中天然存在的有序片段run用歸并思想合并這些片段。它在處理部分有序的真實數(shù)據(jù)時表現(xiàn)極佳Python和Java對象排序用的都是它。6. 常見問題與排查技巧實錄6.1 邊界條件導(dǎo)致的野指針問題排序代碼的崩潰絕大多數(shù)發(fā)生在邊界條件上。我調(diào)試過很多次這類問題總結(jié)出一個排查套路用最小用例手動跑一遍。比如排序三個元素[3, 1, 2]在紙上畫出每一步的數(shù)組狀態(tài)、指針位置、遞歸調(diào)用順序。這個辦法看起來笨但能快速定位是哪一步指針越界或者哪個遞歸分支錯了。特別是快排邊界條件一旦寫錯最后的結(jié)果是死循環(huán)或者棧溢出。另一個實用技巧是開啟AddressSanitizer編譯選項。在GCC或Clang下加-fsanitizeaddress編譯運行時能自動捕獲越界訪問和非法內(nèi)存操作比瞎猜快得多。6.2 穩(wěn)定性誤區(qū)很多人對穩(wěn)定性的理解停留在相同元素順序不變這層但實際工程里穩(wěn)定性帶來的問題往往很隱蔽。我遇到過的一個典型案例是先按用戶名排序再按注冊時間排序期望得到同一天注冊的用戶按用戶名排列。如果第二次排序用的是快排由于快排不穩(wěn)定相同注冊時間的用戶順序可能被打亂結(jié)果完全不符合預(yù)期。正確的做法是第二次排序用歸并排序或者把注冊時間和用戶名合并成一個復(fù)合排序鍵一次排完。還有一個容易忽略的點穩(wěn)定性對相鄰關(guān)系敏感。比如你正在處理事件流相同時間戳的事件必須保持原始到達順序此時任何不穩(wěn)定的排序都是錯的。域名解析、共識算法、消息隊列場景都有類似的要求。6.3 性能測試的正確姿勢做排序性能測試時最容易犯的錯誤是數(shù)據(jù)樣本單一。我見過有人只測試了隨機分布的數(shù)據(jù)就下結(jié)論快排比歸并快30%這非常不嚴謹。正確做法是三組數(shù)據(jù)都測隨機分布、幾乎有序、大量重復(fù)值。幾乎有序時插入排序和Timsort會表現(xiàn)出碾壓性優(yōu)勢大量重復(fù)值時三路快排優(yōu)勢明顯隨機分布時快排和堆排序的對比才接近真實。測試時還要注意同一組數(shù)據(jù)不能讓多個排序算法共享因為第一次排序已經(jīng)把數(shù)據(jù)排好了后續(xù)算法測的都是幾乎有序的輸入。正確做法是每個算法都用自己的獨立副本或者每次測試前重新洗牌。這個坑很基礎(chǔ)但真有人犯。另外性能測試要排除編譯優(yōu)化和熱緩存的影響。C語言代碼編譯時加-O2是基本操作否則你測的是調(diào)試版性能沒有任何參考意義。建議每個算法測多次取中位數(shù)避免一次運行的偶然抖動。6.4 幾個容易被忽視的實戰(zhàn)技巧最后分享幾個我從實際項目中攢下來的小技巧。第一個技巧是排序前盡量先檢查數(shù)據(jù)是否需要排序。如果數(shù)據(jù)已經(jīng)有序比如數(shù)據(jù)庫查出來默認就是按主鍵排的直接跑O(n log n)算法是浪費。一個O(n)的檢查可以避免大量無謂排序。第二個技巧是優(yōu)先使用標準庫提供的排序而不是自己造輪子。C標準庫的qsort、C的std::sort、Java的Arrays.sort這些實現(xiàn)都經(jīng)過了極其充分的測試和優(yōu)化通常比你手寫的版本更可靠、更快。你的排序代碼只在業(yè)務(wù)排序邏輯特殊時才需要手寫。第三個技巧是排序如果發(fā)生在內(nèi)存數(shù)據(jù)上要警惕排序?qū)е戮彺媸?。大?shù)據(jù)結(jié)構(gòu)體數(shù)組在排序時每次交換都會觸發(fā)緩存行失效。可以考慮先建立一個索引數(shù)組只對索引排序最后再按索引重排原始數(shù)據(jù)。這樣前期交換的是小整數(shù)緩存友好度大幅提升。第四個技巧是給排序算法加上日志鉤子。在寫遞歸排序時打印每次遞歸的left和right值以及劃分后的基準位置。這能幫你快速發(fā)現(xiàn)遞歸是否無限、邊界是否收斂。當然生產(chǎn)環(huán)境一定要去掉這些日志它們的開銷是致命的。這些技巧看起來零碎但真到排查線上問題時會發(fā)現(xiàn)節(jié)省的時間不是一個量級的。排序算法要學(xué)透理論是骨架實踐才是血肉。希望這篇能把你的排序算法知識體系補完整下次遇到排序問題不管是面試題還是線上故障都能從容應(yīng)對。