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