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