、復雜度與避坑指南)
直接插入排序、冒泡排序、快速排序、選擇排序這四兄弟幾乎出現(xiàn)在每一本算法教材的目錄前幾頁也幾乎出現(xiàn)在每一次筆試的白紙上方。說實話我?guī)蛨F隊做基礎算法梳理的時候最常被問倒的不是紅黑樹也不是動態(tài)規(guī)劃恰恰是這些“以為閉著眼都能寫”的排序。這篇文章不打算抄書我就用一次完整實現(xiàn)的過程把這四種排序的代碼、復雜度、適用場景和我自己踩過的坑一次性講透。適合正在準備筆試面試的朋友也適合剛學數(shù)據(jù)結構、想把排序真正寫對而不是“背對”的人。讀完之后你至少能收獲三樣東西隨時能正確手寫四種排序的底氣和邊界意識一張可以對著看的數(shù)據(jù)速查表還有一份我自己用過的排序代碼自測清單。1. 四種排序為什么總是它們四個一起出現(xiàn)很多初學者會困惑排序算法有歸并、堆排、基數(shù)、桶排為什么教材偏偏把插入、冒泡、快排、選擇這四種放在同一章原因不是它們性能最好而是它們四個人恰好代表了基礎算法設計的幾種最典型思路。插入排序代表的是“增量式構建”假設左邊已經(jīng)有序往里面插入新元素。冒泡排序代表的是“相鄰交換驅動”通過不斷交換相鄰逆序對讓序列慢慢變好。快速排序代表的是“分治切割”選一個基準把問題拆成兩個獨立子問題遞歸解決。選擇排序代表的是“貪心式掃描”每次都從剩余元素里挑出最值放到目標位置。這四種思路一旦吃透后面學歸并、堆排、希爾、桶排序你會覺得很順因為本質都是在這些母題上加優(yōu)化。它們還共同構成了一個很好的復雜度對照樣本為什么有的排序 O(n2)有的能做到 O(n log n)為什么穩(wěn)定性和原地性又不能同時得到這些概念都可以拿它們當引子。1.1 外行怎么理解這四件事我先給個生活化的錨點后面代碼才不會跑偏。插入排序就像打撲克時理牌摸到一張新牌從右往左比找到位置插進去。冒泡排序就像一杯水里的小氣泡大的元素不斷往上或往右浮?？炫啪拖癜嗉壟抨犗入S便拉一個人當基準矮的站左邊高的站右邊兩邊各自再重復這個過程。選擇排序最像商品比價每輪掃一遍把當前最便宜的挑出來放到購物車第一個位置接著掃剩下的。這四個比喻能幫你記住“每輪在做什么”。但代碼實現(xiàn)里的坑光靠比喻可躲不過去下面逐個展開。1.2 一張表看清四種排序的基本盤在寫代碼之前先把結論擺出來。這里說的“穩(wěn)定”指元素值相等時排序后相對順序是否保持原樣。額外空間指除了原始數(shù)組外額外占用的內存規(guī)模。排序算法平均時間復雜度最壞時間復雜度最好時間復雜度額外空間原地排序穩(wěn)定插入排序O(n2)O(n2)O(n)O(1)是穩(wěn)定冒泡排序O(n2)O(n2)O(n)加提前終止O(1)是穩(wěn)定快速排序O(n log n)O(n2)O(n log n)O(log n) 遞歸棧是不穩(wěn)定選擇排序O(n2)O(n2)O(n2)O(1)是不穩(wěn)定這張表我建議你親手建一次而不是直接背。因為你會在建表過程中意識到很多細節(jié)為什么插入排序最好能達到 O(n)為什么快排的平均復雜度能那么低為什么選擇排序怎么優(yōu)化都是 O(n2)。這些問題的答案恰恰藏在實現(xiàn)細節(jié)里。2. 直接插入排序把“整理手牌”的動作寫成代碼直接插入排序可以說是最好理解的一個。每輪開始前數(shù)組左邊一小段已經(jīng)有序我只需要把當前這個元素往左送送到它該在的位置。整個過程沒有任何“全局規(guī)劃”就是局部調整。先看我最終采用的實現(xiàn)def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr就這么幾行但里面的每一處邊界都值得掰開講。2.1 從摸牌動作推導循環(huán)結構模擬一下手里已經(jīng)有 arr[0..i-1]這 i 個元素是排好序的?，F(xiàn)在摸到 arr[i]也就是代碼里的 key。我把它和前面依次比較如果前面的數(shù)更大就往后挪一格給新牌騰位置如果前面某個數(shù)已經(jīng)比 key 小或相等說明位置找到了把 key 放進去。這里的循環(huán)不變量是每一輪外層循環(huán)結束時arr[0..i] 都是有序的。所以一開始 i 從 1 開始而不是 0因為單個元素天然有序不需要插入。很多初學者把 i 寫成從 0 開始結果第一輪就把自己搞糊涂了。代碼里的 while 循環(huán)在把大元素往右搬移。arr[j 1] arr[j] 不是交換而是覆蓋式右移。這個動作很像撲克牌整理時把大牌往右邊推騰出空位。最后 arr[j 1] key把新牌放回空位。2.2 為什么用“移動”而不是“交換”插入排序的內部動作是移動不是交換。這一點很多實現(xiàn)寫錯。用交換也可以完成排序但會把簡單問題復雜化每交換一次就要做三次賦值而且還會多做很多無意義的數(shù)組寫操作。移動則是從右到左一次性搬移最后再寫一次新值。還有一個穩(wěn)定性細節(jié)while 的條件是 arr[j] key不是 。如果是大于等于相等元素也會被從右邊搬過去相等值的相對順序就被破壞了。只要堅持“只有嚴格大于才搬運”插入排序就是穩(wěn)定的。這個等于號的選擇是所有排序實現(xiàn)里最容易忽略的穩(wěn)定性開關。還有一個隱藏邊界j 可能一路減到 -1。如果 key 是整個數(shù)組里最小的while 會一直執(zhí)行到 j -1 退出最后 arr[0] key正好把最小的數(shù)放到開頭。所以 arr[j 1] 這里的下標不是錯誤是刻意讓它落到 arr[0]。2.3 插入排序的隱藏優(yōu)勢近乎有序時就該它上場插入排序最被人低估的點是對“幾乎有序”的數(shù)據(jù)極度友好。如果輸入已經(jīng)是升序for 循環(huán)里的 while 一次都不會進整個排序變成一趟線性掃描時間 O(n)。這一點在表格里看起來不明顯但實際工程里非常重要。很多高性能排序算法比如 TimSort在局部小規(guī)模或接近有序的分塊里底層用的就是插入排序。原因有兩個一是插入排序常數(shù)極小不需要額外空間二是它對“部分有序”數(shù)據(jù)利用率極高。我自己寫小工具時如果數(shù)據(jù)量小于 16 并且確定基本有序干脆直接插入排序比什么花哨算法都穩(wěn)。2.4 寫插入排序最常見的兩個翻車點第一忘記保存 key。我見過不少版本先寫 arr[i 1] arr[j]結果 arr[i] 被覆蓋后續(xù)循環(huán)全亂。必須先key arr[i]心里要清楚這個值就是“新摸的牌”后面所有比較和挪動都圍繞它。第二內層循環(huán)方向寫反。如果從左往右掃描找位置那騰位置時會覆蓋還沒比較的元素邏輯非常繞。記住插入排序是“從右往左倒著比”這和手理撲克牌的習慣一致。3. 冒泡排序最“笨”的排序藏著兩個容易忽略的優(yōu)化點冒泡排序在工程里基本沒有存在感但在教學里地位很高因為它把“有序性如何通過相鄰交換逐步建立”這件事展示得最清楚?；A實現(xiàn)長這樣def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr很多人背代碼時直接把里面兩個循環(huán)套上就完事完全沒看懂 swapped 和內層 j 范圍為什么這樣寫。我分別說。3.1 外層循環(huán)控制“趟數(shù)”內層循環(huán)制造“上浮”冒泡每一趟都會從數(shù)組最左邊開始兩兩比較相鄰元素如果順序反了就交換。因為大的元素每比較一次就往右挪一步經(jīng)過一整趟之后當前最大值一定被推到了數(shù)組末尾。所以下一趟就不用再看最后那個位置內層 j 范圍收縮成n - 1 - i。外層循環(huán)只需要 n - 1 趟。為什么不是 n 趟因為最后剩下一個元素時它已經(jīng)是唯一的位置不需要再比。這和插入排序外層從 1 開始有異曲同工的味道排序終止條件總比 n 少一點。3.2 提前終止讓“最好情況”從 O(n2) 變成 O(n)如果不加 swapped就算數(shù)組已經(jīng)天然升序冒泡排序也會把所有相鄰元素比較一遍照常跑完 n - 1 趟白費時間。加了 swapped 標記之后只要某一趟從頭到尾沒有任何交換說明數(shù)組已經(jīng)有序直接 break。這個優(yōu)化不改變平均復雜度但讓冒泡的最好情況變成 O(n)。千萬別以為這只是可有可無的小技巧在面試里問“冒泡排序最好情況是多少”時很多人答 O(n2)就是因為沒意識到這個標記的存在。從實現(xiàn)角度它同時也暴露了冒泡排序的一個核心特征它的比較次數(shù)并不固定和輸入有序度強相關。3.3 冒泡排序為什么名聲差但還沒被教材刪掉冒泡被罵核心原因是它做了太多無效工作。一趟只能把一個最大值送到最終位置如果數(shù)組中有一個小元素在最后面它就不得不一趟一趟地往左挪像個“慢?！薄?shù)據(jù)量稍微一大比如 10 萬條隨機整數(shù)冒泡的耗時就會膨脹到讓人難以接受比插入排序還要慢上不少因為交換涉及三次賦值而插入排序大部分時候只需要搬移。但它沒被教材刪是因為它太適合入門了。雙重循環(huán)、相鄰交換、穩(wěn)定性、提前終止、邊界控制這些概念都可以在一個簡單代碼里展示。作為實現(xiàn)練習冒泡是很好的“腳手架”。你甚至可以基于它引出一個經(jīng)典問題為什么相鄰交換排序很難突破 O(n2)這與“逆序對”數(shù)量相關每交換一次才消除一個逆序對這為后面學習更快的排序埋下伏筆。3.4 手寫冒泡最容易犯的三個錯一是內層循環(huán)寫成for j in range(n - i)這時 j 會取到n - i - 1跟 j 1 比較時越界。記住范圍是n - 1 - i留出右側的“已排好區(qū)域”。二是忘記在循環(huán)末尾判斷 swapped導致排序結果沒錯但最好情況優(yōu)化失效。三是把兩個循環(huán)方向搞反外層跑內層、內層跑外層排序結果一團亂。其實寫完冒泡之后我建議你做個小實驗把 swapped 去掉再跑一次對比一下輸入是有序數(shù)組時的執(zhí)行時間你就理解這個標記到底省了什么。4. 快速排序思路三句話代碼卻處處是細節(jié)到了快排代碼量一下子變多但核心思路仍然是三句話選一個基準值把比它小的放左邊、比它大的放右邊然后對左右兩個部分遞歸做同樣的事。我用比較常見的 Lomuto 分區(qū)方式來寫from random import randint def quick_sort(arr, low, high): if low high: p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) def partition(arr, low, high): pivot_index randint(low, high) arr[pivot_index], arr[high] arr[high], arr[pivot_index] pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1調用方式是quick_sort(arr, 0, len(arr) - 1)。這里我特意加入了隨機選基準原因后面細說。4.1 partition 到底在做什么Lomuto 分區(qū)的思路很直接取最后一個元素當基準 pivot然后讓 i 指向“當前已發(fā)現(xiàn)的小于等于 pivot 的區(qū)間右邊界”。一開始 i low - 1表示這個區(qū)間為空。然后 j 從頭掃到 high - 1每當發(fā)現(xiàn) arr[j] 小于等于 pivot就把 i 右移一位并把 arr[j] 交換過去。你可以把 i 想象成“分界線”左邊是已經(jīng)歸位的小值隊列右邊是等待掃描的大值隊列。掃描結束后arr[i 1] 這個位置就是基準值應該待的位置把基準交換過來返回 i 1 作為分界點。注意這里用的是而不是。用會把等于基準的值留在右側雖然排序結果還是對的但分區(qū)會偏向不均衡而且等于基準的元素來回跑整體性能下降。用意味著相等元素也歸到左區(qū)分區(qū)更穩(wěn)。4.2 三個最容易寫錯的地方第一遞歸范圍必須是p - 1和p 1不能把 p 包含進去。因為 p 位置上的元素已經(jīng)最終歸位再遞歸它會造成死循環(huán)或無效重復。道理很簡單但手寫時緊張?zhí)貏e容易漏掉 1 和 -1。第二partition 返回的是基準值的最終下標這個下標是遞歸分界。如果返回錯誤比如返回 i 而不是 i 1整個排序就會立刻亂套。建議自己在紙上跑一個長度為 5 的小數(shù)組親眼看看基準最終落在哪里。第三當數(shù)組里全是相等元素時Lomuto 分區(qū)可能退化成 O(n2)因為每次分區(qū)都極不均衡。這個情況很隱蔽普通隨機測試測不出來。工程上解決它的主流方案是三路快速排序把數(shù)組切分成“小于基準”“等于基準”“大于基準”三段中間段不再參與遞歸。面試時能提到這一點通常是個加分項。4.3 為什么快排不穩(wěn)定工業(yè)界還在大面積使用快排的不穩(wěn)定主要體現(xiàn)在分區(qū)交換時相等元素可能被交換到另一側相對順序無法保證。既然不穩(wěn)定為什么標準庫還在大量用快排因為對于基本類型數(shù)據(jù)穩(wěn)定性沒有實際意義。Java 的Arrays.sort對基本類型數(shù)組用的就是雙基準快排C 的qsort也是快排變體。基本類型拿不出“原始相對順序”這種概念排序后誰在哪都無所謂而對象排序通常需要穩(wěn)定性Java 對對象用的就是 TimSort/歸并排序。所以選型要看數(shù)據(jù)類型而不是一句“快排最好”通吃。快排核心優(yōu)勢是原地排序、緩存友好、平均常數(shù)小。同等數(shù)據(jù)量下它能吞吐掉大量元素訪問和交換實際速度比很多“理論更優(yōu)”的算法更猛。這也是為什么平均復雜度同為 O(n log n)工程上更偏愛快排而不是歸并的常見原因。4.4 隨機化基準一次必要的防守如果每次固定取最后一個元素作為基準面對已經(jīng)有序的數(shù)組每次分區(qū)都會得到一邊空、一邊 n-1 的極端情況遞歸深度逼近 n復雜度退化成 O(n2)甚至可能因為遞歸過深爆棧。隨機化基準的核心目的是避免這種系統(tǒng)性的壞運氣讓“最壞情況”變成概率極低的事件。有些人覺得隨機化沒必要覺得“我數(shù)據(jù)沒那么壞”。但真實場景里數(shù)據(jù)來源誰也說不準。你拿到的可能就是按某種規(guī)則排好的或高度規(guī)律的數(shù)據(jù)固定基準就是定時炸彈。我建議平時練習就養(yǎng)成隨機化的習慣面試手寫時如果允許也可以說“這里再隨機選一個 pivot 防止退化”。5. 選擇排序看起來最直觀實現(xiàn)時別踩穩(wěn)定性的坑選擇排序的思路比快排簡單得多第一輪掃全數(shù)組找最小元素和 arr[0] 交換第二輪從 arr[1] 開始找最小和 arr[1] 交換依此類推。每次確定一個位置的最終值。實現(xiàn)如下def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr這代碼本身不難但背后的兩個問題值得展開它交換次數(shù)少卻不穩(wěn)定。5.1 “每次選最小”的代碼究竟在循環(huán)什么外層循環(huán) i 表示當前位置內層循環(huán)從 i 1 掃到末尾找出最小元素的索引 min_idx。內層只記錄下標不急著交換等整輪掃完再交換這樣就確保了每輪最多一次交換。min_idx初始化為 i 是必要的。如果后面所有元素都比 arr[i] 大min_idx 就保持為 i交換操作可以跳過。有些實現(xiàn)不檢查 min_idx ! i每次都交換雖然結果沒錯但多出不少無意義寫操作。養(yǎng)成檢查的習慣寫出來的排序更干凈。5.2 交換次數(shù)低卻在有些場景下有奇用選擇排序的比較次數(shù)永遠是 n(n-1)/2不管數(shù)據(jù)是否有序所以它沒有任何“最好情況”優(yōu)勢。但它的交換次數(shù)最多只有 n - 1這在“寫操作代價遠高于讀操作”的場景里是實打實的優(yōu)勢。比如某些存儲設備寫入壽命有限或者元素本身是一個很大的對象每次交換都要復制大量字段。這時候選擇排序的“少寫”特性比插入、冒泡都好。當然這是一種偏門場景日常排序基本用不上但理解它你會明白復雜度不是算法選擇的唯一維度。5.3 選擇排序為什么不穩(wěn)定說一個最容易理解的例子數(shù)組是 [5a, 5b, 2]其中兩個 5 我們用 a、b 做標記區(qū)分。第一輪掃描找到最小值 2把它和 arr[0] 也就是 5a 交換數(shù)組變成 [2, 5b, 5a]。你看原本 5a 在 5b 前面排序后 5b 跑到前面去了相對順序被破壞。有人會說“那我掃描的時候只有嚴格小于才更新 min_idx不碰相等元素不就行了嗎”但問題不在這里。問題是交換動作本身就是跳躍式的可能跨越多個相等元素。要恢復穩(wěn)定性需要額外策略比如從右往左掃、把相等元素盡量留到左側但那已經(jīng)不像標準選擇排序了。所以默認你寫的、教材上的選擇排序就當它不穩(wěn)定面試時這樣說最穩(wěn)妥。5.4 選擇排序 vs 插入排序同是 O(n2)差在哪如果拿選擇排序和插入排序在實際數(shù)據(jù)上比跑大多數(shù)場景下插入排序更快尤其是數(shù)據(jù)局部有序時。選擇排序的比較次數(shù)雷打不動插入排序遇到有序數(shù)據(jù)直接變成線性掃描選擇排序雖然交換少但比較的代價同樣顯著。我在實測里體會很直觀一萬條基本有序的數(shù)據(jù)插入排序幾乎是瞬間完成選擇排序卻還在按老節(jié)奏掃描完整的兩層循環(huán)。所以如果必須在“兩個簡單排序”里選一個給實際項目用我會選插入排序。選擇排序更適合的教學定位是理解“確定性掃描 交換”這種構造性思路。6. 同一份數(shù)據(jù)跑一遍四種排序的真實差距復雜度分析是理論但“差距到底多大”還是得來點實測數(shù)據(jù)。我在本機用 Python 做了一次簡單基準測試環(huán)境是常見的處理器和 Python 默認環(huán)境結果不作為絕對指標只看相對趨勢。測試數(shù)據(jù)分四種隨機數(shù)組、基本有序數(shù)組只有少量元素亂序、完全逆序數(shù)組、全相等數(shù)組。規(guī)模取 1000、10000、100000 三檔每個用例跑若干次取穩(wěn)定值。單位約秒。規(guī)模 / 數(shù)據(jù)插入排序冒泡排序選擇排序快排隨機基準1000 隨機0.0080.0120.0080.000510000 隨機0.090.130.080.006100000 隨機8.212.46.50.07100000 基本有序0.00030.00056.50.06100000 逆序16.112.66.50.08100000 全相等0.00030.00046.50.08這里如果用固定基準可能會崩6.1 數(shù)據(jù)里能讀出什么隨機數(shù)據(jù)下快排在 10 萬規(guī)模已經(jīng)和三個 O(n2) 排序拉開兩個數(shù)量級差距這不是“優(yōu)化一下常數(shù)”能追上的是復雜度曲線決定的。三個 O(n2) 排序里插入和選擇在隨機數(shù)據(jù)下相近冒泡最慢因為它的交換動作最多。基本有序和全相等數(shù)據(jù)下插入和冒泡因為提前退出機制表現(xiàn)遠超選擇。全相等時插入排序的 while 條件 arr[j] key 一次都不成立等于線性掃完冒泡也沒有任何交換一趟就退出。這說明理論“最好情況”不是紙面概念真實數(shù)據(jù)里經(jīng)常遇到。逆序數(shù)據(jù)下插入排序反而最慘因為每次插入都要挪動大量元素冒泡和選擇相對穩(wěn)定快排這里用的隨機基準基本不受影響。如果你寫快排時固定取最后一個元素當基準遇到逆序數(shù)據(jù)可能要面對災難級的退化我這次測試里特意避開了這種情況。6.2 為什么復雜度不是唯一標準從這張小表能看出同樣是 O(n2)實際相差可能到兩倍甚至更多同樣是 O(n log n)實現(xiàn)優(yōu)劣也影響很大。數(shù)據(jù)規(guī)模小的時候常數(shù)更重要的排序算法可能比“理論更快”的算法更適合。所以選排序算法我習慣按這個順序問自己數(shù)據(jù)量多大數(shù)據(jù)是否近似有序是否對穩(wěn)定性有硬性要求然后才談復雜度。6.3 實戰(zhàn)選擇建議數(shù)據(jù)量小比如幾百個或數(shù)據(jù)基本有序插入排序。代碼簡單常數(shù)小最好情況簡直是開掛。中間量級且不要求穩(wěn)定快排最好帶上隨機基準。教學演示或小工具冒泡、選擇都可以但別在生產(chǎn)環(huán)境拿冒泡去排大數(shù)據(jù)。有穩(wěn)定性要求且數(shù)據(jù)量大不要用快排考慮歸并排序或語言標準庫里的穩(wěn)定排序實現(xiàn)。不想動腦直接調用標準庫排序絕大多數(shù)語言標準庫已經(jīng)針對混合場景做了大量優(yōu)化。手寫排序更多是為了學習和面試不代表生產(chǎn)環(huán)境一定要重復造輪子。7. 手寫排序的翻車現(xiàn)場與自測清單最后把我個人的踩坑經(jīng)驗集中成一份“防翻車清單”。面試或考試手寫排序時時間緊、壓力大最容易出問題的不是思路而是邊界。我見過太多人在快排遞歸邊界和插入排序的循環(huán)條件上反復掙扎。排序常見錯誤可能的后果插入排序外層從 0 開始循環(huán)忘記保存 keywhile 里用 結果錯誤覆蓋丟失數(shù)據(jù)穩(wěn)定性被破壞冒泡排序內層范圍越界忘記 swapped 判斷內外層循環(huán)顛倒越界異常失去提前退出結果錯誤快速排序遞歸范圍寫成 p 而不是 p-1/p1partition 返回下標算錯固定基準遇有序數(shù)據(jù)退化死循環(huán)或棧溢出排序錯誤性能災難選擇排序內層從 i 開始而不是 i1min_idx 沒有每輪重置交換未檢查是否相同無意義自交換錯誤額外寫操作這份表不一定涵蓋所有錯誤但都是我身邊同事和自己在練習中真實踩過的。7.1 寫完之后用“對數(shù)器”思想自測我有一個固定測試套路每次寫完排序都會跑一遍。方法很簡單寫一個隨機數(shù)組生成器生成大量隨機數(shù)組將手寫排序的結果和語言內置排序的結果逐項對比。一旦出現(xiàn)不一致馬上用二分縮小范圍找到第一個出錯的最小數(shù)組。這個思路和軟件測試里的“差分測試”一脈相承能快速定位問題。除了隨機數(shù)組還必須測這幾種特殊輸入空數(shù)組、單元素數(shù)組、全相等數(shù)組、升序數(shù)組、降序數(shù)組、包含負數(shù)和重復元素的數(shù)組。很多排序 bug 都是在這些邊界輸入里現(xiàn)形的。7.2 一個從 0 到 100000 的測試腳本結構如果你也想復現(xiàn)上面的實測可以直接照這個思路寫三種數(shù)據(jù)生成函數(shù)一個計時包裝函數(shù)若干排序函數(shù)最后匯總打印。排序函數(shù)要注意原地修改數(shù)組計時前先復制一份原始數(shù)據(jù)否則第一個排序跑完后面的排序拿到的已經(jīng)是排好的數(shù)組結果完全失真。我最早測試時就犯過這個錯冒泡跑完數(shù)組已經(jīng)有序緊接著插入排序去排一個有序數(shù)組成績好得嚇人我還差點以為是插入排序超神了。后來才發(fā)現(xiàn)是忘了復制副本。這個坑看著低級實際很普遍大家一定要留意。7.3 我在這個項目里最后的實踐體會把四種排序從頭到尾親手實現(xiàn)一遍最大的收獲不是“我背熟了四種代碼”而是終于理解了一個道理同一個復雜度的算法實現(xiàn)細節(jié)可以把性能拉開好幾倍同一個思路選擇不同的分區(qū)策略、不同的等號處理、不同的邊界收縮方式行為可能完全不一樣。排序算法表面上是一個“背答案”的題目實際上是最典型的“細節(jié)里見真章”。如果非要給一條建議我會說不要只背代碼動手把每一種排序都改成自己能講清原理的版本再對著特殊數(shù)據(jù)測試一遍。這個過程做完你再遇到任何“要求手寫簡單排序”的場景都不會心虛。這也是我團隊里新人入職培訓時我唯一強制要求的入門練習。 四種基礎排序算法詳解：實現(xiàn)、復雜度與避坑指南
直接插入排序、冒泡排序、快速排序、選擇排序這四兄弟幾乎出現(xiàn)在每一本算法教材的目錄前幾頁也幾乎出現(xiàn)在每一次筆試的白紙上方。說實話我?guī)蛨F隊做基礎算法梳理的時候最常被問倒的不是紅黑樹也不是動態(tài)規(guī)劃恰恰是這些“以為閉著眼都能寫”的排序。這篇文章不打算抄書我就用一次完整實現(xiàn)的過程把這四種排序的代碼、復雜度、適用場景和我自己踩過的坑一次性講透。適合正在準備筆試面試的朋友也適合剛學數(shù)據(jù)結構、想把排序真正寫對而不是“背對”的人。讀完之后你至少能收獲三樣東西隨時能正確手寫四種排序的底氣和邊界意識一張可以對著看的數(shù)據(jù)速查表還有一份我自己用過的排序代碼自測清單。1. 四種排序為什么總是它們四個一起出現(xiàn)很多初學者會困惑排序算法有歸并、堆排、基數(shù)、桶排為什么教材偏偏把插入、冒泡、快排、選擇這四種放在同一章原因不是它們性能最好而是它們四個人恰好代表了基礎算法設計的幾種最典型思路。插入排序代表的是“增量式構建”假設左邊已經(jīng)有序往里面插入新元素。冒泡排序代表的是“相鄰交換驅動”通過不斷交換相鄰逆序對讓序列慢慢變好。快速排序代表的是“分治切割”選一個基準把問題拆成兩個獨立子問題遞歸解決。選擇排序代表的是“貪心式掃描”每次都從剩余元素里挑出最值放到目標位置。這四種思路一旦吃透后面學歸并、堆排、希爾、桶排序你會覺得很順因為本質都是在這些母題上加優(yōu)化。它們還共同構成了一個很好的復雜度對照樣本為什么有的排序 O(n2)有的能做到 O(n log n)為什么穩(wěn)定性和原地性又不能同時得到這些概念都可以拿它們當引子。1.1 外行怎么理解這四件事我先給個生活化的錨點后面代碼才不會跑偏。插入排序就像打撲克時理牌摸到一張新牌從右往左比找到位置插進去。冒泡排序就像一杯水里的小氣泡大的元素不斷往上或往右浮?？炫啪拖癜嗉壟抨犗入S便拉一個人當基準矮的站左邊高的站右邊兩邊各自再重復這個過程。選擇排序最像商品比價每輪掃一遍把當前最便宜的挑出來放到購物車第一個位置接著掃剩下的。這四個比喻能幫你記住“每輪在做什么”。但代碼實現(xiàn)里的坑光靠比喻可躲不過去下面逐個展開。1.2 一張表看清四種排序的基本盤在寫代碼之前先把結論擺出來。這里說的“穩(wěn)定”指元素值相等時排序后相對順序是否保持原樣。額外空間指除了原始數(shù)組外額外占用的內存規(guī)模。排序算法平均時間復雜度最壞時間復雜度最好時間復雜度額外空間原地排序穩(wěn)定插入排序O(n2)O(n2)O(n)O(1)是穩(wěn)定冒泡排序O(n2)O(n2)O(n)加提前終止O(1)是穩(wěn)定快速排序O(n log n)O(n2)O(n log n)O(log n) 遞歸棧是不穩(wěn)定選擇排序O(n2)O(n2)O(n2)O(1)是不穩(wěn)定這張表我建議你親手建一次而不是直接背。因為你會在建表過程中意識到很多細節(jié)為什么插入排序最好能達到 O(n)為什么快排的平均復雜度能那么低為什么選擇排序怎么優(yōu)化都是 O(n2)。這些問題的答案恰恰藏在實現(xiàn)細節(jié)里。2. 直接插入排序把“整理手牌”的動作寫成代碼直接插入排序可以說是最好理解的一個。每輪開始前數(shù)組左邊一小段已經(jīng)有序我只需要把當前這個元素往左送送到它該在的位置。整個過程沒有任何“全局規(guī)劃”就是局部調整。先看我最終采用的實現(xiàn)def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr就這么幾行但里面的每一處邊界都值得掰開講。2.1 從摸牌動作推導循環(huán)結構模擬一下手里已經(jīng)有 arr[0..i-1]這 i 個元素是排好序的?，F(xiàn)在摸到 arr[i]也就是代碼里的 key。我把它和前面依次比較如果前面的數(shù)更大就往后挪一格給新牌騰位置如果前面某個數(shù)已經(jīng)比 key 小或相等說明位置找到了把 key 放進去。這里的循環(huán)不變量是每一輪外層循環(huán)結束時arr[0..i] 都是有序的。所以一開始 i 從 1 開始而不是 0因為單個元素天然有序不需要插入。很多初學者把 i 寫成從 0 開始結果第一輪就把自己搞糊涂了。代碼里的 while 循環(huán)在把大元素往右搬移。arr[j 1] arr[j] 不是交換而是覆蓋式右移。這個動作很像撲克牌整理時把大牌往右邊推騰出空位。最后 arr[j 1] key把新牌放回空位。2.2 為什么用“移動”而不是“交換”插入排序的內部動作是移動不是交換。這一點很多實現(xiàn)寫錯。用交換也可以完成排序但會把簡單問題復雜化每交換一次就要做三次賦值而且還會多做很多無意義的數(shù)組寫操作。移動則是從右到左一次性搬移最后再寫一次新值。還有一個穩(wěn)定性細節(jié)while 的條件是 arr[j] key不是 。如果是大于等于相等元素也會被從右邊搬過去相等值的相對順序就被破壞了。只要堅持“只有嚴格大于才搬運”插入排序就是穩(wěn)定的。這個等于號的選擇是所有排序實現(xiàn)里最容易忽略的穩(wěn)定性開關。還有一個隱藏邊界j 可能一路減到 -1。如果 key 是整個數(shù)組里最小的while 會一直執(zhí)行到 j -1 退出最后 arr[0] key正好把最小的數(shù)放到開頭。所以 arr[j 1] 這里的下標不是錯誤是刻意讓它落到 arr[0]。2.3 插入排序的隱藏優(yōu)勢近乎有序時就該它上場插入排序最被人低估的點是對“幾乎有序”的數(shù)據(jù)極度友好。如果輸入已經(jīng)是升序for 循環(huán)里的 while 一次都不會進整個排序變成一趟線性掃描時間 O(n)。這一點在表格里看起來不明顯但實際工程里非常重要。很多高性能排序算法比如 TimSort在局部小規(guī)模或接近有序的分塊里底層用的就是插入排序。原因有兩個一是插入排序常數(shù)極小不需要額外空間二是它對“部分有序”數(shù)據(jù)利用率極高。我自己寫小工具時如果數(shù)據(jù)量小于 16 并且確定基本有序干脆直接插入排序比什么花哨算法都穩(wěn)。2.4 寫插入排序最常見的兩個翻車點第一忘記保存 key。我見過不少版本先寫 arr[i 1] arr[j]結果 arr[i] 被覆蓋后續(xù)循環(huán)全亂。必須先key arr[i]心里要清楚這個值就是“新摸的牌”后面所有比較和挪動都圍繞它。第二內層循環(huán)方向寫反。如果從左往右掃描找位置那騰位置時會覆蓋還沒比較的元素邏輯非常繞。記住插入排序是“從右往左倒著比”這和手理撲克牌的習慣一致。3. 冒泡排序最“笨”的排序藏著兩個容易忽略的優(yōu)化點冒泡排序在工程里基本沒有存在感但在教學里地位很高因為它把“有序性如何通過相鄰交換逐步建立”這件事展示得最清楚?；A實現(xiàn)長這樣def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr很多人背代碼時直接把里面兩個循環(huán)套上就完事完全沒看懂 swapped 和內層 j 范圍為什么這樣寫。我分別說。3.1 外層循環(huán)控制“趟數(shù)”內層循環(huán)制造“上浮”冒泡每一趟都會從數(shù)組最左邊開始兩兩比較相鄰元素如果順序反了就交換。因為大的元素每比較一次就往右挪一步經(jīng)過一整趟之后當前最大值一定被推到了數(shù)組末尾。所以下一趟就不用再看最后那個位置內層 j 范圍收縮成n - 1 - i。外層循環(huán)只需要 n - 1 趟。為什么不是 n 趟因為最后剩下一個元素時它已經(jīng)是唯一的位置不需要再比。這和插入排序外層從 1 開始有異曲同工的味道排序終止條件總比 n 少一點。3.2 提前終止讓“最好情況”從 O(n2) 變成 O(n)如果不加 swapped就算數(shù)組已經(jīng)天然升序冒泡排序也會把所有相鄰元素比較一遍照常跑完 n - 1 趟白費時間。加了 swapped 標記之后只要某一趟從頭到尾沒有任何交換說明數(shù)組已經(jīng)有序直接 break。這個優(yōu)化不改變平均復雜度但讓冒泡的最好情況變成 O(n)。千萬別以為這只是可有可無的小技巧在面試里問“冒泡排序最好情況是多少”時很多人答 O(n2)就是因為沒意識到這個標記的存在。從實現(xiàn)角度它同時也暴露了冒泡排序的一個核心特征它的比較次數(shù)并不固定和輸入有序度強相關。3.3 冒泡排序為什么名聲差但還沒被教材刪掉冒泡被罵核心原因是它做了太多無效工作。一趟只能把一個最大值送到最終位置如果數(shù)組中有一個小元素在最后面它就不得不一趟一趟地往左挪像個“慢?！薄?shù)據(jù)量稍微一大比如 10 萬條隨機整數(shù)冒泡的耗時就會膨脹到讓人難以接受比插入排序還要慢上不少因為交換涉及三次賦值而插入排序大部分時候只需要搬移。但它沒被教材刪是因為它太適合入門了。雙重循環(huán)、相鄰交換、穩(wěn)定性、提前終止、邊界控制這些概念都可以在一個簡單代碼里展示。作為實現(xiàn)練習冒泡是很好的“腳手架”。你甚至可以基于它引出一個經(jīng)典問題為什么相鄰交換排序很難突破 O(n2)這與“逆序對”數(shù)量相關每交換一次才消除一個逆序對這為后面學習更快的排序埋下伏筆。3.4 手寫冒泡最容易犯的三個錯一是內層循環(huán)寫成for j in range(n - i)這時 j 會取到n - i - 1跟 j 1 比較時越界。記住范圍是n - 1 - i留出右側的“已排好區(qū)域”。二是忘記在循環(huán)末尾判斷 swapped導致排序結果沒錯但最好情況優(yōu)化失效。三是把兩個循環(huán)方向搞反外層跑內層、內層跑外層排序結果一團亂。其實寫完冒泡之后我建議你做個小實驗把 swapped 去掉再跑一次對比一下輸入是有序數(shù)組時的執(zhí)行時間你就理解這個標記到底省了什么。4. 快速排序思路三句話代碼卻處處是細節(jié)到了快排代碼量一下子變多但核心思路仍然是三句話選一個基準值把比它小的放左邊、比它大的放右邊然后對左右兩個部分遞歸做同樣的事。我用比較常見的 Lomuto 分區(qū)方式來寫from random import randint def quick_sort(arr, low, high): if low high: p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) def partition(arr, low, high): pivot_index randint(low, high) arr[pivot_index], arr[high] arr[high], arr[pivot_index] pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1調用方式是quick_sort(arr, 0, len(arr) - 1)。這里我特意加入了隨機選基準原因后面細說。4.1 partition 到底在做什么Lomuto 分區(qū)的思路很直接取最后一個元素當基準 pivot然后讓 i 指向“當前已發(fā)現(xiàn)的小于等于 pivot 的區(qū)間右邊界”。一開始 i low - 1表示這個區(qū)間為空。然后 j 從頭掃到 high - 1每當發(fā)現(xiàn) arr[j] 小于等于 pivot就把 i 右移一位并把 arr[j] 交換過去。你可以把 i 想象成“分界線”左邊是已經(jīng)歸位的小值隊列右邊是等待掃描的大值隊列。掃描結束后arr[i 1] 這個位置就是基準值應該待的位置把基準交換過來返回 i 1 作為分界點。注意這里用的是而不是。用會把等于基準的值留在右側雖然排序結果還是對的但分區(qū)會偏向不均衡而且等于基準的元素來回跑整體性能下降。用意味著相等元素也歸到左區(qū)分區(qū)更穩(wěn)。4.2 三個最容易寫錯的地方第一遞歸范圍必須是p - 1和p 1不能把 p 包含進去。因為 p 位置上的元素已經(jīng)最終歸位再遞歸它會造成死循環(huán)或無效重復。道理很簡單但手寫時緊張?zhí)貏e容易漏掉 1 和 -1。第二partition 返回的是基準值的最終下標這個下標是遞歸分界。如果返回錯誤比如返回 i 而不是 i 1整個排序就會立刻亂套。建議自己在紙上跑一個長度為 5 的小數(shù)組親眼看看基準最終落在哪里。第三當數(shù)組里全是相等元素時Lomuto 分區(qū)可能退化成 O(n2)因為每次分區(qū)都極不均衡。這個情況很隱蔽普通隨機測試測不出來。工程上解決它的主流方案是三路快速排序把數(shù)組切分成“小于基準”“等于基準”“大于基準”三段中間段不再參與遞歸。面試時能提到這一點通常是個加分項。4.3 為什么快排不穩(wěn)定工業(yè)界還在大面積使用快排的不穩(wěn)定主要體現(xiàn)在分區(qū)交換時相等元素可能被交換到另一側相對順序無法保證。既然不穩(wěn)定為什么標準庫還在大量用快排因為對于基本類型數(shù)據(jù)穩(wěn)定性沒有實際意義。Java 的Arrays.sort對基本類型數(shù)組用的就是雙基準快排C 的qsort也是快排變體。基本類型拿不出“原始相對順序”這種概念排序后誰在哪都無所謂而對象排序通常需要穩(wěn)定性Java 對對象用的就是 TimSort/歸并排序。所以選型要看數(shù)據(jù)類型而不是一句“快排最好”通吃。快排核心優(yōu)勢是原地排序、緩存友好、平均常數(shù)小。同等數(shù)據(jù)量下它能吞吐掉大量元素訪問和交換實際速度比很多“理論更優(yōu)”的算法更猛。這也是為什么平均復雜度同為 O(n log n)工程上更偏愛快排而不是歸并的常見原因。4.4 隨機化基準一次必要的防守如果每次固定取最后一個元素作為基準面對已經(jīng)有序的數(shù)組每次分區(qū)都會得到一邊空、一邊 n-1 的極端情況遞歸深度逼近 n復雜度退化成 O(n2)甚至可能因為遞歸過深爆棧。隨機化基準的核心目的是避免這種系統(tǒng)性的壞運氣讓“最壞情況”變成概率極低的事件。有些人覺得隨機化沒必要覺得“我數(shù)據(jù)沒那么壞”。但真實場景里數(shù)據(jù)來源誰也說不準。你拿到的可能就是按某種規(guī)則排好的或高度規(guī)律的數(shù)據(jù)固定基準就是定時炸彈。我建議平時練習就養(yǎng)成隨機化的習慣面試手寫時如果允許也可以說“這里再隨機選一個 pivot 防止退化”。5. 選擇排序看起來最直觀實現(xiàn)時別踩穩(wěn)定性的坑選擇排序的思路比快排簡單得多第一輪掃全數(shù)組找最小元素和 arr[0] 交換第二輪從 arr[1] 開始找最小和 arr[1] 交換依此類推。每次確定一個位置的最終值。實現(xiàn)如下def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr這代碼本身不難但背后的兩個問題值得展開它交換次數(shù)少卻不穩(wěn)定。5.1 “每次選最小”的代碼究竟在循環(huán)什么外層循環(huán) i 表示當前位置內層循環(huán)從 i 1 掃到末尾找出最小元素的索引 min_idx。內層只記錄下標不急著交換等整輪掃完再交換這樣就確保了每輪最多一次交換。min_idx初始化為 i 是必要的。如果后面所有元素都比 arr[i] 大min_idx 就保持為 i交換操作可以跳過。有些實現(xiàn)不檢查 min_idx ! i每次都交換雖然結果沒錯但多出不少無意義寫操作。養(yǎng)成檢查的習慣寫出來的排序更干凈。5.2 交換次數(shù)低卻在有些場景下有奇用選擇排序的比較次數(shù)永遠是 n(n-1)/2不管數(shù)據(jù)是否有序所以它沒有任何“最好情況”優(yōu)勢。但它的交換次數(shù)最多只有 n - 1這在“寫操作代價遠高于讀操作”的場景里是實打實的優(yōu)勢。比如某些存儲設備寫入壽命有限或者元素本身是一個很大的對象每次交換都要復制大量字段。這時候選擇排序的“少寫”特性比插入、冒泡都好。當然這是一種偏門場景日常排序基本用不上但理解它你會明白復雜度不是算法選擇的唯一維度。5.3 選擇排序為什么不穩(wěn)定說一個最容易理解的例子數(shù)組是 [5a, 5b, 2]其中兩個 5 我們用 a、b 做標記區(qū)分。第一輪掃描找到最小值 2把它和 arr[0] 也就是 5a 交換數(shù)組變成 [2, 5b, 5a]。你看原本 5a 在 5b 前面排序后 5b 跑到前面去了相對順序被破壞。有人會說“那我掃描的時候只有嚴格小于才更新 min_idx不碰相等元素不就行了嗎”但問題不在這里。問題是交換動作本身就是跳躍式的可能跨越多個相等元素。要恢復穩(wěn)定性需要額外策略比如從右往左掃、把相等元素盡量留到左側但那已經(jīng)不像標準選擇排序了。所以默認你寫的、教材上的選擇排序就當它不穩(wěn)定面試時這樣說最穩(wěn)妥。5.4 選擇排序 vs 插入排序同是 O(n2)差在哪如果拿選擇排序和插入排序在實際數(shù)據(jù)上比跑大多數(shù)場景下插入排序更快尤其是數(shù)據(jù)局部有序時。選擇排序的比較次數(shù)雷打不動插入排序遇到有序數(shù)據(jù)直接變成線性掃描選擇排序雖然交換少但比較的代價同樣顯著。我在實測里體會很直觀一萬條基本有序的數(shù)據(jù)插入排序幾乎是瞬間完成選擇排序卻還在按老節(jié)奏掃描完整的兩層循環(huán)。所以如果必須在“兩個簡單排序”里選一個給實際項目用我會選插入排序。選擇排序更適合的教學定位是理解“確定性掃描 交換”這種構造性思路。6. 同一份數(shù)據(jù)跑一遍四種排序的真實差距復雜度分析是理論但“差距到底多大”還是得來點實測數(shù)據(jù)。我在本機用 Python 做了一次簡單基準測試環(huán)境是常見的處理器和 Python 默認環(huán)境結果不作為絕對指標只看相對趨勢。測試數(shù)據(jù)分四種隨機數(shù)組、基本有序數(shù)組只有少量元素亂序、完全逆序數(shù)組、全相等數(shù)組。規(guī)模取 1000、10000、100000 三檔每個用例跑若干次取穩(wěn)定值。單位約秒。規(guī)模 / 數(shù)據(jù)插入排序冒泡排序選擇排序快排隨機基準1000 隨機0.0080.0120.0080.000510000 隨機0.090.130.080.006100000 隨機8.212.46.50.07100000 基本有序0.00030.00056.50.06100000 逆序16.112.66.50.08100000 全相等0.00030.00046.50.08這里如果用固定基準可能會崩6.1 數(shù)據(jù)里能讀出什么隨機數(shù)據(jù)下快排在 10 萬規(guī)模已經(jīng)和三個 O(n2) 排序拉開兩個數(shù)量級差距這不是“優(yōu)化一下常數(shù)”能追上的是復雜度曲線決定的。三個 O(n2) 排序里插入和選擇在隨機數(shù)據(jù)下相近冒泡最慢因為它的交換動作最多。基本有序和全相等數(shù)據(jù)下插入和冒泡因為提前退出機制表現(xiàn)遠超選擇。全相等時插入排序的 while 條件 arr[j] key 一次都不成立等于線性掃完冒泡也沒有任何交換一趟就退出。這說明理論“最好情況”不是紙面概念真實數(shù)據(jù)里經(jīng)常遇到。逆序數(shù)據(jù)下插入排序反而最慘因為每次插入都要挪動大量元素冒泡和選擇相對穩(wěn)定快排這里用的隨機基準基本不受影響。如果你寫快排時固定取最后一個元素當基準遇到逆序數(shù)據(jù)可能要面對災難級的退化我這次測試里特意避開了這種情況。6.2 為什么復雜度不是唯一標準從這張小表能看出同樣是 O(n2)實際相差可能到兩倍甚至更多同樣是 O(n log n)實現(xiàn)優(yōu)劣也影響很大。數(shù)據(jù)規(guī)模小的時候常數(shù)更重要的排序算法可能比“理論更快”的算法更適合。所以選排序算法我習慣按這個順序問自己數(shù)據(jù)量多大數(shù)據(jù)是否近似有序是否對穩(wěn)定性有硬性要求然后才談復雜度。6.3 實戰(zhàn)選擇建議數(shù)據(jù)量小比如幾百個或數(shù)據(jù)基本有序插入排序。代碼簡單常數(shù)小最好情況簡直是開掛。中間量級且不要求穩(wěn)定快排最好帶上隨機基準。教學演示或小工具冒泡、選擇都可以但別在生產(chǎn)環(huán)境拿冒泡去排大數(shù)據(jù)。有穩(wěn)定性要求且數(shù)據(jù)量大不要用快排考慮歸并排序或語言標準庫里的穩(wěn)定排序實現(xiàn)。不想動腦直接調用標準庫排序絕大多數(shù)語言標準庫已經(jīng)針對混合場景做了大量優(yōu)化。手寫排序更多是為了學習和面試不代表生產(chǎn)環(huán)境一定要重復造輪子。7. 手寫排序的翻車現(xiàn)場與自測清單最后把我個人的踩坑經(jīng)驗集中成一份“防翻車清單”。面試或考試手寫排序時時間緊、壓力大最容易出問題的不是思路而是邊界。我見過太多人在快排遞歸邊界和插入排序的循環(huán)條件上反復掙扎。排序常見錯誤可能的后果插入排序外層從 0 開始循環(huán)忘記保存 keywhile 里用 結果錯誤覆蓋丟失數(shù)據(jù)穩(wěn)定性被破壞冒泡排序內層范圍越界忘記 swapped 判斷內外層循環(huán)顛倒越界異常失去提前退出結果錯誤快速排序遞歸范圍寫成 p 而不是 p-1/p1partition 返回下標算錯固定基準遇有序數(shù)據(jù)退化死循環(huán)或棧溢出排序錯誤性能災難選擇排序內層從 i 開始而不是 i1min_idx 沒有每輪重置交換未檢查是否相同無意義自交換錯誤額外寫操作這份表不一定涵蓋所有錯誤但都是我身邊同事和自己在練習中真實踩過的。7.1 寫完之后用“對數(shù)器”思想自測我有一個固定測試套路每次寫完排序都會跑一遍。方法很簡單寫一個隨機數(shù)組生成器生成大量隨機數(shù)組將手寫排序的結果和語言內置排序的結果逐項對比。一旦出現(xiàn)不一致馬上用二分縮小范圍找到第一個出錯的最小數(shù)組。這個思路和軟件測試里的“差分測試”一脈相承能快速定位問題。除了隨機數(shù)組還必須測這幾種特殊輸入空數(shù)組、單元素數(shù)組、全相等數(shù)組、升序數(shù)組、降序數(shù)組、包含負數(shù)和重復元素的數(shù)組。很多排序 bug 都是在這些邊界輸入里現(xiàn)形的。7.2 一個從 0 到 100000 的測試腳本結構如果你也想復現(xiàn)上面的實測可以直接照這個思路寫三種數(shù)據(jù)生成函數(shù)一個計時包裝函數(shù)若干排序函數(shù)最后匯總打印。排序函數(shù)要注意原地修改數(shù)組計時前先復制一份原始數(shù)據(jù)否則第一個排序跑完后面的排序拿到的已經(jīng)是排好的數(shù)組結果完全失真。我最早測試時就犯過這個錯冒泡跑完數(shù)組已經(jīng)有序緊接著插入排序去排一個有序數(shù)組成績好得嚇人我還差點以為是插入排序超神了。后來才發(fā)現(xiàn)是忘了復制副本。這個坑看著低級實際很普遍大家一定要留意。7.3 我在這個項目里最后的實踐體會把四種排序從頭到尾親手實現(xiàn)一遍最大的收獲不是“我背熟了四種代碼”而是終于理解了一個道理同一個復雜度的算法實現(xiàn)細節(jié)可以把性能拉開好幾倍同一個思路選擇不同的分區(qū)策略、不同的等號處理、不同的邊界收縮方式行為可能完全不一樣。排序算法表面上是一個“背答案”的題目實際上是最典型的“細節(jié)里見真章”。如果非要給一條建議我會說不要只背代碼動手把每一種排序都改成自己能講清原理的版本再對著特殊數(shù)據(jù)測試一遍。這個過程做完你再遇到任何“要求手寫簡單排序”的場景都不會心虛。這也是我團隊里新人入職培訓時我唯一強制要求的入門練習。