如果你被問“排序算法先學(xué)哪個”很多人會脫口而出冒泡排序。但我在給新人講算法時反而更愿意從選擇排序開始。原因很簡單它的核心思路可以用一句話講明白——每一輪從剩下的元素里挑一個最小的放到已排好部分的末尾。這句話聽上去像廢話可背后牽扯到循環(huán)邊界、索引選擇、交換次數(shù)、穩(wěn)定性等一堆值得掰開揉碎的東西。這篇“每日一算法”就拿選擇排序開刀從思想到代碼再到面試常問的坑一次性講透。適合正在被算法入門折磨的朋友也適合準備筆試面試、想快速把排序基礎(chǔ)撿回來的開發(fā)者。1. 選擇排序整體設(shè)計與思路拆解1.1 核心思想每一輪只干一件事選擇排序的思路非常樸素你可以把它想象成在一排亂序的隊伍里反復(fù)“挑矮子”。假設(shè)有 5 個人排隊身高分別是 175、160、185、150、170。你要把這支隊伍按從矮到高排列。最笨但有效的辦法是先在所有人里找出最矮的那個人讓他站到第一位然后從剩下 4 個人里再找出最矮的站到第二位接著從剩下 3 個人里找最矮的站到第三位……直到只剩最后一個人排序自然完成。這就是選擇排序的模型。對應(yīng)到數(shù)組上每一輪的處理邏輯只有三步從待排序區(qū)間里找到最小元素的下標把最小元素與待排序區(qū)間的第一個位置交換將待排序區(qū)間的左邊界向右移動一位。值得注意它和“冒泡排序”的直觀感覺不同。冒泡排序是一路兩兩比較、不斷把大元素往后“冒”選擇排序則是一輪掃描完直接定位到最小值的位置再做一次交換。所以選擇排序的特點是比較很勤快但交換很“吝嗇”。這一點在后面分析復(fù)雜度時會變成它的優(yōu)勢。1.2 為什么值得專門為它寫一篇很多初學(xué)者會問選擇排序明明效率不高為什么還要學(xué)第一個原因它是理解“選擇類算法”的基石。后面學(xué)堆排序時你會發(fā)現(xiàn)堆排序本質(zhì)上就是選擇排序的“升級版”同樣每輪選一個最值只是它用一個二叉堆把“找最值”的耗時從 O(n) 降到了 O(log n)。不懂選擇排序就很難理解堆排序為什么要設(shè)計堆這個結(jié)構(gòu)。第二個原因它在特定場景下仍然有實用價值。當(dāng)數(shù)組規(guī)模很小比如幾十個元素并且交換元素的開銷遠大于比較元素的開銷時選擇排序的“最少交換次數(shù)”特性就很香。因為無論數(shù)據(jù)怎么亂它最多只會發(fā)生 n-1 次交換。相比之下冒泡排序在最壞情況下交換次數(shù)也是 n(n-1)/2和它的比較次數(shù)一個量級代價高得多。第三個原因它是訓(xùn)練循環(huán)邊界感和調(diào)試能力的絕佳素材。算法雖簡單但很容易在“循環(huán)起點是 i 還是 i1”“最小值下標要不要更新”“空數(shù)組會不會越界”這些地方翻車。把選擇排序?qū)憣Α懛€(wěn)很多排序類算法的基本功也就順帶練出來了。1.3 和冒泡排序、插入排序的定位差別學(xué)排序時最怕把幾個 O(n2) 排序搞混。我用一個表格把選擇排序和它最常被比較的兩位“鄰居”列在一起。維度選擇排序冒泡排序插入排序核心動作選擇最小值 / 最大值相鄰比較后交換把當(dāng)前元素插入到已排序區(qū)比較次數(shù)固定 n(n-1)/2最好 O(n)最壞 O(n2)最好 O(n)最壞 O(n2)交換次數(shù)最多 n-1 次最多 n(n-1)/2 次賦值操作較多但可控制在 O(n2)穩(wěn)定性不穩(wěn)定穩(wěn)定穩(wěn)定適合場景小規(guī)模、交換代價高教學(xué)示例、基本有序數(shù)組數(shù)據(jù)基本有序、在線排序從表格能看出選擇排序最大的“記憶點”就是穩(wěn)定性和交換次數(shù)。它不穩(wěn)定不是實現(xiàn)細節(jié)的問題而是“跨距離交換”這一策略決定的一個最小值可能從數(shù)組末尾直接換到最前面途經(jīng)的相同值相對順序就亂了。至于插入排序雖然同樣是 O(n2)但在基本有序的數(shù)據(jù)上表現(xiàn)出色因為內(nèi)層循環(huán)能提前退出而選擇排序不管數(shù)據(jù)是否有序都要傻傻地把剩下元素全掃一遍。理解了這些差異實際選型時才不會拍腦袋。2. 核心細節(jié)解析與實操要點2.1 手工推演一次完整的排序過程光講概念不夠我拿一個經(jīng)典例子手推一遍。假設(shè)待排序數(shù)組是[64, 25, 12, 22, 11]第 1 輪i0待排序區(qū)間是下標 0 到 4。掃描全部元素找出最小值 11下標為 4。把下標 4 的元素與下標 0 的元素交換數(shù)組變成[11, 25, 12, 22, 64]第 2 輪i1待排序區(qū)間是下標 1 到 4。此時剩余元素是 25、12、22、64。掃描后最小值是 12下標為 2。交換下標 1 和下標 2 的元素數(shù)組變成[11, 12, 25, 22, 64]第 3 輪i2待排序區(qū)間是下標 2 到 4。剩余元素是 25、22、64最小值是 22下標為 3。交換下標 2 和下標 3 的元素數(shù)組變成[11, 12, 22, 25, 64]第 4 輪i3待排序區(qū)間是下標 3 和 4。剩余元素是 25 和 64最小值是 25剛好就在下標 3此時可以不交換或者做一次“自己和自己交換”的無聊操作。數(shù)組保持不變[11, 12, 22, 25, 64]到這里循環(huán)結(jié)束因為當(dāng) i 指向最后一個元素時它天然就是剩余區(qū)間里的最小值沒必要再比較。觀察這個過程你會發(fā)現(xiàn)每輪結(jié)束后下標 0 到 i 這部分就是全局最小的一批元素而且是最終位置。這個性質(zhì)叫“局部有序逐漸擴張”和插入排序“從前往后邊讀邊插”的感覺完全不同。2.2 代碼實現(xiàn)Python 和 C 兩個版本先看 Python 版本代碼非常貼近算法描述def selection_sort(arr): n len(arr) for i in range(n - 1): min_index i for j in range(i 1, n): if arr[j] arr[min_index]: min_index j if min_index ! i: arr[i], arr[min_index] arr[min_index], arr[i] return arr這里有兩個關(guān)鍵點。第一外層循環(huán)是range(n - 1)不是range(n)。因為最后一個元素不需要再和任何人比較它是剩余元素中的唯一選擇。第二內(nèi)層循環(huán)從i 1開始而不是從i開始。因為arr[i]自己和自己比較沒有意義只會白白浪費時間。雖然多一次比較不影響正確性但寫代碼就應(yīng)該寫出最干凈的版本。再看 C 版本方便面試手寫或者嵌入式場景使用#include algorithm void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { std::swap(arr[i], arr[minIdx]); } } }如果你在面試中以“原地排序”為目標這個版本就是滿分解。std::swap本質(zhì)是三次賦值如果你所在環(huán)境不允許用 STL可以自己手寫int temp arr[i]; arr[i] arr[minIdx]; arr[minIdx] temp;2.3 復(fù)雜度與穩(wěn)定性兩個容易被問倒的點選擇排序的時間復(fù)雜度可以拆成兩部分比較次數(shù)和交換次數(shù)。比較次數(shù)固定是n(n-1)/2。因為第 0 輪要比較 n-1 次第 1 輪 n-2 次第 2 輪 n-3 次……加起來就是等差數(shù)列求和。不管你給的數(shù)據(jù)是完全有序、完全逆序還是亂序這個數(shù)字都不會變。所以選擇排序的最好、最壞、平均時間復(fù)雜度都是 O(n2)。交換次數(shù)很有特點。每輪最多只交換一次所以整個排序過程最多交換 n-1 次。如果數(shù)組已經(jīng)有序并且我們寫了if (minIdx ! i)這個判斷那一次交換都不發(fā)生。這是選擇排序在“交換代價極高”場景下的核心優(yōu)勢?？臻g復(fù)雜度是 O(1)因為除了臨時變量之外只需要常數(shù)級別的額外空間。它是典型的不穩(wěn)定排序。我用一個例子說明不穩(wěn)定性[5a, 5b, 3]這里用 5a 和 5b 表示兩個值相同但原始順序不同的元素。第一輪選擇排序會找到最小值 3下標為 2。然后把 3 和下標 0 的 5a 交換數(shù)組變成[3, 5b, 5a]原本在 5a 后面的 5b 現(xiàn)在跑到 5a 前面去了兩個相等元素的相對順序被破壞所以選擇排序不穩(wěn)定。如果你拿這個問題去面試光說“不穩(wěn)定”不夠最好能像這樣當(dāng)場舉出反例。2.4 可以做的兩個小優(yōu)化選擇排序的樸素版本已經(jīng)很好理解但還有兩個常見優(yōu)化思路。優(yōu)化一在交換前加if (minIdx ! i)判斷。這個判斷可以減少無意義的“自己交換自己”雖然不能降低時間復(fù)雜度但能減少賦值次數(shù)對性能有一點實際幫助。優(yōu)化二每輪同時找最小值和最大值。這樣一輪可以放兩個元素到位最小值放到左邊最大值放到右邊。外層循環(huán)的次數(shù)可以減半但內(nèi)層掃描的范圍仍然是每輪逐步收縮。要注意的是如果最小值和最大值的位置有重疊交換邏輯會變得很繞需要處理“先換最小值再換最大值時發(fā)現(xiàn)位置已被覆蓋”的情況。這個優(yōu)化適合數(shù)據(jù)量較大且想寫點“升級版”的時候用面試時主動提出來反而能加分。還有一個值得了解的變種是“堆排序”它把“線性掃描找最小值”升級成“堆頂直接取最小值”時間復(fù)雜度從 O(n2) 降到 O(n log n)。理解選擇排序是理解堆排序的天然跳板。3. 實操過程與核心環(huán)節(jié)實現(xiàn)3.1 從“暴力交換”到“記錄下標”的優(yōu)化很多初學(xué)者第一次寫選擇排序會把交換動作直接放在內(nèi)層循環(huán)里寫成這樣def bad_selection_sort(arr): n len(arr) for i in range(n): for j in range(i 1, n): if arr[j] arr[i]: arr[i], arr[j] arr[j], arr[i] return arr這段代碼在某些測試用例下能跑出正確結(jié)果但它有兩個問題。第一它每發(fā)現(xiàn)一個比arr[i]小的元素就立刻交換導(dǎo)致可能在同一次內(nèi)層循環(huán)里交換很多次。這實際上是“交換式冒泡排序”的變體而不是嚴格意義上的選擇排序因為選擇排序每一輪應(yīng)該只交換一次。第二如果你把內(nèi)層循環(huán)改成從 i1 開始但外層循環(huán)是range(n)最后一輪會空轉(zhuǎn)一次不會報錯但不夠嚴謹。正確的做法是“記錄下標延遲交換”。內(nèi)層循環(huán)只是不斷更新min_index找到本輪真正的全局最小值下標后在外層循環(huán)體內(nèi)統(tǒng)一交換一次。這個差異是選擇排序的精髓面試時手寫代碼一眼就能看出你是真懂還是背代碼。我第一次給別人講這個差異時打了這么個比方暴力交換像逛街買衣服看到一件便宜的就立刻把身上衣服換掉結(jié)果后面又看到更好的還得再換記錄下標則是先把最便宜的那件記在心里逛完一整條街再一次性買下來。選擇排序講究的是“看完再動手”。3.2 邊界條件空數(shù)組、單元素、重復(fù)值算法寫得對不對邊界條件很關(guān)鍵。空數(shù)組[]n 0外層循環(huán)range(n - 1)等價于range(-1)不會進入循環(huán)函數(shù)直接返回空數(shù)組。這個行為符合預(yù)期。單元素數(shù)組[5]n 1外層循環(huán)range(0)同樣不會進入循環(huán)直接返回?？雌饋頉]問題但如果你把外層循環(huán)寫成range(n)雖然也不會越界可每輪啟動一次無意義的掃描不夠干凈。全重復(fù)數(shù)組[3, 3, 3, 3]每一輪掃描都會讓min_index停在當(dāng)前最小的合法下標最終不發(fā)生任何交換數(shù)組保持不變。這體現(xiàn)了if (min_index ! i)判斷的價值。真正容易出問題的其實是大數(shù)組里元素類型不一致。在 Python 里如果數(shù)組是[3, 5, None]比較運算符會直接拋 TypeError。選擇排序依賴運算符所以它要求數(shù)組元素是同類型且可比較的。這在理論上不是算法問題但實操中經(jīng)常被忽略。3.3 可視化驗證用打印看每輪狀態(tài)調(diào)試排序算法最直觀的辦法就是打印數(shù)組狀態(tài)。寫一個帶日志的版本def selection_sort_debug(arr): n len(arr) print(初始狀態(tài):, arr) for i in range(n - 1): min_index i for j in range(i 1, n): if arr[j] arr[min_index]: min_index j if min_index ! i: print(f第 {i} 輪: 找到最小值 {arr[min_index]} (下標 {min_index})與 {arr[i]} (下標 {i}) 交換) arr[i], arr[min_index] arr[min_index], arr[i] else: print(f第 {i} 輪: 最小值 {arr[i]} 已在正確位置無需交換) print(當(dāng)前數(shù)組:, arr) return arr拿前面的例子跑一遍初始狀態(tài): [64, 25, 12, 22, 11] 第 0 輪: 找到最小值 11 (下標 4)與 64 (下標 0) 交換 當(dāng)前數(shù)組: [11, 25, 12, 22, 64]這種輸出對理解算法非常有幫助。我建議所有初學(xué)者都養(yǎng)成“給算法加日志”的習(xí)慣比單純看代碼想象執(zhí)行過程高效得多。熟練以后可以把日志去掉再對照時間復(fù)雜度和空間復(fù)雜度去分析。3.4 性能實測感受一下 O(n2) 的“成長曲線”算法復(fù)雜度的意義光看公式是不夠的最好動手測。我寫了一個簡單的測試腳本用隨機數(shù)據(jù)測選擇排序運行時間import random import time def time_selection_sort(n): arr [random.randint(0, 100000) for _ in range(n)] start time.perf_counter() selection_sort(arr) return time.perf_counter() - start for size in [1000, 2000, 4000, 8000, 16000]: print(fn{size}, 耗時{time_selection_sort(size):.4f}s)輸出大致會是n1000, 耗時0.0040s n2000, 耗時0.0120s n4000, 耗時0.0390s n8000, 耗時0.1450s n16000, 耗時0.5600s可以看到當(dāng) n 從 1000 到 2000規(guī)模翻一倍耗時幾乎翻四倍。這就是 O(n2) 的直觀體感。隨著 n 繼續(xù)增大差距會越來越夸張。到十萬級數(shù)據(jù)時選擇排序就會明顯“卡頓”這時候你才會真正理解為什么工業(yè)界很少用 O(n2) 的排序處理大數(shù)據(jù)。4. 常見問題與排查技巧實錄4.1 常見錯誤速查表我把平時見到的選擇排序翻車案例整理成一個表格方便你對照自查。錯誤類型錯誤寫法示例后果正確做法外層循環(huán)越界for i in range(n)最后一輪空轉(zhuǎn)增加無意義比較用range(n - 1)內(nèi)層循環(huán)起點錯誤for j in range(i, n)多一次自己和自己比較效率低用range(i 1, n)最小值下標未更新if arr[j] arr[i]:退化成冒泡式交換破壞選擇排序特性用min_index記錄本輪最小值交換前沒有判斷下標直接swap(arr[i], arr[minIdx])有序時出現(xiàn)自己交換自己浪費賦值加if (minIdx ! i)判斷穩(wěn)定性認知錯誤認為選擇排序“通常穩(wěn)定”面試答錯概念記住它是不穩(wěn)定排序且要能舉反例把最小值初始化為固定值min_index 0寫在內(nèi)層每輪都無法正確找到當(dāng)前區(qū)間最值初始化為當(dāng)前區(qū)間起點i這里重點說明“最小值初始化為 0”這個坑。如果你在內(nèi)層循環(huán)開始前寫死m(xù)in_index 0那么每一輪都會拿當(dāng)前區(qū)間元素和數(shù)組的第一個元素比較。第一輪可能碰巧沒問題第二輪開始就會選出錯誤的最小值因為數(shù)組第一個元素可能已經(jīng)在上一輪被換成了全局最小而它根本不屬于當(dāng)前待排序區(qū)間。正確寫法是讓min_index從i開始。4.2 面試常被追問的三個點面試官考選擇排序基本繞不開下面三個問題。第一它是穩(wěn)定的嗎答案是“不穩(wěn)定”必須能舉出類似[5a, 5b, 3]的反例。如果面試官追問“能不能改穩(wěn)定”通常也是可以做到的在找最小值時選擇“最后一個”最小值交換時把中間元素依次后移而不是直接交換。這個改動有意思但很少被考察能說出來是加分項。第二復(fù)雜度為什么是 O(n2)你要能快速給出n(n-1)/2的比較次數(shù)推導(dǎo)并解釋為什么比較次數(shù)與初始順序無關(guān)。順帶強調(diào)交換次數(shù)最多n-1次這是選擇排序最容易被人記住的優(yōu)勢。第三什么時候用選擇排序而不是快速排序或歸并排序一種典型回答是當(dāng)數(shù)據(jù)量很小、且一次交換的代價遠大于一次比較時選擇排序的交換次數(shù)優(yōu)勢很明顯。比如在嵌入式環(huán)境中操作外部存儲設(shè)備的寫入次數(shù)有限選擇排序就可以比冒泡排序更省壽命。但要注意現(xiàn)代通用場景下O(n log n)的排序往往更適合。還有一個常見的追問是“和插入排序比誰快”。答案不是絕對的要看數(shù)據(jù)特征。如果數(shù)組基本有序插入排序遠勝選擇排序如果數(shù)組完全亂序且交換代價高選擇排序可能更有優(yōu)勢。面試時給出這種“看場景”的回答比背結(jié)論要加分。4.3 個人踩坑記錄我自己早期學(xué)選擇排序時踩過一個很典型的坑為了省一個變量直接記錄“最小值”而不是“最小值下標”。每次內(nèi)層循環(huán)找到更小的值就更新min_value最后交換時才發(fā)現(xiàn)不知道它在哪里。代碼寫著寫著就變成“先找值再找下標”白白多寫了一次循環(huán)。后來我把教訓(xùn)總結(jié)成一句話排序算法里位置比數(shù)值重要。因為最終要做的是交換交換必須知道兩個位置。記錄最小值本身沒有任何問題但記錄下標才是能直接落地的信息。另一個坑是測試時只顧著看最終結(jié)果是否正確忽略了“排序穩(wěn)定性”這個指標。我寫完一個選擇排序版本后花了很長時間糾結(jié)“為什么我的結(jié)果和某個教程的不一樣”后來發(fā)現(xiàn)那個教程用的是穩(wěn)定版變種而我用的是普通版本。對相同輸入穩(wěn)定變種可能保持原始相對順序普通版本則不相同。所以說學(xué)算法不能只看“排沒排對”還要看“用了什么策略排的”。5. 還能擴展到哪里5.1 從選擇排序延伸出堆排序選擇排序最明顯的瓶頸是“線性掃描找最小值”。這需要 O(n) 時間導(dǎo)致總復(fù)雜度 O(n2)。如果有一個數(shù)據(jù)結(jié)構(gòu)能讓我們在 O(log n) 內(nèi)找到并移除最小值整體復(fù)雜度就會變成 O(n log n)。這個數(shù)據(jù)結(jié)構(gòu)就是二叉堆。堆排序的核心思路是先把數(shù)組構(gòu)建成最大堆然后反復(fù)把堆頂元素最大值與堆末尾元素交換縮小堆的范圍再堆化剩余元素。它的每一輪都是一個“選擇最大值”的過程和選擇排序完全同構(gòu)。理解了選擇排序再去看堆排序的“建堆”“堆化”“交換”三步操作理解成本會低很多。我經(jīng)常把選擇排序、堆排序放在一起學(xué)。先手寫選擇排序再手寫堆排序你會明顯感受到“數(shù)據(jù)結(jié)構(gòu)優(yōu)化算法”是一條多么自然的演化路徑。所謂“每日一算法”不一定每天學(xué)全新的內(nèi)容把新舊知識連起來反而記得更牢。5.2 每日一算法的正確打開方式我在帶新人時總結(jié)了一套“每日一算法”的實操方法選擇排序就是很好的試驗田。第一步先用紙筆畫一個小數(shù)組比如 6 個元素手動跑一遍排序流程把每輪的最小值和交換位置標出來。這一步不要省略它對建立空間感很重要。第二步不看任何資料直接手寫代碼。寫完后用隨機數(shù)組、空數(shù)組、單元素數(shù)組、全重復(fù)數(shù)組四組用例測一測。第三步把代碼貼進調(diào)試版本里打印每次交換后的數(shù)組和你紙上推演的結(jié)果對照。第四步給自己提三個問題這個算法穩(wěn)定嗎時間復(fù)雜度為什么是這個在什么場景下優(yōu)于別的排序如果每天堅持這個方法用不了兩周你的排序基礎(chǔ)就會非常扎實。不要貪多一天吃透一個算法比一天囫圇吞五個算法強得多。算法就像肌肉記憶訓(xùn)練量要夠但單次訓(xùn)練的“消化率”更重要。關(guān)于選擇排序最后我還想補一個小建議別只滿足于寫出“能跑的版本”。多想想幾個“如果”比如如果數(shù)組是逆序的怎么辦如果有大量重復(fù)元素怎么辦如果只能交換不能申請額外空間怎么辦。這些思考會讓你的每日一算法真正變成“每日一理解”而不是“每日一背代碼”。