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