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