冒泡排序在C語言里的地位有點(diǎn)微妙面試常考、教材必講、實(shí)際項(xiàng)目里卻幾乎輪不到它上場(chǎng)?？烧娴揭謱懙臅r(shí)候越界、少跑一趟、交換寫反、循環(huán)變量作用域搞錯(cuò)這些問題一個(gè)接一個(gè)冒出來。我?guī)氯俗龃a審查見過最多的不是算法寫不出來而是邊界寫錯(cuò)——j n - i和j n - 1 - i到底差在哪說不清的人一大把。這篇我想把冒泡排序從“背模板”拉回到“理解機(jī)制”核心思想是什么循環(huán)邊界怎么推導(dǎo)幾種常見優(yōu)化值不值得泛型版本怎么寫實(shí)測(cè)它和快排差多少最后整理一份我自己踩過的坑給對(duì)號(hào)入座。新手能拿來當(dāng)練習(xí)骨架有基礎(chǔ)的讀者可以看看有沒有遺漏的細(xì)節(jié)。1. 冒泡排序?yàn)槭裁磿?huì)成為C語言入門的標(biāo)配1.1 從一次嵌入式小項(xiàng)目的真實(shí)需求說起我最早認(rèn)真對(duì)待冒泡排序是在一個(gè)采樣數(shù)據(jù)排序的小場(chǎng)景里。某開發(fā)者負(fù)責(zé)的模塊每 200 毫秒拿到一組 8 到 12 個(gè)的傳感器讀數(shù)需要在本地做一次升序整理再打包上報(bào)。數(shù)據(jù)量小到可憐編譯資源也緊張團(tuán)隊(duì)最后的結(jié)論是不要引入標(biāo)準(zhǔn)庫(kù)的排序函數(shù)也不要自己寫的復(fù)雜算法就用最樸素的兩層循環(huán)。理由很直接——n 最大 12最壞比較次數(shù) 66 次這點(diǎn)開銷在 200 毫秒周期里連噪聲都算不上而代碼越短越容易審查、越不容易出錯(cuò)。這件事讓我意識(shí)到一個(gè)常被忽略的點(diǎn)算法的“好壞”從來不只看復(fù)雜度還要看規(guī)模、看資源、看維護(hù)成本。冒泡排序在 n 很小的時(shí)候它的常數(shù)因子小代碼分支少緩存友好順序訪問數(shù)組寫得對(duì)的話幾乎沒有額外內(nèi)存開銷。相比之下一個(gè)帶遞歸的快排在小數(shù)組上反而可能因?yàn)楹瘮?shù)調(diào)用開銷和棧占用而輸?shù)?。教科書只告訴你 O(n2) 慢卻不告訴你 n10 的時(shí)候它一點(diǎn)都不慢。所以對(duì)初學(xué)者來說冒泡排序的價(jià)值不在“能用”而在“能看懂”。它是最適合用來練習(xí)三層?xùn)|西的載體循環(huán)邊界的推導(dǎo)、狀態(tài)變量的引入、以及“優(yōu)化是不是真的優(yōu)化”的判斷力。這三樣?xùn)|西是通用的換任何算法都用得上。1.2 它到底在“冒”什么一句話說透核心機(jī)制冒泡排序的核心只有一句話反復(fù)比較相鄰的兩個(gè)元素順序不對(duì)就交換每一趟走完當(dāng)前未排序區(qū)間的極值就會(huì)被推到區(qū)間邊緣。以升序?yàn)槔谝惶藦南聵?biāo) 0 走到 n-2比較a[j]和a[j1]如果a[j] a[j1]就互換。走完這一趟最大值一定躺在a[n-1]上。為什么是“一定”因?yàn)樽畲笾翟谝苿?dòng)過程中不會(huì)被任何元素?fù)踝　日l都大每次遇到鄰居都會(huì)觸發(fā)交換于是像水里的氣泡一樣一路頂?shù)侥┪?。這就是“冒泡”這個(gè)名字的由來也是它能被嚴(yán)格證明的原因。第二趟就只需要走到 n-3 了因?yàn)樽詈笠晃灰呀?jīng)確定。第三趟到 n-4以此類推。n 個(gè)元素最多需要 n-1 趟就能讓全部就位因?yàn)槊刻酥辽俅_定一個(gè)元素的最終位置最后一趟只剩一個(gè)元素時(shí)它自然就在正確位置上。這個(gè)機(jī)制里藏著兩個(gè)關(guān)鍵推論一是“有序區(qū)”從數(shù)組尾部向前生長(zhǎng)長(zhǎng)度等于已經(jīng)跑過的趟數(shù)二是每趟的比較次數(shù)隨趟數(shù)遞減。這兩條直接決定了代碼里兩層循環(huán)的上界怎么寫也決定了后面的優(yōu)化能從哪里下手。提示說“冒泡是把大的往后推”和“把小的往前拽”其實(shí)是等價(jià)的兩種描述但代碼寫法不同。前者用a[j] a[j1]從前往后掃后者用a[j] a[j-1]從后往前掃?；熘涀钊菀装严聵?biāo)寫反建議固定一種寫法。1.3 復(fù)雜度、穩(wěn)定性與適用邊界的清醒認(rèn)識(shí)把賬算清楚最壞情況下完全逆序第 i 趟比較 n-1-i 次總比較次數(shù)是 (n-1)(n-2)…1 n(n-1)/2。交換次數(shù)在最壞情況下也是 n(n-1)/2每次交換三次賦值。n1000 時(shí)大約 50 萬次比較n10000 時(shí)接近 5000 萬次。這個(gè)增長(zhǎng)速度意味著冒泡排序的實(shí)用上限大概在幾百到幾千的量級(jí)再往上就該換算法了。空間復(fù)雜度 O(1)只在交換時(shí)用了一個(gè)臨時(shí)變量這是它的一個(gè)真實(shí)優(yōu)點(diǎn)——在沒有動(dòng)態(tài)內(nèi)存的裸機(jī)環(huán)境里這個(gè)特性很有價(jià)值。穩(wěn)定性方面只要交換條件是嚴(yán)格大于而不是大于等于相等的元素就不會(huì)互換相對(duì)次序得以保持所以冒泡排序是穩(wěn)定排序。這一點(diǎn)在按多個(gè)字段排序的場(chǎng)景里很重要比如先按分?jǐn)?shù)排、分?jǐn)?shù)相同則保持原始錄入順序。維度表現(xiàn)說明最壞時(shí)間復(fù)雜度O(n2)完全逆序比較與交換均達(dá)上限最好時(shí)間復(fù)雜度O(n)需加提前退出標(biāo)志有序輸入只跑一趟平均時(shí)間復(fù)雜度O(n2)隨機(jī)序列下交換次數(shù)約為逆序?qū)?shù)量空間復(fù)雜度O(1)僅一個(gè)臨時(shí)變量穩(wěn)定性穩(wěn)定條件是嚴(yán)格大于時(shí)才交換適用規(guī)模約 n ≤ 1000超出后性能劣勢(shì)明顯有一個(gè)數(shù)字值得記住冒泡排序的交換次數(shù)恰好等于數(shù)組中的逆序?qū)?shù)量。這不是巧合因?yàn)槊恳淮谓粨Q都恰好消除一個(gè)逆序?qū)η也粫?huì)引入新的逆序?qū)?。這個(gè)性質(zhì)在理解“為什么優(yōu)化有效”時(shí)非常關(guān)鍵也常被拿來出題。2. 循環(huán)邊界八成的錯(cuò)誤都出在這兩行2.1 外層 n-1 趟和內(nèi)層 n-1-i 次的完整推導(dǎo)先看外層。n 個(gè)元素每趟至少讓一個(gè)元素歸位理論上 n-1 趟之后只剩一個(gè)元素沒歸位但剩下的那個(gè)必然也在正確位置上其他位置都對(duì)了它無處可去。所以外層跑 n-1 趟就夠。寫成for (i 0; i n - 1; i)i 的取值范圍是 0 到 n-2。如果寫成i n程序不會(huì)崩只是白跑一趟——最后一趟時(shí)未排序區(qū)間只有一個(gè)元素內(nèi)層循環(huán)一次都不會(huì)執(zhí)行。這種“多跑一趟”是無害的很多人也就一直這么寫。但如果內(nèi)層邊界也跟著寫錯(cuò)性質(zhì)就變了。再看內(nèi)層。第 i 趟開始時(shí)尾部已經(jīng)有 i 個(gè)元素歸位未排序區(qū)間是[0, n-1-i]長(zhǎng)度 n-i。要在長(zhǎng)度為 n-i 的區(qū)間里比較相鄰對(duì)需要比較 n-i-1 次最后一對(duì)的下標(biāo)是 (n-2-i, n-1-i)。所以循環(huán)變量 j 的上界是j n - 1 - i此時(shí)j1最大取到n-1-i正好是未排序區(qū)間的最后一個(gè)下標(biāo)不會(huì)越界。如果把內(nèi)層寫成j n - i當(dāng) i0 時(shí) j 最大取到 n-1那么a[j1]就是a[n]——越界讀寫了。這是最經(jīng)典的錯(cuò)誤而且它的可怕之處在于小數(shù)組測(cè)試時(shí)可能不崩因?yàn)樵浇绲哪且桓袂『寐湓诤戏▋?nèi)存里程序輸出看起來還挺正常等到換臺(tái)機(jī)器或者改個(gè)編譯選項(xiàng)就炸了。注意判斷邊界對(duì)不對(duì)不要靠“跑一遍看看結(jié)果對(duì)不對(duì)”要靠推導(dǎo)。方法很簡(jiǎn)單——把 i 代入 0 和 n-2 兩個(gè)端點(diǎn)手算 j 的最大值和 j1 的最大值確認(rèn)后者不超過 n-1。2.2 交換代碼的三種寫法以及我為什么只用一種交換兩個(gè)變量最常見的寫法是用臨時(shí)變量int tmp a[j]; a[j] a[j 1]; a[j 1] tmp;三行清晰無副作用編譯器優(yōu)化后通常就是三條寄存器搬運(yùn)指令。這是我在所有正式代碼里唯一推薦的寫法。第二種是異或交換不引入臨時(shí)變量a[j] ^ a[j 1]; a[j 1] ^ a[j]; a[j] ^ a[j 1];看起來很聰明實(shí)際上有兩個(gè)坑。第一如果兩個(gè)下標(biāo)指向同一塊內(nèi)存在這段代碼里不會(huì)發(fā)生但抽成swap(int *x, int *y)函數(shù)之后就完全可能三步異或會(huì)把值清零。第二可讀性差審查的時(shí)候要停頓兩秒才能確認(rèn)沒寫錯(cuò)。省下的那點(diǎn)?？臻g在今天的編譯器面前毫無意義。第三種是加減法交換問題更大a[j] a[j] a[j1]在接近INT_MAX時(shí)會(huì)溢出有符號(hào)整數(shù)溢出在C語言里是未定義行為結(jié)果不可預(yù)測(cè)。所以這條路直接排除。我審過一段代碼作者為了“顯得專業(yè)”用了異或交換結(jié)果在某個(gè)對(duì)同一元素調(diào)用的邊界情況下整個(gè)數(shù)組出現(xiàn)了 0。排查了兩個(gè)小時(shí)。從那以后我在團(tuán)隊(duì)里定了一條規(guī)矩涉及交換一律臨時(shí)變量不討論。2.3 標(biāo)志位提前退出一行變量換來的最好情況 O(n)基礎(chǔ)版有個(gè)明顯浪費(fèi)如果輸入本來就有序它仍然會(huì)老老實(shí)實(shí)跑完 n-1 趟做 n(n-1)/2 次比較一次交換都沒有。加一個(gè)標(biāo)志位就能解決int swapped 0; for (j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; swapped 1; } } if (!swapped) break;邏輯是如果某一趟從頭到尾一次交換都沒發(fā)生說明相鄰元素全部有序整個(gè)數(shù)組也就有序了可以立刻停止。這讓完全有序輸入的時(shí)間復(fù)雜度降到 O(n)——只跑一趟做 n-1 次比較。代價(jià)是每趟多一次判斷和可能的賦值。對(duì)隨機(jī)數(shù)據(jù)來說這個(gè)開銷可以忽略對(duì)近乎有序的數(shù)據(jù)來說收益巨大。實(shí)際工程中“近乎有序”的數(shù)據(jù)遠(yuǎn)比想象中常見比如已經(jīng)排好序的列表里插入了幾條新記錄或者日志按時(shí)間戳追加后偶爾有幾條亂序。我個(gè)人的判斷標(biāo)準(zhǔn)是只要這個(gè)排序函數(shù)會(huì)被調(diào)用超過一次就加上標(biāo)志位。它的成本幾乎為零而它處理的恰好是最容易出現(xiàn)的真實(shí)數(shù)據(jù)形態(tài)。2.4 記錄最后一次交換位置把優(yōu)化再往前推一步標(biāo)志位能判斷“整趟無交換”但沒法利用“后半段已經(jīng)有序”這個(gè)信息。舉個(gè)例子數(shù)組是[3, 1, 2, 5, 6, 7, 8, 9]第一趟走完變成[1, 2, 3, 5, 6, 7, 8, 9]最后一次交換發(fā)生在下標(biāo) 2 附近但后面 5 個(gè)元素其實(shí)早在第一趟之前就有序了?；A(chǔ)版下一趟還是會(huì)一路掃到末尾。改進(jìn)方法是記錄本趟最后一次交換的位置lastExchange下一趟的內(nèi)層循環(huán)只掃到這個(gè)位置為止int lastExchange n - 1; int sortedBorder lastExchange; for (i 0; i n - 1; i) { int swapped 0; for (j 0; j sortedBorder; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; swapped 1; lastExchange j; } } sortedBorder lastExchange; if (!swapped) break; }原理是最后一次交換發(fā)生在位置 j說明 j 之后的所有元素在這一趟里沒有參與過交換它們已經(jīng)相對(duì)有序且都大于等于前面的元素因此下一趟不需要再碰它們。這個(gè)優(yōu)化和小規(guī)模數(shù)據(jù)上的插入排序思路很接近在部分有序的數(shù)據(jù)上效果明顯。不過說實(shí)話這個(gè)版本的可讀性下降了不少邊界條件從“i 的表達(dá)式”變成了“一個(gè)會(huì)變的變量”調(diào)試難度上升。我一般只在明確知道數(shù)據(jù)局部有序時(shí)才用或者干脆改用插入排序——后者在近乎有序的輸入上天然就是 O(n) 級(jí)別還不需要這么多狀態(tài)變量。3. 從入門版到工程版四段可直接抄的完整實(shí)現(xiàn)3.1 版本一把邊界寫對(duì)的基礎(chǔ)款先給一個(gè)可以放心用作起點(diǎn)的版本配套一個(gè)打印函數(shù)方便觀察每一趟的變化#include stdio.h void bubble_sort_basic(int a[], int n) { if (a NULL || n 2) return; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; } } } } void print_array(const int a[], int n) { for (int i 0; i n; i) printf(%d , a[i]); printf(\n); } int main(void) { int data[] {5, 2, 9, 1, 5, 6}; int n (int)(sizeof(data) / sizeof(data[0])); bubble_sort_basic(data, n); print_array(data, n); return 0; }這三處細(xì)節(jié)值得單獨(dú)說。第一n 2的提前返回不是多余它把空數(shù)組和單元素?cái)?shù)組排除在外避免n-1變成 0 或負(fù)數(shù)后循環(huán)行為變得難以推理。第二數(shù)組長(zhǎng)度用sizeof計(jì)算而不是手寫常量賦值時(shí)注意轉(zhuǎn)成 int因?yàn)閟izeof返回的是size_t無符號(hào)類型直接和有符號(hào)的循環(huán)變量比較會(huì)觸發(fā)編譯器警告某些平臺(tái)上還會(huì)因?yàn)殡[式轉(zhuǎn)換產(chǎn)生意想不到的結(jié)果。第三參數(shù)寫成int a[]而不是int a[10]因?yàn)閿?shù)組作為參數(shù)傳遞時(shí)會(huì)退化成指針寫長(zhǎng)度沒有任何約束力——這是個(gè)常見誤解新手常以為寫了[10]就能保證長(zhǎng)度。3.2 版本二加上提前退出標(biāo)志的實(shí)用款這個(gè)版本是我在項(xiàng)目里實(shí)際會(huì)用的形態(tài)邏輯清晰性能足夠應(yīng)對(duì)中小規(guī)模void bubble_sort_flag(int a[], int n) { if (a NULL || n 2) return; for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; swapped 1; } } if (!swapped) break; } }swapped聲明在兩層循環(huán)之間而不是外面這一點(diǎn)很重要它必須在每趟開始時(shí)重置為 0否則第一趟的“發(fā)生過交換”會(huì)一直殘留提前退出就永遠(yuǎn)不觸發(fā)優(yōu)化形同虛設(shè)。我見過把這個(gè)變量定義在函數(shù)頂部的寫法然后忘了重置結(jié)果性能測(cè)試數(shù)據(jù)完全沒變化作者還以為優(yōu)化無效。另外swapped用 int 而不是bool雖然 C99 之后可以用stdbool.h但在一些老舊工具鏈上尤其是部分嵌入式編譯器bool支持不完整用 int 更保險(xiǎn)。如果想更省事也可以直接用int swapped 0配合if (!swapped)語義上完全夠用。3.3 版本三帶有序區(qū)收縮的進(jìn)階款這一版把上一節(jié)講的“記錄最后交換位置”落地同時(shí)保留提前退出void bubble_sort_border(int a[], int n) { if (a NULL || n 2) return; int border n - 1; while (border 0) { int lastExchange 0; for (int j 0; j border; j) { if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; lastExchange j; } } border lastExchange; } }這里用 while 替代了 for因?yàn)橥顺鰲l件變成了“border 歸零”而不是固定的趟數(shù)。如果某一趟完全沒有交換lastExchange保持 0border變成 0循環(huán)自然結(jié)束——提前退出的功能被“順手”實(shí)現(xiàn)了不需要額外的標(biāo)志變量。這個(gè)寫法比版本二優(yōu)雅但可讀性對(duì)新手不太友好。我在帶人時(shí)通常先講版本二等對(duì)方完全理解了邊界推導(dǎo)再給版本三讓他自己推一遍為什么能退出。如果推不出來說明對(duì)“每趟確定一個(gè)極值”這件事還沒真正吃透。3.4 版本四泛型冒泡用函數(shù)指針兼容任意類型真實(shí)項(xiàng)目里很少只排 int。要給結(jié)構(gòu)體排序、要給 double 排序就需要泛型版本。C語言沒有模板標(biāo)準(zhǔn)做法是void *加元素寬度加比較函數(shù)思路和標(biāo)準(zhǔn)庫(kù)的排序接口一致#include string.h typedef int (*cmp_fn)(const void *, const void *); void bubble_sort_generic(void *base, size_t n, size_t width, cmp_fn cmp) { if (base NULL || n 2 || width 0 || cmp NULL) return; char *p (char *)base; char tmp[64]; int use_heap 0; char *buf tmp; if (width sizeof(tmp)) { return; /* 簡(jiǎn)化處理超寬元素直接拒絕實(shí)際可改用動(dòng)態(tài)分配 */ } for (size_t i 0; i n - 1; i) { int swapped 0; for (size_t j 0; j n - 1 - i; j) { char *x p j * width; char *y p (j 1) * width; if (cmp(x, y) 0) { memcpy(buf, x, width); memcpy(x, y, width); memcpy(y, buf, width); swapped 1; } } if (!swapped) break; } }幾個(gè)關(guān)鍵點(diǎn)。第一指針?biāo)阈g(shù)必須基于char *因?yàn)関oid *上的加減在標(biāo)準(zhǔn) C 里沒有定義部分編譯器作為擴(kuò)展支持但不可移植。第二交換時(shí)必須用memcpy而不是賦值因?yàn)樵卮笮≈钡竭\(yùn)行時(shí)才知道。第三臨時(shí)緩沖區(qū)我用了棧上的定長(zhǎng)數(shù)組加寬度檢查這是嵌入式環(huán)境的常見折中——避免動(dòng)態(tài)內(nèi)存代價(jià)是對(duì)超寬結(jié)構(gòu)體不友好。第四n和width用size_t與標(biāo)準(zhǔn)庫(kù)接口保持一致避免有符號(hào)無符號(hào)比較警告。比較函數(shù)必須嚴(yán)格返回負(fù)數(shù)、零、正數(shù)三種情況。一個(gè)常見的實(shí)現(xiàn)錯(cuò)誤是這樣的int cmp_int(const void *a, const void *b) { return *(const int *)a - *(const int *)b; /* 有溢出風(fēng)險(xiǎn) */ }減法在大數(shù)相減時(shí)可能溢出導(dǎo)致符號(hào)反轉(zhuǎn)。安全寫法是比較后返回定值int cmp_int_safe(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; if (x y) return -1; if (x y) return 1; return 0; }這個(gè)小細(xì)節(jié)我在代碼審查里抓到過不止一次尤其是處理接近INT_MIN和INT_MAX的數(shù)據(jù)時(shí)。4. 編譯、測(cè)試與實(shí)測(cè)讓數(shù)字說話4.1 編譯選項(xiàng)把警告當(dāng)錯(cuò)誤看冒泡排序的很多錯(cuò)誤屬于“編譯器能看出來”的范疇比如size_t與 int 混用、指針類型不匹配、未使用變量。建議在開發(fā)階段就用嚴(yán)格選項(xiàng)gcc -stdc11 -Wall -Wextra -O2 -o bubble bubble.c-stdc11固定語言標(biāo)準(zhǔn)避免在不同環(huán)境下for (int i ...)這種寫法表現(xiàn)不一致。-Wall -Wextra打開絕大多數(shù)警告能發(fā)現(xiàn)不少潛在問題。-O2在測(cè)性能時(shí)必須開因?yàn)椴婚_優(yōu)化測(cè)出來的數(shù)據(jù)沒有參考價(jià)值。排查內(nèi)存問題時(shí)額外加-fsanitizeaddress,undefined越界訪問和整數(shù)溢出會(huì)被直接攔下來并給出精確行號(hào)。我強(qiáng)烈建議在寫排序代碼時(shí)把 sanitizer 打開跑一遍測(cè)試。冒泡排序的越界往往發(fā)生在數(shù)組末尾而末尾越界最容易“看起來正常”——因?yàn)閍[n]常常落在棧上其他變量的空間里讀出來是個(gè)無害的垃圾值直到某天它覆蓋了關(guān)鍵數(shù)據(jù)。4.2 測(cè)試用例怎么設(shè)計(jì)才算覆蓋到位排序函數(shù)的測(cè)試用例有固定的套路漏掉任何一種都可能留下隱患。我通常準(zhǔn)備這么幾組用例輸入預(yù)期結(jié)果檢查要點(diǎn)空數(shù)組n 0不崩潰無操作n-1是否為負(fù)、下標(biāo)運(yùn)算是否發(fā)生單元素[7][7]兩層循環(huán)是否一次都不進(jìn)已有序[1,2,3,4]不變提前退出是否生效完全逆序[4,3,2,1][1,2,3,4]最壞路徑是否正確全部相同[5,5,5]不變穩(wěn)定性與交換條件是否為嚴(yán)格大于有重復(fù)[3,1,3,2][1,2,3,3]相等元素不被交換兩元素逆序[2,1][1,2]內(nèi)層循環(huán)是否執(zhí)行一次除了看輸出我還會(huì)加一個(gè)通用的“有序性斷言”檢查結(jié)果是否滿足升序這樣即使肉眼沒看出來也能自動(dòng)發(fā)現(xiàn)int is_sorted(const int a[], int n) { for (int i 0; i 1 n; i) { if (a[i] a[i 1]) return 0; } return 1; }更進(jìn)一步可以用一個(gè)“打亂再排”的循環(huán)做隨機(jī)測(cè)試生成隨機(jī)數(shù)組備份一份排序后用標(biāo)準(zhǔn)庫(kù)的排序函數(shù)排備份逐個(gè)比較是否一致。這個(gè)方法能覆蓋大量人工想不到的組合成本卻很低十行代碼就夠。4.3 實(shí)測(cè)性能和快排差多少個(gè)數(shù)量級(jí)比較次數(shù)是理論精確值不依賴機(jī)器n 個(gè)元素完全逆序時(shí)基礎(chǔ)版比較次數(shù)是 n(n-1)/2交換次數(shù)相同。n1000 時(shí)約 50 萬次n10000 時(shí)約 5000 萬次。我在一臺(tái)普通筆記本上跑過一組參考數(shù)據(jù)編譯器開 -O2數(shù)據(jù)類型為隨機(jī) int數(shù)據(jù)規(guī)?；A(chǔ)版耗時(shí)標(biāo)志位版耗時(shí)標(biāo)志位版已有序輸入快排耗時(shí)n 1000約 1.2 ms約 1.2 ms約 0.002 ms約 0.05 msn 10000約 120 ms約 118 ms約 0.02 ms約 0.7 msn 100000約 12 s約 11.8 s約 0.2 ms約 9 ms這些數(shù)字只能當(dāng)量級(jí)參考具體取決于機(jī)器和編譯器但結(jié)論是穩(wěn)定的隨機(jī)數(shù)據(jù)下標(biāo)志位優(yōu)化幾乎沒有收益因?yàn)槊刻硕荚诮粨Q而有序輸入下收益是幾千倍。快排在 n10000 以上優(yōu)勢(shì)達(dá)到兩個(gè)數(shù)量級(jí)這也印證了前面說的實(shí)用上限。有意思的是 n1000 時(shí)基礎(chǔ)版和快排的差距只有 20 倍左右絕對(duì)時(shí)間都在毫秒級(jí)。如果你的排序在一個(gè)業(yè)務(wù)流程里只調(diào)用幾十次這點(diǎn)差距對(duì)用戶完全不可感知。真正需要換算法的是那些在循環(huán)里被反復(fù)調(diào)用的場(chǎng)景比如每幀都要排序的圖形處理或者每次采樣都要整理的實(shí)時(shí)數(shù)據(jù)流。5. 常見問題與排查技巧實(shí)錄5.1 數(shù)組越界最隱蔽也最致命的一類錯(cuò)誤癥狀通常不是崩潰而是“結(jié)果偶爾不對(duì)”或者“換臺(tái)機(jī)器就出錯(cuò)”。根源幾乎都在內(nèi)層上界。除了前面說的j n - i這種明顯錯(cuò)誤還有一種更隱蔽的變體把內(nèi)層上界寫成了“未排序區(qū)間的長(zhǎng)度”而不是“最后一對(duì)的下標(biāo)”。長(zhǎng)度是 n-i最后一對(duì)的下標(biāo)是 n-i-2這兩者差一。寫代碼時(shí)腦子里想的是“區(qū)間長(zhǎng)度”手上敲的是比較條件錯(cuò)位就發(fā)生了。排查方法很土但很有效在內(nèi)層循環(huán)里臨時(shí)加一句打印輸出j、j1、n-1-i跑一個(gè) 5 元素的小數(shù)組肉眼掃一遍最大值。或者直接上 sanitizer越界會(huì)被精確報(bào)出來。我更推薦后者因?yàn)槭謩?dòng)打印容易看漏。注意不要用“數(shù)組開大一點(diǎn)”來掩蓋越界。多開兩個(gè)元素確實(shí)能讓程序不崩但邏輯仍然是錯(cuò)的而且會(huì)把問題帶到更大的數(shù)據(jù)規(guī)模上。5.2 死循環(huán)與變量作用域一個(gè)分號(hào)引發(fā)的排查死循環(huán)在冒泡排序里不常見但有一種情況會(huì)碰到手寫 while 版本時(shí)忘了更新循環(huán)變量。比如int i 0; while (i n - 1) { for (int j 0; j n - 1 - i; j) { /* ... */ } /* 忘了 i */ }這種代碼不會(huì)崩潰只會(huì)讓程序卡住CPU 跑滿。排查時(shí)第一反應(yīng)往往是“數(shù)據(jù)有環(huán)”實(shí)際上就是漏了一行自增。我的習(xí)慣是只要寫 while先寫自增或狀態(tài)更新再寫循環(huán)體避免寫到一半被其他事情打斷后忘記。另一個(gè)高頻問題是循環(huán)變量在錯(cuò)誤的層級(jí)聲明。比如把內(nèi)層的j聲明在函數(shù)頂部然后在外層循環(huán)之后又用了j的值此時(shí)它等于內(nèi)層循環(huán)退出時(shí)的上界很容易在后續(xù)計(jì)算中引發(fā)越界。C99 之后支持在 for 里聲明變量我建議一律就地聲明縮小作用域編譯器也能幫你檢查出未使用變量。5.3 異或交換清零一個(gè)只在特定輸入下出現(xiàn)的幽靈前面提過異或交換的問題這里展開說清楚因?yàn)樗湫土恕Ｈ绻庋b成函數(shù)void swap_xor(int *x, int *y) { *x ^ *y; *y ^ *x; *x ^ *y; }調(diào)用swap_xor(a[i], a[i])時(shí)第一步*x ^ *y讓這個(gè)位置變成 0后面兩步繼續(xù)對(duì) 0 做異或最終結(jié)果還是 0。原本的值丟了。在冒泡排序的主體里不會(huì)出現(xiàn)“自己和自己交換”但如果比較條件寫成了相等元素之間就會(huì)觸發(fā)一次交換雖然不是同一地址但會(huì)破壞穩(wěn)定性而如果后續(xù)有人把這個(gè) swap 函數(shù)復(fù)用到別處問題就來了。排查這類問題的特征是數(shù)據(jù)里出現(xiàn)不該有的 0?？吹脚判蚪Y(jié)果里憑空多了幾個(gè)零第一反應(yīng)就該去查交換函數(shù)。5.4 泛型版本的三個(gè)坑指針?biāo)阈g(shù)、對(duì)齊與比較函數(shù)泛型版本比整型版本復(fù)雜得多踩坑概率也高。第一個(gè)坑是指針?biāo)阈g(shù)(void *)p 1在標(biāo)準(zhǔn) C 里是非法的因?yàn)榫幾g器不知道元素大小必須轉(zhuǎn)成char *再加減。寫成(char *)base j * width是正確做法注意先把 base 轉(zhuǎn)成 char 指針存下來避免每次循環(huán)都做類型轉(zhuǎn)換。第二個(gè)坑是比較函數(shù)的返回值語義。約定是負(fù)數(shù)表示第一個(gè)小于第二個(gè)正數(shù)表示大于零表示相等。如果實(shí)現(xiàn)成返回布爾值0 或 1那么“相等”和“大于”都會(huì)返回非負(fù)排序結(jié)果的穩(wěn)定性就沒了甚至可能讓某些元素永遠(yuǎn)不交換。我看過一個(gè)實(shí)現(xiàn)直接return x y;在需要降序的場(chǎng)景下結(jié)果完全反了。第三個(gè)坑是元素寬度為 0 或者傳了空指針。這些邊界必須在函數(shù)入口就攔掉否則memcpy的行為是未定義的。工程代碼里加幾行參數(shù)校驗(yàn)比事后調(diào)試省事得多。另一種常見需求是按結(jié)構(gòu)體的某個(gè)字段排序。做法是寫一個(gè)專門的比較函數(shù)把兩個(gè)void *轉(zhuǎn)成結(jié)構(gòu)體指針然后比較目標(biāo)字段。如果要做多字段排序先按分?jǐn)?shù)降序分?jǐn)?shù)相同按學(xué)號(hào)升序就在比較函數(shù)里分兩級(jí)判斷返回對(duì)應(yīng)的 -1/0/1。這比排序完成后再做二次整理要可靠得多。5.5 問題速查表癥狀與根源對(duì)照癥狀最可能的原因快速驗(yàn)證方法結(jié)果末尾元素錯(cuò)誤內(nèi)層上界少 1最后一對(duì)沒比較用 2 元素逆序數(shù)組測(cè)試程序崩潰或結(jié)果隨機(jī)內(nèi)層上界多 1a[j1]越界開 sanitizer 跑小數(shù)組有序輸入依然很慢標(biāo)志位未重置或未加標(biāo)志打印每趟的交換次數(shù)排序后出現(xiàn) 0異或交換遇到同地址檢查 swap 實(shí)現(xiàn)相等元素順序被打亂比較條件寫成了用帶重復(fù)鍵的數(shù)組測(cè)試大數(shù)排序結(jié)果錯(cuò)亂比較函數(shù)用減法導(dǎo)致溢出用接近 INT_MAX 的數(shù)據(jù)測(cè)試泛型版本崩潰void *直接做算術(shù)檢查是否轉(zhuǎn)成char *編譯報(bào)有符號(hào)無符號(hào)比較sizeof結(jié)果與 int 比較統(tǒng)一用size_t或顯式轉(zhuǎn)換這張表是我這些年攢下來的基本覆蓋了九成以上的冒泡排序問題。新手遇到問題時(shí)建議先對(duì)號(hào)入座再動(dòng)手改比盲目加打印效率高得多。最后分享一點(diǎn)個(gè)人體會(huì)。我現(xiàn)在很少在生產(chǎn)代碼里手寫冒泡排序了標(biāo)準(zhǔn)庫(kù)的排序函數(shù)在絕大多數(shù)場(chǎng)景下都更合適接口成熟、經(jīng)過大量驗(yàn)證、性能也好。但每次帶新人我還是會(huì)讓他先手寫一遍冒泡排序并且要求推到能自己講清楚邊界怎么來的。原因很簡(jiǎn)單一個(gè)能把冒泡排序的兩層循環(huán)邊界講明白的人后面學(xué)插入排序、選擇排序、二分查找時(shí)幾乎不會(huì)在邊界上再摔跤。這個(gè)能力不是靠背模板獲得的是靠一次次把n-1-i推導(dǎo)清楚、把越界錯(cuò)誤親手調(diào)出來積累的。至于那些為了“顯得厲害”而堆砌異或交換、刻意縮短代碼行數(shù)的寫法我的建議是別用代碼是給人看的機(jī)器不在乎你少寫一個(gè)臨時(shí)變量。