聊到排序冒泡排序幾乎是繞不開(kāi)的第一個(gè)算法。它簡(jiǎn)單到讓人覺(jué)得“就這”但實(shí)際寫(xiě)起來(lái)尤其是親手調(diào)試的時(shí)候才體會(huì)到什么叫“一看就會(huì)一寫(xiě)就廢”。對(duì)我來(lái)說(shuō)這個(gè)算法是塊很好的試金石——它不考驗(yàn)智力考驗(yàn)的是你有沒(méi)有真正理解循環(huán)邊界和變量交換也是后端、前端、嵌入式等方向面試時(shí)都愛(ài)問(wèn)的基礎(chǔ)題。這篇文章我準(zhǔn)備從核心思想講到三種主流語(yǔ)言的寫(xiě)法再到優(yōu)化思路和新手必踩的坑最后把冒泡排序和選擇排序放在一起掰扯清楚。剛學(xué)編程的朋友可以把它當(dāng)入門(mén)教程寫(xiě)過(guò)幾段代碼的老哥也能看看優(yōu)化和排查部分保證有收獲。1. 冒泡排序到底在干什么1.1 一句話搞懂核心思路冒泡排序的思路就一句話重復(fù)地遍歷數(shù)組依次比較相鄰的兩個(gè)元素如果順序錯(cuò)了就交換直到整個(gè)數(shù)組有序。每次遍歷的時(shí)候較大的元素會(huì)一點(diǎn)一點(diǎn)地往后“挪”就像水里的氣泡往上升一樣所以叫“冒泡排序”。每一輪遍歷結(jié)束總有一個(gè)數(shù)會(huì)被推到它最終該待的位置——這個(gè)數(shù)就是當(dāng)前未排序區(qū)間里的最大值。這里面最要緊的動(dòng)作是“相鄰比較”。它不是讓某個(gè)元素去和其他所有元素比而是始終比較arr[j]和arr[j1]這種緊挨著的兩個(gè)數(shù)。正是這一條決定了冒泡排序是穩(wěn)定排序也決定了它每一趟能把一個(gè)最大值送到末尾。1.2 用排隊(duì)的故事把算法“演”一遍想象有一隊(duì)人站成一排老師要求按身高從矮到高排好。你從隊(duì)伍最左端開(kāi)始先看第一個(gè)人和第二個(gè)人如果左邊比右邊高就讓兩個(gè)人交換位置接著看第二個(gè)人和第三個(gè)人同樣地左邊高就交換。這樣一路看下去走到隊(duì)伍末尾時(shí)你會(huì)發(fā)現(xiàn)最高那個(gè)人已經(jīng)被“頂”到了最后面就像氣泡浮到了頂。第一趟結(jié)束你成功把全班最高的人放到了最后的位置這個(gè)位置就再也不需要?jiǎng)恿恕５诙酥恍枰幚砬?n-1 個(gè)人同樣的方法第二高的人會(huì)被放到倒數(shù)第二個(gè)位置。如此反復(fù)總共需要 n-1 趟最后一趟只剩一個(gè)人不用再比隊(duì)伍就排好了。這個(gè)故事里藏著兩個(gè)關(guān)鍵點(diǎn)為什么是 n-1 趟以及為什么內(nèi)層比較次數(shù)是 n-1-i。這兩個(gè)問(wèn)題想明白了冒泡排序你就真懂了。1.3 為什么說(shuō)它的名字起得很形象“冒泡”這個(gè)叫法特別貼切。你去看每一趟的比較過(guò)程越小的元素會(huì)越過(guò)它前面的大元素一點(diǎn)一點(diǎn)地向前移動(dòng)。那種在數(shù)組里往前“飄”的感覺(jué)和氣泡從水底升起來(lái)幾乎一模一樣。還有個(gè)說(shuō)法也很有意思如果從最終結(jié)果往回看每一趟結(jié)束最大的數(shù)都準(zhǔn)確地落到了它該待的位置像一顆石子沉到水底。但算法里元素確實(shí)是在“冒”到頂部所以大家還是習(xí)慣叫冒泡。理解這個(gè)名字你就會(huì)記住它的行為特征每趟選出一個(gè)當(dāng)前范圍內(nèi)最大或最小的元素放到正確的一端。2. 三種主流語(yǔ)言實(shí)現(xiàn)與對(duì)比2.1 C語(yǔ)言版數(shù)組與指針的經(jīng)典配合C語(yǔ)言版本是最樸素、也最能看清冒泡排序本質(zhì)的實(shí)現(xiàn)。因?yàn)闆](méi)有現(xiàn)成的交換函數(shù)你手寫(xiě) temp 交換邏輯反而能加深對(duì)“值傳遞”的理解。#include stdio.h void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; int n sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } return 0; }這里有幾個(gè)細(xì)節(jié)值得停下來(lái)看。外層i從 0 到n-2正好是 n-1 趟因?yàn)樽詈笠惶酥皇Ｒ粋€(gè)元素時(shí)不需要比較。內(nèi)層j從 0 到n-2-i是因?yàn)槊恳惶私Y(jié)束后數(shù)組末尾的 i1 個(gè)元素已經(jīng)排好不需要再碰它們。你要是把內(nèi)層條件寫(xiě)成j n - i當(dāng) i 為 0 時(shí) j 可以取到 n-1訪問(wèn)arr[j1]就等于訪問(wèn)arr[n]越界程序直接崩潰。2.2 C版模板和標(biāo)準(zhǔn)庫(kù)讓代碼更通用C 里可以玩得更花一點(diǎn)。用模板把類型抽象出來(lái)函數(shù)既能排 int 數(shù)組也能排 double、float甚至自定義結(jié)構(gòu)體需要重載比較運(yùn)算符。#include iostream #include vector #include algorithm // for std::swap template typename T void bubble_sort(std::vectorT arr) { int n static_castint(arr.size()); for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); } } } } int main() { std::vectorint arr {64, 34, 25, 12, 22, 11, 90}; bubble_sort(arr); for (int x : arr) { std::cout x ; } return 0; }用std::swap的好處是不用自己寫(xiě) temp 邏輯代碼更短也不容易漏掉中間的賦值步驟。但注意std::swap對(duì)復(fù)雜類型可能涉及移動(dòng)或拷貝開(kāi)銷不一定比手寫(xiě)小只是在這種入門(mén)場(chǎng)景里完全不用糾結(jié)。2.3 Java版方法與數(shù)組對(duì)象的封裝Java 版本在思路上和 C 完全一樣區(qū)別在于 Java 的數(shù)組是對(duì)象方法直接改原數(shù)組不需要返回新數(shù)組。這在做算法題的時(shí)候反而方便因?yàn)楹芏嗨㈩}網(wǎng)站都要求原地修改。public class BubbleSort { public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } public static void main(String[] args) { int[] arr {64, 34, 25, 12, 22, 11, 90}; bubbleSort(arr); for (int num : arr) { System.out.print(num ); } } }Java 里因?yàn)闆](méi)有給基本類型數(shù)組提供現(xiàn)成的 swap 方法所以還是手寫(xiě)三行交換。也不要想著用Arrays.sort代替那就不是冒泡排序了。這三個(gè)版本你只要吃透一個(gè)其他語(yǔ)言基本就是換皮邏輯骨架完全一致。對(duì)比項(xiàng)C語(yǔ)言CJava數(shù)組處理數(shù)組長(zhǎng)度參數(shù)vector容器模板數(shù)組對(duì)象交換方式手寫(xiě)temp三行std::swap手寫(xiě)temp三行適用類型僅對(duì)應(yīng)類型通用類型僅對(duì)應(yīng)類型典型場(chǎng)景嵌入式/底層算法競(jìng)賽/工程后端業(yè)務(wù)/刷題3. 從能用走向好用三種經(jīng)典優(yōu)化3.1 提前結(jié)束沒(méi)有交換就收工原始版本的冒泡排序有一個(gè)明顯的問(wèn)題即使數(shù)組本來(lái)就有序它照樣兢兢業(yè)業(yè)地比較 n(n-1)/2 次。比如[1, 2, 3, 4, 5]第一趟從頭比到尾一次交換都沒(méi)發(fā)生這時(shí)候就可以斷定數(shù)組已經(jīng)有序直接退出。優(yōu)化方法就是加一個(gè)標(biāo)志位swapped。每一趟開(kāi)始時(shí)置為 false只要發(fā)生任何一次交換就置為 true。一趟結(jié)束后檢查這個(gè)標(biāo)志如果還是 false說(shuō)明整趟下來(lái)沒(méi)有需要調(diào)整的元素后面也不需要再比了。void bubble_sort_early_exit(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (swapped 0) { break; } } }這個(gè)優(yōu)化效果非常直觀最好情況下一開(kāi)始就發(fā)現(xiàn)有序時(shí)間復(fù)雜度從 O(n^2) 直接降到 O(n)。實(shí)際開(kāi)發(fā)中如果數(shù)據(jù)本身有序或接近有序這個(gè)標(biāo)志位能省下大量無(wú)效比較。3.2 記錄最后一次交換的位置縮小掃描范圍第二個(gè)優(yōu)化稍微進(jìn)階一點(diǎn)。每一趟內(nèi)層循環(huán)結(jié)束之前最后一次發(fā)生交換的位置lastSwap之后的元素其實(shí)已經(jīng)全部有序了。下一趟循環(huán)完全不用掃描到 n-1-i只需要掃到lastSwap就行了。void bubble_sort_tail_mark(int arr[], int n) { int lastSwap n - 1; while (lastSwap 0) { int currentSwap 0; for (int j 0; j lastSwap; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; currentSwap j; } } lastSwap currentSwap; } }這里currentSwap記錄的不是交換次數(shù)而是最后一次交換發(fā)生時(shí) j 的位置。下一趟只需要遍歷到這個(gè)位置它之后的部分已經(jīng)確定有序。對(duì)于“數(shù)組后面大半已經(jīng)有序”這類情況這個(gè)技巧能省一半甚至更多的比較次數(shù)。3.3 雞尾酒排序雙向冒泡效率翻倍雞尾酒排序也叫雙向冒泡排序思路是一趟從左往右把最大值送到末尾下一趟從右往左把最小值送到開(kāi)頭來(lái)回交替像調(diào)雞尾酒一樣。void cocktail_sort(int arr[], int n) { int left 0; int right n - 1; while (left right) { for (int i left; i right; i) { if (arr[i] arr[i 1]) { int temp arr[i]; arr[i] arr[i 1]; arr[i 1] temp; } } right--; for (int i right; i left; i--) { if (arr[i - 1] arr[i]) { int temp arr[i - 1]; arr[i - 1] arr[i]; arr[i] temp; } } left; } }這種寫(xiě)法在“大部分元素有序只有少數(shù)幾個(gè)元素待歸位”的場(chǎng)景里優(yōu)勢(shì)特別明顯。舉個(gè)例子[2, 3, 4, 5, 1]普通冒泡需要把 1 從最左邊一路換到最右邊過(guò)程非常漫長(zhǎng)雞尾酒排序在第二趟回掃時(shí)就能把 1 快速帶到最前面。不過(guò)它仍然處理不了真正的亂序數(shù)組復(fù)雜度還是 O(n^2)只是常數(shù)因子小了一些。4. 冒泡排序和選擇排序怎么選4.1 兩者核心差異在“交換”選擇排序的思路和冒泡完全不同每一趟掃描未排序區(qū)間找到最小值所在的下標(biāo)一趟結(jié)束后只交換一次把這個(gè)最小值放到正確的位置。它不進(jìn)行大量的相鄰交換而是記錄位置最后統(tǒng)一換。這個(gè)差異在數(shù)據(jù)規(guī)模變大時(shí)體現(xiàn)得很明顯。假設(shè)有 n 個(gè)數(shù)冒泡排序最壞情況下要做 n(n-1)/2 次交換選擇排序不管數(shù)據(jù)多亂每一趟最多交換一次總共最多 n-1 次交換。如果數(shù)組里的元素是大型結(jié)構(gòu)體一次交換的代價(jià)可能是拷貝幾百字節(jié)的數(shù)據(jù)這時(shí)候選擇排序的優(yōu)勢(shì)就出來(lái)了。4.2 穩(wěn)定性到底差在哪選擇排序有一個(gè)致命的問(wèn)題它是不穩(wěn)定的。原因在于它做的是“跳躍式交換”——把最小值直接換到前面可能會(huì)把兩個(gè)相等元素的相對(duì)順序打亂。比如數(shù)組[3a, 3b, 1]選擇排序會(huì)把 1 換到最前面那 3a 和 3b 誰(shuí)在前面就取決于實(shí)現(xiàn)細(xì)節(jié)大概率變成[1, 3b, 3a]原來(lái) 3a 在 3b 前面的相對(duì)順序被破壞了。冒泡排序只交換相鄰元素相等的元素不會(huì)被交換所以能保持原來(lái)的相對(duì)順序是穩(wěn)定的排序算法。如果你后續(xù)還要按其他字段排序穩(wěn)定性就很重要。比如先按姓名排序再按年齡排序穩(wěn)定的排序可以保證年齡相同的人仍然按姓名排列。4.3 實(shí)際開(kāi)發(fā)中該怎么選說(shuō)了這么多理論落到實(shí)際中我就給大家一個(gè)可以直接抄作業(yè)的結(jié)論元素?cái)?shù)量小于 100 甚至幾十兩者性能差異肉眼感覺(jué)不到選哪個(gè)全看你更熟悉哪個(gè)。元素是大型結(jié)構(gòu)體一次賦值開(kāi)銷很大優(yōu)先選選擇排序因?yàn)樗粨Q次數(shù)少。需要保持相等元素的相對(duì)順序有多個(gè)排序字段需求選冒泡。數(shù)據(jù)幾乎有序用加了提前退出優(yōu)化的冒泡效果遠(yuǎn)超選擇排序。數(shù)據(jù)量一旦到千級(jí)、萬(wàn)級(jí)這兩個(gè)都不太行了直接上快排、歸并這類更高效的排序。對(duì)比維度冒泡排序選擇排序平均時(shí)間復(fù)雜度O(n^2)O(n^2)最好時(shí)間復(fù)雜度O(n)優(yōu)化后O(n^2)最壞時(shí)間復(fù)雜度O(n^2)O(n^2)空間復(fù)雜度O(1)O(1)交換次數(shù)最多 n(n-1)/2最多 n-1穩(wěn)定性穩(wěn)定不穩(wěn)定實(shí)現(xiàn)難度極簡(jiǎn)簡(jiǎn)單5. 新手最容易踩的坑與排查實(shí)錄5.1 數(shù)組越界是最狠的一刀冒泡排序里的越界問(wèn)題幾乎都出在內(nèi)層循環(huán)的邊界上。我見(jiàn)過(guò)最典型的寫(xiě)法是for (int j 0; j n - i; j)然后循環(huán)體里寫(xiě)if (arr[j] arr[j1])。當(dāng) i0 時(shí)j 最大能取到 n-1arr[j1]就是arr[n]直接越界。C 語(yǔ)言對(duì)越界訪問(wèn)往往不會(huì)直接報(bào)錯(cuò)而是讀到一塊未知內(nèi)存數(shù)值千奇百怪結(jié)果排序亂得毫無(wú)規(guī)律。更可怕的是如果越界的那塊內(nèi)存恰好在寫(xiě)操作范圍內(nèi)你可能會(huì)悄悄把別的變量改掉。調(diào)試這種問(wèn)題不如直接從根上記住外層 i 次數(shù)是 n-1內(nèi)層 j 終點(diǎn)是 n-1-i多一個(gè)都不行。5.2 比較符號(hào)寫(xiě)反排序順序全反如果你想要升序應(yīng)該是if (arr[j] arr[j1])才交換也就是“左邊比右邊大就換”。很多人緊張的時(shí)候會(huì)寫(xiě)成結(jié)果變成“左邊比右邊小就換”一趟跑完數(shù)組從升序變成了降序而且程序完全正常、不報(bào)錯(cuò)特別難排查。減少符號(hào)錯(cuò)誤的技巧是先把需求用中文說(shuō)出來(lái)“把大的往后挪”然后翻譯成代碼就是arr[j] arr[j1]時(shí)交換。你要是搞不清降序怎么寫(xiě)就反過(guò)來(lái)想“把小的往后挪”那條件就是arr[j] arr[j1]。5.3 死循環(huán)的出入口控制while 版本比 for 版本更容易寫(xiě)出死循環(huán)。比如有人想用while (i n-1)控制外層循環(huán)卻忘了讓 i 自增或者內(nèi)層用 while 控制 j忘記在循環(huán)體末尾更新 j。遇到這種情況程序就會(huì)一直停在原地交換同一對(duì)元素CPU 直接拉滿風(fēng)扇狂轉(zhuǎn)。我排查死循環(huán)的思路是先看循環(huán)變量有沒(méi)有向退出條件推進(jìn)的變化再看退出條件是不是永遠(yuǎn)為真。在冒泡排序的場(chǎng)景中i和j必須按預(yù)期自增n不能在中途被修改。最好的預(yù)防辦法是盡量用 for 循環(huán)把循環(huán)變量的初始化、條件判斷、自增寫(xiě)在同一個(gè)地方不容易漏。5.4 空數(shù)組和單元素?cái)?shù)組很多新手寫(xiě)的排序函數(shù)丟進(jìn)空數(shù)組或者只有一個(gè)元素的數(shù)組就直接崩了。原因是代碼里沒(méi)做長(zhǎng)度判斷n - 1可能變成負(fù)值循環(huán)直接進(jìn)入奇怪的狀態(tài)。if (n 1) { return; }像這樣的防御性判斷放在函數(shù)開(kāi)頭幾毫秒的性能損失可以忽略不計(jì)但能避免大量邊界問(wèn)題。這也是工程代碼和練習(xí)代碼的區(qū)別工程代碼里你永遠(yuǎn)要假設(shè)輸入可能是任何離譜的數(shù)據(jù)。5.5 常見(jiàn)錯(cuò)誤速查表為了方便大家排查我把實(shí)際輔導(dǎo)過(guò)程中遇到的高頻問(wèn)題整理成了表格按出現(xiàn)頻率排序癥狀可能原因處理方式排序后結(jié)果亂序內(nèi)層循環(huán)越界訪問(wèn)檢查j n - 1 - i輸出為降序比較符號(hào)寫(xiě)反換成arr[j] arr[j1]數(shù)組沒(méi)變交換邏輯忘記寫(xiě)檢查有沒(méi)有 temp 三行交換程序卡死不動(dòng)while 循環(huán)變量未更新改用 for 循環(huán)空數(shù)組崩潰缺少長(zhǎng)度判斷開(kāi)頭加if (n 1) return重復(fù)元素順序變了用了統(tǒng)一改成6. 復(fù)雜度分析與適用邊界6.1 時(shí)間復(fù)雜度是怎么算出來(lái)的冒泡排序的時(shí)間復(fù)雜度推導(dǎo)非常直觀不需要高等數(shù)學(xué)。外層循環(huán)跑 n-1 趟第一趟內(nèi)層比較 n-1 次第二趟 n-2 次第三趟 n-3 次……最后一趟 1 次?？偟谋容^次數(shù)就是(n-1) (n-2) ... 1這是一個(gè)等差數(shù)列求和結(jié)果是n(n-1)/2。當(dāng) n 足夠大時(shí)n(n-1)/2約等于n^2/2所以時(shí)間復(fù)雜度為 O(n^2)。最壞的情況是完全逆序的數(shù)組每一趟每一次比較都需要交換比較次數(shù)和交換次數(shù)都是 n(n-1)/2最好的情況是數(shù)組已經(jīng)有序優(yōu)化版本只需要 n-1 次比較就能結(jié)束時(shí)間復(fù)雜度降到 O(n)?？臻g復(fù)雜度是 O(1)因?yàn)檎麄€(gè)排序過(guò)程只用了 temp 這一個(gè)額外變量原地完成排序不隨 n 增長(zhǎng)而增長(zhǎng)。6.2 穩(wěn)定性為什么是它的王牌屬性前面提到過(guò)冒泡排序是穩(wěn)定排序。這里我想補(bǔ)充一個(gè)細(xì)節(jié)穩(wěn)定性不是所有排序都有的快排、選擇排序都不穩(wěn)定歸并排序穩(wěn)定但實(shí)現(xiàn)復(fù)雜。在很多真實(shí)業(yè)務(wù)里比如訂單先按金額排序再按時(shí)間排序如果排序算法不穩(wěn)定第二次排序就可能把相同金額的訂單順序打亂。冒泡排序即使在沒(méi)有優(yōu)化的版本里也只在arr[j] arr[j1]時(shí)交換。遇到兩個(gè)相等的元素它不會(huì)交換它們所以相等元素的相對(duì)位置始終保持不變。這一特性在需要多關(guān)鍵字排序時(shí)是無(wú)價(jià)之寶。6.3 什么場(chǎng)景才值得用冒泡排序聊到這里很多人會(huì)問(wèn)既然 O(n^2)為什么還要學(xué)它、用它我自己的理解是冒泡排序的價(jià)值主要在三個(gè)地方一是教學(xué)它的邏輯足夠簡(jiǎn)單是建立“循環(huán)交換”心智模型最好的素材二是小數(shù)據(jù)集數(shù)據(jù)量不超過(guò)幾十個(gè)時(shí)哪怕是 O(n^2)在實(shí)際運(yùn)行中也是毫秒級(jí)的事用冒泡排序反而代碼最簡(jiǎn)潔、最難出錯(cuò)三是面試面試官問(wèn)排序算法時(shí)如果你能先快速寫(xiě)出一個(gè)正確的冒泡排序然后自然講出優(yōu)化方案再對(duì)比分析復(fù)雜度這本身就是一種高級(jí)的溝通能力。在工程上我見(jiàn)過(guò)有人在嵌入式設(shè)備上用它處理不到 50 個(gè)元素的緩沖區(qū)排序因?yàn)閷?shí)現(xiàn)短小、無(wú)遞歸、不占?？臻g還方便移植到各種架構(gòu)。指望用冒泡排序處理百萬(wàn)級(jí)數(shù)據(jù)那肯定是選型問(wèn)題不是算法本身的問(wèn)題。最后分享一個(gè)小技巧初學(xué)階段建議拿撲克牌或者紙片寫(xiě)數(shù)字按冒泡排序的規(guī)則手動(dòng)“跑”一遍你真的會(huì)看到那個(gè)“氣泡”是怎么冒出來(lái)的。我當(dāng)年就是靠這個(gè)動(dòng)作徹底理解了它之后看任何語(yǔ)言的寫(xiě)法都覺(jué)得是理所當(dāng)然。排序作為計(jì)算機(jī)科學(xué)里最基礎(chǔ)的一類算法冒泡排序又是這條路上最平的臺(tái)階踩穩(wěn)了后面爬任何一座山都會(huì)輕松不少。