化：相鄰交換、穩(wěn)定排序與時間復雜度解析)
1. 冒泡排序到底在干什么冒泡排序真的是排序算法里最貼近直覺的一個我當初學它的時候幾乎沒費什么勁。你想象一個水池水底有一堆大小不一的石頭大的石頭天然沉底小的氣泡往上飄。冒泡排序的每一趟循環(huán)就像一次“讓一個最大的值慢慢浮到正確位置”的過程所以這個算法的名字起得非常形象。它解決的問題很簡單給我一組亂序的數(shù)字我通過反復比較相鄰的兩個元素如果順序不對就交換它們的位置最終讓整個序列排列整齊。這個“反復比較相鄰元素并交換”的動作就是冒泡排序的全部核心沒有復雜的遞歸沒有精巧的分治就是老老實實地一遍遍掃過去。我剛接觸編程的時候?qū)W的第一個排序算法就是它。那時候不理解時間復雜度也不關心什么是穩(wěn)定排序我就是把代碼敲了一遍然后指著打印出來的結(jié)果說“哦原來排序是這么回事”。所以如果你剛?cè)腴T編程拿冒泡排序當作理解“算法到底是什么”的第一個例子是很合適的。這個算法適合誰來學我覺得有三類人第一類是剛接觸數(shù)據(jù)結(jié)構(gòu)和算法的大學生需要一個不那么嚇人的入門案例第二類是準備面試的開發(fā)者雖然冒泡排序在工程里基本不會用但面試官偶爾會拿它考基本功尤其是它的優(yōu)化寫法第三類是自學編程的朋友你可能沒有系統(tǒng)的算法課想通過一個簡單的例子建立對代碼執(zhí)行流程的直覺。這篇文章我會從思路、代碼、實操、踩坑四個維度把它講透最后還會拿它和選擇排序做個對比幫你看清楚為什么它簡單但確實不是效率最優(yōu)的選擇。2. 設計思路拆解三個關鍵問題想明白代碼自然就寫出來了2.1 為什么是“相鄰比較”而不是“隨便挑兩個比”冒泡排序最核心的動作是每一輪循環(huán)里依次比較相鄰的兩個元素也就是第0個和第1個、第1個和第2個這樣一路比到最后一個。如果左邊的數(shù)大于右邊的數(shù)就交換它們的位置。為什么非要相鄰比較這里面其實藏著一個很重要的設計邏輯每一次交換都讓一個較大的值向序列末尾方向移動一位經(jīng)過一整趟的比較就能確定一個“本輪最大的值”被推到了它最終應該在的位置。這種“一趟確定一個最終位置”的特性讓整個排序過程天然是收斂的。你不需要額外記錄什么極值下標也不需要額外的數(shù)據(jù)結(jié)構(gòu)幫你存儲中間狀態(tài)就靠相鄰交換信息自然傳遞。如果你跳著比較比如把第0個元素和第3個元素比較那確實也能找出來最大值但中間那幾個元素的狀態(tài)完全沒被整理你需要額外寫很多邏輯才能保證整個序列有序。所以說相鄰比較正好是“信息傳遞最直接、代碼最簡單”的方式這也是冒泡排序設計上的巧思。2.2 為什么需要多輪循環(huán)每輪掃描的范圍為什么越來越小光一趟掃描肯定不夠。第一趟掃描結(jié)束你只能保證最大值到了最后前面還有一堆亂序的數(shù)字。所以需要再來一趟把第二大的值推到倒數(shù)第二的位置再第三趟推出第三大的值……總共需要 n-1 趟n 是元素個數(shù)。這里有一個特別容易忽略的細節(jié)每一趟掃描的范圍在縮小。第一趟掃描到最后一個位置第二趟其實只需要掃描到倒數(shù)第二個位置因為最后一個位置已經(jīng)是最大值再去比較它純屬浪費。這個“每趟少比較一個位置”的優(yōu)化是初學冒泡排序時最容易忘記的。很多教科書代碼里會這么寫for (int i 0; i n-1; i) { for (int j 0; j n-1-i; j) { // 比較并交換 } }注意內(nèi)層循環(huán)的條件是n-1-i不是n-1。這就是在每一輪掃描中自動把已經(jīng)排好的尾部區(qū)域排除掉。我見過不少人把這個-i丟了程序其實也能跑出正確結(jié)果因為多比較的只是已經(jīng)排好序的元素不會產(chǎn)生錯誤但效率確實低了一截。這種丟寫法只能說“僥幸正確”不嚴謹。2.3 穩(wěn)定排序是什么意思冒泡為什么天生是穩(wěn)定的冒泡排序是穩(wěn)定排序。所謂穩(wěn)定就是如果兩個元素的值相同它們在排序完成后的相對順序不會改變。比如有兩個同為 5 的數(shù)字一開始前面的那個 5排完序之后依然在前面。冒泡排序為什么天然穩(wěn)定因為它的交換條件寫的是“如果左邊的大于右邊才交換”注意是嚴格大于不是大于等于。如果兩個元素相等條件不成立就不會交換所以相同值的相對順序被保住了。這一點在大部分普通場景下沒什么感覺但當你排序的是對象比如員工對象按工資排序而工資相同的員工希望保持原來的入職順序那穩(wěn)定排序就很有意義。我以前寫一個報表工具時需要在兩輪排序的基礎上保持前一輪的排序痕跡穩(wěn)定排序就成了唯一合理的選擇。所以不要覺得穩(wěn)定性只是一個概念題實際工程里是真的會用到的。3. 核心細節(jié)實操用代碼把冒泡排序?qū)懗鰜聿⒗斫饷恳恍械暮x3.1 C語言版本最接近底層的寫法幫你建立內(nèi)存視角C語言的實現(xiàn)最直觀因為它讓你直面數(shù)組操作和交換邏輯。先看一個最基礎版本#include stdio.h void bubbleSort(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[j1]) { // 交換兩個數(shù) int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; } } } } int main() { int arr[] {5, 1, 4, 2, 8}; int n sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } return 0; }這里的sizeof(arr) / sizeof(arr[0])是C語言里計算數(shù)組長度最常用的方式sizeof(arr)是整個數(shù)組占用的總字節(jié)數(shù)除以單個元素的字節(jié)數(shù)就得到元素個數(shù)。記住這個寫法面試和筆試經(jīng)常用。交換邏輯用了臨時變量temp這是最樸素的交換思想。兩個杯子要互換液體必須先有一個空杯子。這個類比幫我理解了很多年的交換操作。3.2 Java版本更符合工程習慣的寫法Java里的寫法在思路上完全一致只是語法有些區(qū)別。Java傳入數(shù)組本身就是引用傳遞所以在方法內(nèi)直接修改數(shù)組外面的變量也會隨之改變這一點和C語言通過指針傳入是異曲同工的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[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] 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版本需要注意的細節(jié)是arr.length是一個屬性不是方法所以別寫arr.length()。初學Java從C語言轉(zhuǎn)過來的人經(jīng)常在這個地方犯迷糊C語言是sizeof(arr)/sizeof(arr[0])Java直接.length兩個語言的風格差異就在這里體現(xiàn)出來了。3.3 Python版本最簡潔的表達適合快速驗證思路Python的寫法可以把冒泡排序壓縮到幾乎不能再短def bubble_sort(arr): n len(arr) for i in range(n-1): for j in range(n-1-i): if arr[j] arr[j1]: arr[j], arr[j1] arr[j1], arr[j] return arr if __name__ __main__: test [5, 1, 4, 2, 8] print(bubble_sort(test))Python的arr[j], arr[j1] arr[j1], arr[j]這種并行賦值寫法底層其實是一口氣完成了取值和賦值不需要臨時變量。這個語法糖寫起來很爽但要注意右邊是“先算完再統(tǒng)一賦值”理解了這個你就不會擔心順序錯亂的問題。Python版最適合什么場景當你腦子里有了一個算法的模糊想法想快速驗證一下對不對用Python最合適寫起來省時間能讓你把注意力集中在邏輯上而不是語言細節(jié)上。3.4 最關鍵的那行代碼為什么是j n-1-i少個-i行不行這一小節(jié)我要重點講因為它是冒泡排序無數(shù)初學者最容易栽跟頭的地方。外層循環(huán)控制的是“一共要跑幾趟”n 個元素最多需要 n-1 趟。為什么是 n-1因為當 n-1 個元素已經(jīng)跑到正確位置之后剩下的那一個元素自然就在正確位置了不需要再處理。這是排序算法的通用邏輯。內(nèi)層循環(huán)控制的是“這一趟比較哪些位置”。第一趟j 從 0 掃到 n-2也就是說比較第0和第1個、第1和第2個、……、第n-2和第n-1個覆蓋整個數(shù)組。每比較一次如果左邊大于右邊就交換一趟結(jié)束最大的值到了最后。第二趟開始就不同了。最后一個位置已經(jīng)是最大值我再去比較第 n-2 和第 n-1 個是毫無意義的比較。所以第二趟只需要掃到 n-2 即止也就是j n-2。第三趟需要掃到 n-3以此類推。用i表示當前是第幾趟那這一趟的掃描上限就是n-1-i。如果你寫成j n-1代碼依然能正確排序因為多比較的那些部分不會產(chǎn)生錯誤交換只是白白消耗了CPU時間。對于算法學習來說這是不合格的因為算法的意義之一就是效率而效率就藏在這些細節(jié)里。4. 實操過程還原從一個亂序數(shù)組開始手動走一遍排序過程4.1 用例子走完整流程我拿[5, 1, 4, 2, 8]這個數(shù)組來手動模擬一遍冒泡排序的每一輪狀態(tài)這是理解冒泡排序最快的辦法。強烈建議你也用紙筆畫一遍只看代碼是形成不了直覺的。第一趟i0j 從 0 掃到 3比較 j05 和 151交換數(shù)組變成[1, 5, 4, 2, 8]比較 j15 和 454交換數(shù)組變成[1, 4, 5, 2, 8]比較 j25 和 252交換數(shù)組變成[1, 4, 2, 5, 8]比較 j35 和 858不交換數(shù)組保持[1, 4, 2, 5, 8]第一趟結(jié)束8 這個最大的數(shù)已經(jīng)浮到了最后它的位置確定了。第二趟i1j 從 0 掃到 2比較 j01 和 414不交換比較 j14 和 242交換數(shù)組變成[1, 2, 4, 5, 8]比較 j24 和 545不交換第二趟結(jié)束5 的位置確定了。第三趟i2j 從 0 掃到 1比較 j01 和 212不交換比較 j12 和 424不交換第三趟結(jié)束沒有發(fā)生任何交換。第四趟i3j 從 0 掃到 0比較 j01 和 212不交換全部結(jié)束數(shù)組已經(jīng)有序。注意一個細節(jié)第三趟結(jié)束的時候?qū)嶋H上就已經(jīng)完全有序了但冒泡排序不知道它還會繼續(xù)跑第四趟。這就是為什么它需要額外的優(yōu)化手段來處理這些無用的趟數(shù)這部分在后面的常見問題章節(jié)我會詳細講。4.2 手動走一遍之后觀察到了什么規(guī)律手動模擬完有三個規(guī)律是我希望你能自己體會到的第一每一趟都能確定一個最大值到它最終的位置這個位置是從后往前依次確定的。所以外層循環(huán)跑完 n-1 趟之后所有位置都確定了。第二數(shù)組如果本來接近有序冒泡排序也不會自動“感知”到這一點它依然傻傻跑完全部趟數(shù)除非你加了優(yōu)化。這也是它和插入排序的一個重要區(qū)別插入排序在接近有序的數(shù)據(jù)上表現(xiàn)非常好冒泡排序在沒有優(yōu)化的情況下不行。第三交換操作發(fā)生的位置和次數(shù)是沒有規(guī)律的。有時候這趟交換了很多次有時候一次都沒有。所以判斷一個數(shù)組是否提前完成排序就看某一趟有沒有發(fā)生任何交換這也是“哨兵優(yōu)化”的思想基礎。4.3 用表格看每一輪的變化我把上面的過程整理成表格方便你對照。趟數(shù)掃描范圍比較過程是否有交換本輪結(jié)束后的數(shù)組第1趟j0~35和1交換5和4交換5和2交換5和8不換是[1, 4, 2, 5, 8]第2趟j0~21和4不換4和2交換4和5不換是[1, 2, 4, 5, 8]第3趟j0~11和2不換2和4不換否[1, 2, 4, 5, 8]第4趟j0~01和2不換否[1, 2, 4, 5, 8]這個表格建議你親手畫一遍。我見過很多學生代碼寫得很溜但問他[3,1,2]排序過程中第二趟長什么樣他就答不上來。這類問題面試經(jīng)常考畫圖能力代表了你對算法的真實理解程度。5. 常見問題與踩坑復盤運行結(jié)果不對先想想這4個地方5.1 問題一為什么我的輸出沒有變化數(shù)組好像完全沒被排序出現(xiàn)這種情況最典型的錯誤是交換邏輯沒生效。我見過有人把交換寫成這樣arr[j] arr[j1]; arr[j1] arr[j];很明顯第一步執(zhí)行之后arr[j]已經(jīng)被覆蓋了第二步賦值等于把同一個值寫了兩遍數(shù)組自然沒變化。正確寫法必須借助臨時變量或者用像Python那樣的一次性賦值。這種問題在C和Java里很常見因為它們的賦值是“先算右邊再把結(jié)果覆蓋左邊”不會自動保留原值。另一個可能原因是你傳參的方式不對。C語言里如果你傳的是數(shù)組的副本而不是指針函數(shù)內(nèi)部修改就不會影響到外部數(shù)組。Java里數(shù)組是引用傳遞基本不會踩這個坑。C里如果你寫函數(shù)時形參用了vectorint而不是vectorint也會發(fā)生拷貝排序只作用于副本。5.2 問題二循環(huán)邊界條件到底怎么記每次寫都要翻書邊界條件這塊我提供一個記憶口訣外層循環(huán)i從 0 到 n-2內(nèi)層循環(huán)j從 0 到 n-i-2那么比較的下標就是arr[j]和arr[j1]。這個口訣等價于上面的代碼但更好記因為 j 的最大值是 n-i-2所以 j1 的最大值是 n-i-1也就是當前趟數(shù)需要處理的最后一個元素位置。如果你不放心可以隨手代入數(shù)字驗證n5i0 時j 最大是3比較的是arr[3]和arr[4]覆蓋了所有元素。i3 時j 最大是0比較的是arr[0]和arr[1]只比較最前面的一對。這樣算下來邏輯就通順了。5.3 問題三我加了優(yōu)化為什么反而排錯序了很多人在理解了冒泡排序之后會想著加一個“提前結(jié)束”的優(yōu)化如果某一趟沒有發(fā)生任何交換就說明數(shù)組已經(jīng)有序直接退出循環(huán)。這個思路是對的但實現(xiàn)的時候容易出錯。常見的錯誤寫法是這樣的for (int i 0; i n-1; i) { int flag 0; for (int j 0; j n-1-i; j) { if (arr[j] arr[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; flag 1; } } // 下面的寫法是錯誤的 // if (flag) break; }注意flag 1表示發(fā)生了交換那么“沒有發(fā)生交換”應該是flag 0退出條件應該是if (!flag) break;。如果你寫成if (flag) break;那就變成“只要有交換就退出”只跑一趟就結(jié)束了排序結(jié)果當然不對。這個坑我當年也踩過本質(zhì)上是把標志位的語義搞反了。寫優(yōu)化代碼時建議先把“這個變量到底表示什么”想清楚再寫判斷條件。我這里貼一個正確的優(yōu)化版本void bubbleSortOptimized(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[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; swapped 1; } } if (swapped 0) { break; } } }5.4 問題四數(shù)據(jù)量一大就慢得離譜是不是我寫錯了不是寫錯了是冒泡排序本身確實慢。它的時間復雜度是 O(n2)什么意思如果數(shù)組有 1000 個元素內(nèi)外兩層循環(huán)大概要執(zhí)行百萬次比較操作如果數(shù)組有 10000 個元素就要上億次比較。這個增長速度是平方級別的數(shù)據(jù)量翻一倍耗時大約翻四倍。所以工程上沒人用冒泡排序處理大規(guī)模數(shù)據(jù)這是正常的。如果你只是寫完代碼做測試建議用幾百個元素的數(shù)組感受一下邏輯不要去排 10 萬個數(shù)。真要對大數(shù)組排序用 C 標準庫的qsortJava 的Arrays.sort()或者 C 的std::sort這些底層都是快排、歸并這類 O(n log n) 的算法性能差距是數(shù)量級的。6. 選擇排序和冒泡排序?qū)Ρ日l更好什么時候用哪個6.1 選擇排序的思路回顧選擇排序和冒泡排序經(jīng)常被放在一起比較因為它們的實現(xiàn)難度差不多思路也都是在每一輪中確定一個元素的最終位置。區(qū)別在于選擇排序不再是相鄰元素交換而是每一輪在剩余未排序部分里找出最小值或最大值記錄它的下標等這一輪掃描結(jié)束后再把它和當前輪次的起始位置交換。舉個例子[5, 1, 4, 2, 8]第一輪掃描全部元素找到最小值 1 在下標1的位置然后讓下標0的位置和下標1的位置交換得到[1, 5, 4, 2, 8]。第二輪掃描下標1到4的部分找到最小值 2交換到下標1得到[1, 2, 4, 5, 8]。以此類推。6.2 冒泡和選擇的核心差異兩者在時間復雜度上是一樣的都是 O(n2)。但在實際行為上差別很大冒泡排序每一輪可能需要很多次交換而選擇排序每一輪最多只交換一次。所以雖然比較次數(shù)差不多但選擇排序的“數(shù)據(jù)搬動”次數(shù)遠小于冒泡排序在交換代價較高的場景里選擇排序更優(yōu)一些。再看穩(wěn)定性冒泡排序是穩(wěn)定的選擇排序是不穩(wěn)定的。選擇排序的不穩(wěn)定體現(xiàn)在哪里比如數(shù)組[5, 8, 5, 2, 9]第一輪找到最小值 2和第一個 5 交換這樣原本排在后面的第二個 5 就跑到了第一個 5 的前面相對順序被破壞了。這個區(qū)別在純數(shù)字排序中感受不到但排序?qū)ο笫菐Ц郊有畔⒌慕Y(jié)構(gòu)體時就很重要。6.3 一張表講清三個常見基礎排序為了方便對比我把冒泡、選擇、插入三個基礎排序放在一起排序算法時間復雜度平均穩(wěn)定性交換次數(shù)特點冒泡排序O(n2)穩(wěn)定多每輪可能多次交換思路最直觀適合入門選擇排序O(n2)不穩(wěn)定少每輪最多一次交換交換代價低但不穩(wěn)定插入排序O(n2)穩(wěn)定視數(shù)據(jù)而定接近有序時很少對接近有序的數(shù)據(jù)效率極高通常的建議是工程里這三個都不常用但如果一定要在冒泡和選擇之間選一個用于特定場景我會看兩個因素如果數(shù)據(jù)的“寫入”成本遠高于“讀取”成本我選選擇排序因為它能顯著減少交換次數(shù)如果對穩(wěn)定性有明確要求我選冒泡排序。6.4 初中級面試里冒泡排序被問到的幾種變形面試官問你冒泡排序往往不是讓你背代碼而是讓你寫一個“優(yōu)化的冒泡排序”或者問你“冒泡排序怎么改進”。我自己被問過的問題包括你能讓冒泡排序在輸入已經(jīng)有序的情況下只掃描一趟就停止嗎你能讓內(nèi)層循環(huán)每一輪少比較一些位置嗎如果數(shù)組后半部分已經(jīng)有序怎么跳過它第一個問題的答案是加標志位優(yōu)化。第二個問題的答案是j n-1-i。第三個問題稍微難一點記錄最后一次發(fā)生交換的位置lastSwapIndex因為在這個位置之后的元素都已經(jīng)在正確的位置上下一輪掃描只需要掃到lastSwapIndex即可。這種優(yōu)化代碼比基礎版多一點但耐人尋味值得寫一遍public static void bubbleSortWithLastSwap(int[] arr) { int n arr.length; int lastSwapIndex n - 1; while (lastSwapIndex 0) { int currentLast -1; for (int j 0; j lastSwapIndex; j) { if (arr[j] arr[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; currentLast j; } } lastSwapIndex currentLast; } }這段代碼的可讀性沒有基礎版好但效率在特定數(shù)據(jù)下提升很大。面試時如果你能主動寫出這個版本至少說明你對冒泡排序的理解不是停留在背代碼層面。7. 寫在最后的實操體會冒泡排序是我講給別人最多的一個排序算法倒不是因為它在實際工程中多常用而是因為它包含了一整套學習算法的“基本功”邊界條件的推演、臨時變量的交換、標志位的優(yōu)化、時間復雜度的分析。它就像編程界的“Hello World”雖然簡單但五臟俱全。我在實際教學中發(fā)現(xiàn)最快掌握冒泡排序的方式不是看視頻而是拿筆在紙上畫兩個數(shù)組一個亂序的一個有序的然后手動執(zhí)行每一輪比較和交換把你看到的每一步寫下來。這個過程大概需要十五分鐘但做完之后你再看任何語言的冒泡排序代碼都不會再覺得陌生。最后分享一個小技巧當你面試或考試被要求手寫冒泡排序時寫完基礎版本之后主動補一句“這里可以加一個標志位如果某一趟沒有交換就提前結(jié)束最壞情況還是 O(n2)但最好情況下能降到 O(n)”。這句話一說出來面試官通常就會對你刮目相看因為大多數(shù)人只會默寫代碼而你展現(xiàn)了改進意識。這個算法后續(xù)還可以繼續(xù)擴展的方向是理解它和插入排序的相似與不同進而是希爾排序再到分治思想下的歸并排序和快速排序。冒泡排序是你排序算法地圖的第一塊拼圖拼好它后面的路會平順很多。 冒泡排序從原理到優(yōu)化：相鄰交換、穩(wěn)定排序與時間復雜度解析
1. 冒泡排序到底在干什么冒泡排序真的是排序算法里最貼近直覺的一個我當初學它的時候幾乎沒費什么勁。你想象一個水池水底有一堆大小不一的石頭大的石頭天然沉底小的氣泡往上飄。冒泡排序的每一趟循環(huán)就像一次“讓一個最大的值慢慢浮到正確位置”的過程所以這個算法的名字起得非常形象。它解決的問題很簡單給我一組亂序的數(shù)字我通過反復比較相鄰的兩個元素如果順序不對就交換它們的位置最終讓整個序列排列整齊。這個“反復比較相鄰元素并交換”的動作就是冒泡排序的全部核心沒有復雜的遞歸沒有精巧的分治就是老老實實地一遍遍掃過去。我剛接觸編程的時候?qū)W的第一個排序算法就是它。那時候不理解時間復雜度也不關心什么是穩(wěn)定排序我就是把代碼敲了一遍然后指著打印出來的結(jié)果說“哦原來排序是這么回事”。所以如果你剛?cè)腴T編程拿冒泡排序當作理解“算法到底是什么”的第一個例子是很合適的。這個算法適合誰來學我覺得有三類人第一類是剛接觸數(shù)據(jù)結(jié)構(gòu)和算法的大學生需要一個不那么嚇人的入門案例第二類是準備面試的開發(fā)者雖然冒泡排序在工程里基本不會用但面試官偶爾會拿它考基本功尤其是它的優(yōu)化寫法第三類是自學編程的朋友你可能沒有系統(tǒng)的算法課想通過一個簡單的例子建立對代碼執(zhí)行流程的直覺。這篇文章我會從思路、代碼、實操、踩坑四個維度把它講透最后還會拿它和選擇排序做個對比幫你看清楚為什么它簡單但確實不是效率最優(yōu)的選擇。2. 設計思路拆解三個關鍵問題想明白代碼自然就寫出來了2.1 為什么是“相鄰比較”而不是“隨便挑兩個比”冒泡排序最核心的動作是每一輪循環(huán)里依次比較相鄰的兩個元素也就是第0個和第1個、第1個和第2個這樣一路比到最后一個。如果左邊的數(shù)大于右邊的數(shù)就交換它們的位置。為什么非要相鄰比較這里面其實藏著一個很重要的設計邏輯每一次交換都讓一個較大的值向序列末尾方向移動一位經(jīng)過一整趟的比較就能確定一個“本輪最大的值”被推到了它最終應該在的位置。這種“一趟確定一個最終位置”的特性讓整個排序過程天然是收斂的。你不需要額外記錄什么極值下標也不需要額外的數(shù)據(jù)結(jié)構(gòu)幫你存儲中間狀態(tài)就靠相鄰交換信息自然傳遞。如果你跳著比較比如把第0個元素和第3個元素比較那確實也能找出來最大值但中間那幾個元素的狀態(tài)完全沒被整理你需要額外寫很多邏輯才能保證整個序列有序。所以說相鄰比較正好是“信息傳遞最直接、代碼最簡單”的方式這也是冒泡排序設計上的巧思。2.2 為什么需要多輪循環(huán)每輪掃描的范圍為什么越來越小光一趟掃描肯定不夠。第一趟掃描結(jié)束你只能保證最大值到了最后前面還有一堆亂序的數(shù)字。所以需要再來一趟把第二大的值推到倒數(shù)第二的位置再第三趟推出第三大的值……總共需要 n-1 趟n 是元素個數(shù)。這里有一個特別容易忽略的細節(jié)每一趟掃描的范圍在縮小。第一趟掃描到最后一個位置第二趟其實只需要掃描到倒數(shù)第二個位置因為最后一個位置已經(jīng)是最大值再去比較它純屬浪費。這個“每趟少比較一個位置”的優(yōu)化是初學冒泡排序時最容易忘記的。很多教科書代碼里會這么寫for (int i 0; i n-1; i) { for (int j 0; j n-1-i; j) { // 比較并交換 } }注意內(nèi)層循環(huán)的條件是n-1-i不是n-1。這就是在每一輪掃描中自動把已經(jīng)排好的尾部區(qū)域排除掉。我見過不少人把這個-i丟了程序其實也能跑出正確結(jié)果因為多比較的只是已經(jīng)排好序的元素不會產(chǎn)生錯誤但效率確實低了一截。這種丟寫法只能說“僥幸正確”不嚴謹。2.3 穩(wěn)定排序是什么意思冒泡為什么天生是穩(wěn)定的冒泡排序是穩(wěn)定排序。所謂穩(wěn)定就是如果兩個元素的值相同它們在排序完成后的相對順序不會改變。比如有兩個同為 5 的數(shù)字一開始前面的那個 5排完序之后依然在前面。冒泡排序為什么天然穩(wěn)定因為它的交換條件寫的是“如果左邊的大于右邊才交換”注意是嚴格大于不是大于等于。如果兩個元素相等條件不成立就不會交換所以相同值的相對順序被保住了。這一點在大部分普通場景下沒什么感覺但當你排序的是對象比如員工對象按工資排序而工資相同的員工希望保持原來的入職順序那穩(wěn)定排序就很有意義。我以前寫一個報表工具時需要在兩輪排序的基礎上保持前一輪的排序痕跡穩(wěn)定排序就成了唯一合理的選擇。所以不要覺得穩(wěn)定性只是一個概念題實際工程里是真的會用到的。3. 核心細節(jié)實操用代碼把冒泡排序?qū)懗鰜聿⒗斫饷恳恍械暮x3.1 C語言版本最接近底層的寫法幫你建立內(nèi)存視角C語言的實現(xiàn)最直觀因為它讓你直面數(shù)組操作和交換邏輯。先看一個最基礎版本#include stdio.h void bubbleSort(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[j1]) { // 交換兩個數(shù) int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; } } } } int main() { int arr[] {5, 1, 4, 2, 8}; int n sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } return 0; }這里的sizeof(arr) / sizeof(arr[0])是C語言里計算數(shù)組長度最常用的方式sizeof(arr)是整個數(shù)組占用的總字節(jié)數(shù)除以單個元素的字節(jié)數(shù)就得到元素個數(shù)。記住這個寫法面試和筆試經(jīng)常用。交換邏輯用了臨時變量temp這是最樸素的交換思想。兩個杯子要互換液體必須先有一個空杯子。這個類比幫我理解了很多年的交換操作。3.2 Java版本更符合工程習慣的寫法Java里的寫法在思路上完全一致只是語法有些區(qū)別。Java傳入數(shù)組本身就是引用傳遞所以在方法內(nèi)直接修改數(shù)組外面的變量也會隨之改變這一點和C語言通過指針傳入是異曲同工的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[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] 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版本需要注意的細節(jié)是arr.length是一個屬性不是方法所以別寫arr.length()。初學Java從C語言轉(zhuǎn)過來的人經(jīng)常在這個地方犯迷糊C語言是sizeof(arr)/sizeof(arr[0])Java直接.length兩個語言的風格差異就在這里體現(xiàn)出來了。3.3 Python版本最簡潔的表達適合快速驗證思路Python的寫法可以把冒泡排序壓縮到幾乎不能再短def bubble_sort(arr): n len(arr) for i in range(n-1): for j in range(n-1-i): if arr[j] arr[j1]: arr[j], arr[j1] arr[j1], arr[j] return arr if __name__ __main__: test [5, 1, 4, 2, 8] print(bubble_sort(test))Python的arr[j], arr[j1] arr[j1], arr[j]這種并行賦值寫法底層其實是一口氣完成了取值和賦值不需要臨時變量。這個語法糖寫起來很爽但要注意右邊是“先算完再統(tǒng)一賦值”理解了這個你就不會擔心順序錯亂的問題。Python版最適合什么場景當你腦子里有了一個算法的模糊想法想快速驗證一下對不對用Python最合適寫起來省時間能讓你把注意力集中在邏輯上而不是語言細節(jié)上。3.4 最關鍵的那行代碼為什么是j n-1-i少個-i行不行這一小節(jié)我要重點講因為它是冒泡排序無數(shù)初學者最容易栽跟頭的地方。外層循環(huán)控制的是“一共要跑幾趟”n 個元素最多需要 n-1 趟。為什么是 n-1因為當 n-1 個元素已經(jīng)跑到正確位置之后剩下的那一個元素自然就在正確位置了不需要再處理。這是排序算法的通用邏輯。內(nèi)層循環(huán)控制的是“這一趟比較哪些位置”。第一趟j 從 0 掃到 n-2也就是說比較第0和第1個、第1和第2個、……、第n-2和第n-1個覆蓋整個數(shù)組。每比較一次如果左邊大于右邊就交換一趟結(jié)束最大的值到了最后。第二趟開始就不同了。最后一個位置已經(jīng)是最大值我再去比較第 n-2 和第 n-1 個是毫無意義的比較。所以第二趟只需要掃到 n-2 即止也就是j n-2。第三趟需要掃到 n-3以此類推。用i表示當前是第幾趟那這一趟的掃描上限就是n-1-i。如果你寫成j n-1代碼依然能正確排序因為多比較的那些部分不會產(chǎn)生錯誤交換只是白白消耗了CPU時間。對于算法學習來說這是不合格的因為算法的意義之一就是效率而效率就藏在這些細節(jié)里。4. 實操過程還原從一個亂序數(shù)組開始手動走一遍排序過程4.1 用例子走完整流程我拿[5, 1, 4, 2, 8]這個數(shù)組來手動模擬一遍冒泡排序的每一輪狀態(tài)這是理解冒泡排序最快的辦法。強烈建議你也用紙筆畫一遍只看代碼是形成不了直覺的。第一趟i0j 從 0 掃到 3比較 j05 和 151交換數(shù)組變成[1, 5, 4, 2, 8]比較 j15 和 454交換數(shù)組變成[1, 4, 5, 2, 8]比較 j25 和 252交換數(shù)組變成[1, 4, 2, 5, 8]比較 j35 和 858不交換數(shù)組保持[1, 4, 2, 5, 8]第一趟結(jié)束8 這個最大的數(shù)已經(jīng)浮到了最后它的位置確定了。第二趟i1j 從 0 掃到 2比較 j01 和 414不交換比較 j14 和 242交換數(shù)組變成[1, 2, 4, 5, 8]比較 j24 和 545不交換第二趟結(jié)束5 的位置確定了。第三趟i2j 從 0 掃到 1比較 j01 和 212不交換比較 j12 和 424不交換第三趟結(jié)束沒有發(fā)生任何交換。第四趟i3j 從 0 掃到 0比較 j01 和 212不交換全部結(jié)束數(shù)組已經(jīng)有序。注意一個細節(jié)第三趟結(jié)束的時候?qū)嶋H上就已經(jīng)完全有序了但冒泡排序不知道它還會繼續(xù)跑第四趟。這就是為什么它需要額外的優(yōu)化手段來處理這些無用的趟數(shù)這部分在后面的常見問題章節(jié)我會詳細講。4.2 手動走一遍之后觀察到了什么規(guī)律手動模擬完有三個規(guī)律是我希望你能自己體會到的第一每一趟都能確定一個最大值到它最終的位置這個位置是從后往前依次確定的。所以外層循環(huán)跑完 n-1 趟之后所有位置都確定了。第二數(shù)組如果本來接近有序冒泡排序也不會自動“感知”到這一點它依然傻傻跑完全部趟數(shù)除非你加了優(yōu)化。這也是它和插入排序的一個重要區(qū)別插入排序在接近有序的數(shù)據(jù)上表現(xiàn)非常好冒泡排序在沒有優(yōu)化的情況下不行。第三交換操作發(fā)生的位置和次數(shù)是沒有規(guī)律的。有時候這趟交換了很多次有時候一次都沒有。所以判斷一個數(shù)組是否提前完成排序就看某一趟有沒有發(fā)生任何交換這也是“哨兵優(yōu)化”的思想基礎。4.3 用表格看每一輪的變化我把上面的過程整理成表格方便你對照。趟數(shù)掃描范圍比較過程是否有交換本輪結(jié)束后的數(shù)組第1趟j0~35和1交換5和4交換5和2交換5和8不換是[1, 4, 2, 5, 8]第2趟j0~21和4不換4和2交換4和5不換是[1, 2, 4, 5, 8]第3趟j0~11和2不換2和4不換否[1, 2, 4, 5, 8]第4趟j0~01和2不換否[1, 2, 4, 5, 8]這個表格建議你親手畫一遍。我見過很多學生代碼寫得很溜但問他[3,1,2]排序過程中第二趟長什么樣他就答不上來。這類問題面試經(jīng)常考畫圖能力代表了你對算法的真實理解程度。5. 常見問題與踩坑復盤運行結(jié)果不對先想想這4個地方5.1 問題一為什么我的輸出沒有變化數(shù)組好像完全沒被排序出現(xiàn)這種情況最典型的錯誤是交換邏輯沒生效。我見過有人把交換寫成這樣arr[j] arr[j1]; arr[j1] arr[j];很明顯第一步執(zhí)行之后arr[j]已經(jīng)被覆蓋了第二步賦值等于把同一個值寫了兩遍數(shù)組自然沒變化。正確寫法必須借助臨時變量或者用像Python那樣的一次性賦值。這種問題在C和Java里很常見因為它們的賦值是“先算右邊再把結(jié)果覆蓋左邊”不會自動保留原值。另一個可能原因是你傳參的方式不對。C語言里如果你傳的是數(shù)組的副本而不是指針函數(shù)內(nèi)部修改就不會影響到外部數(shù)組。Java里數(shù)組是引用傳遞基本不會踩這個坑。C里如果你寫函數(shù)時形參用了vectorint而不是vectorint也會發(fā)生拷貝排序只作用于副本。5.2 問題二循環(huán)邊界條件到底怎么記每次寫都要翻書邊界條件這塊我提供一個記憶口訣外層循環(huán)i從 0 到 n-2內(nèi)層循環(huán)j從 0 到 n-i-2那么比較的下標就是arr[j]和arr[j1]。這個口訣等價于上面的代碼但更好記因為 j 的最大值是 n-i-2所以 j1 的最大值是 n-i-1也就是當前趟數(shù)需要處理的最后一個元素位置。如果你不放心可以隨手代入數(shù)字驗證n5i0 時j 最大是3比較的是arr[3]和arr[4]覆蓋了所有元素。i3 時j 最大是0比較的是arr[0]和arr[1]只比較最前面的一對。這樣算下來邏輯就通順了。5.3 問題三我加了優(yōu)化為什么反而排錯序了很多人在理解了冒泡排序之后會想著加一個“提前結(jié)束”的優(yōu)化如果某一趟沒有發(fā)生任何交換就說明數(shù)組已經(jīng)有序直接退出循環(huán)。這個思路是對的但實現(xiàn)的時候容易出錯。常見的錯誤寫法是這樣的for (int i 0; i n-1; i) { int flag 0; for (int j 0; j n-1-i; j) { if (arr[j] arr[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; flag 1; } } // 下面的寫法是錯誤的 // if (flag) break; }注意flag 1表示發(fā)生了交換那么“沒有發(fā)生交換”應該是flag 0退出條件應該是if (!flag) break;。如果你寫成if (flag) break;那就變成“只要有交換就退出”只跑一趟就結(jié)束了排序結(jié)果當然不對。這個坑我當年也踩過本質(zhì)上是把標志位的語義搞反了。寫優(yōu)化代碼時建議先把“這個變量到底表示什么”想清楚再寫判斷條件。我這里貼一個正確的優(yōu)化版本void bubbleSortOptimized(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[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; swapped 1; } } if (swapped 0) { break; } } }5.4 問題四數(shù)據(jù)量一大就慢得離譜是不是我寫錯了不是寫錯了是冒泡排序本身確實慢。它的時間復雜度是 O(n2)什么意思如果數(shù)組有 1000 個元素內(nèi)外兩層循環(huán)大概要執(zhí)行百萬次比較操作如果數(shù)組有 10000 個元素就要上億次比較。這個增長速度是平方級別的數(shù)據(jù)量翻一倍耗時大約翻四倍。所以工程上沒人用冒泡排序處理大規(guī)模數(shù)據(jù)這是正常的。如果你只是寫完代碼做測試建議用幾百個元素的數(shù)組感受一下邏輯不要去排 10 萬個數(shù)。真要對大數(shù)組排序用 C 標準庫的qsortJava 的Arrays.sort()或者 C 的std::sort這些底層都是快排、歸并這類 O(n log n) 的算法性能差距是數(shù)量級的。6. 選擇排序和冒泡排序?qū)Ρ日l更好什么時候用哪個6.1 選擇排序的思路回顧選擇排序和冒泡排序經(jīng)常被放在一起比較因為它們的實現(xiàn)難度差不多思路也都是在每一輪中確定一個元素的最終位置。區(qū)別在于選擇排序不再是相鄰元素交換而是每一輪在剩余未排序部分里找出最小值或最大值記錄它的下標等這一輪掃描結(jié)束后再把它和當前輪次的起始位置交換。舉個例子[5, 1, 4, 2, 8]第一輪掃描全部元素找到最小值 1 在下標1的位置然后讓下標0的位置和下標1的位置交換得到[1, 5, 4, 2, 8]。第二輪掃描下標1到4的部分找到最小值 2交換到下標1得到[1, 2, 4, 5, 8]。以此類推。6.2 冒泡和選擇的核心差異兩者在時間復雜度上是一樣的都是 O(n2)。但在實際行為上差別很大冒泡排序每一輪可能需要很多次交換而選擇排序每一輪最多只交換一次。所以雖然比較次數(shù)差不多但選擇排序的“數(shù)據(jù)搬動”次數(shù)遠小于冒泡排序在交換代價較高的場景里選擇排序更優(yōu)一些。再看穩(wěn)定性冒泡排序是穩(wěn)定的選擇排序是不穩(wěn)定的。選擇排序的不穩(wěn)定體現(xiàn)在哪里比如數(shù)組[5, 8, 5, 2, 9]第一輪找到最小值 2和第一個 5 交換這樣原本排在后面的第二個 5 就跑到了第一個 5 的前面相對順序被破壞了。這個區(qū)別在純數(shù)字排序中感受不到但排序?qū)ο笫菐Ц郊有畔⒌慕Y(jié)構(gòu)體時就很重要。6.3 一張表講清三個常見基礎排序為了方便對比我把冒泡、選擇、插入三個基礎排序放在一起排序算法時間復雜度平均穩(wěn)定性交換次數(shù)特點冒泡排序O(n2)穩(wěn)定多每輪可能多次交換思路最直觀適合入門選擇排序O(n2)不穩(wěn)定少每輪最多一次交換交換代價低但不穩(wěn)定插入排序O(n2)穩(wěn)定視數(shù)據(jù)而定接近有序時很少對接近有序的數(shù)據(jù)效率極高通常的建議是工程里這三個都不常用但如果一定要在冒泡和選擇之間選一個用于特定場景我會看兩個因素如果數(shù)據(jù)的“寫入”成本遠高于“讀取”成本我選選擇排序因為它能顯著減少交換次數(shù)如果對穩(wěn)定性有明確要求我選冒泡排序。6.4 初中級面試里冒泡排序被問到的幾種變形面試官問你冒泡排序往往不是讓你背代碼而是讓你寫一個“優(yōu)化的冒泡排序”或者問你“冒泡排序怎么改進”。我自己被問過的問題包括你能讓冒泡排序在輸入已經(jīng)有序的情況下只掃描一趟就停止嗎你能讓內(nèi)層循環(huán)每一輪少比較一些位置嗎如果數(shù)組后半部分已經(jīng)有序怎么跳過它第一個問題的答案是加標志位優(yōu)化。第二個問題的答案是j n-1-i。第三個問題稍微難一點記錄最后一次發(fā)生交換的位置lastSwapIndex因為在這個位置之后的元素都已經(jīng)在正確的位置上下一輪掃描只需要掃到lastSwapIndex即可。這種優(yōu)化代碼比基礎版多一點但耐人尋味值得寫一遍public static void bubbleSortWithLastSwap(int[] arr) { int n arr.length; int lastSwapIndex n - 1; while (lastSwapIndex 0) { int currentLast -1; for (int j 0; j lastSwapIndex; j) { if (arr[j] arr[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; currentLast j; } } lastSwapIndex currentLast; } }這段代碼的可讀性沒有基礎版好但效率在特定數(shù)據(jù)下提升很大。面試時如果你能主動寫出這個版本至少說明你對冒泡排序的理解不是停留在背代碼層面。7. 寫在最后的實操體會冒泡排序是我講給別人最多的一個排序算法倒不是因為它在實際工程中多常用而是因為它包含了一整套學習算法的“基本功”邊界條件的推演、臨時變量的交換、標志位的優(yōu)化、時間復雜度的分析。它就像編程界的“Hello World”雖然簡單但五臟俱全。我在實際教學中發(fā)現(xiàn)最快掌握冒泡排序的方式不是看視頻而是拿筆在紙上畫兩個數(shù)組一個亂序的一個有序的然后手動執(zhí)行每一輪比較和交換把你看到的每一步寫下來。這個過程大概需要十五分鐘但做完之后你再看任何語言的冒泡排序代碼都不會再覺得陌生。最后分享一個小技巧當你面試或考試被要求手寫冒泡排序時寫完基礎版本之后主動補一句“這里可以加一個標志位如果某一趟沒有交換就提前結(jié)束最壞情況還是 O(n2)但最好情況下能降到 O(n)”。這句話一說出來面試官通常就會對你刮目相看因為大多數(shù)人只會默寫代碼而你展現(xiàn)了改進意識。這個算法后續(xù)還可以繼續(xù)擴展的方向是理解它和插入排序的相似與不同進而是希爾排序再到分治思想下的歸并排序和快速排序。冒泡排序是你排序算法地圖的第一塊拼圖拼好它后面的路會平順很多。