《Hello 算法》選擇排序（Selection Sort）深度解析：原理、PythonTutor 視覺化與 13 種語言實作

• 教程
• 文档
• 示例工程
• 教育

本篇技術指南以 hello-algo 倉庫中的選擇排序（selection sort）教學內容為主體，系統講解其「每輪從未排序區間挑出最小元素」的核心思想、完整演算法流程、時間/空間複雜度與非穩定特性，並結合倉庫提供的 PythonTutor 視覺化檔案與 13 種程式語言的實作原始碼，讓讀者既能看懂原理，也能直接跑通程式碼、對照驗證。

選擇排序的核心思想與演算法流程

選擇排序（selection sort）的工作原理非常簡單：開啟一個迴圈，每輪從未排序區間選擇最小的元素，將其放到已排序區間的末尾。設陣列的長度為 $n$，其完整流程如下：

1. 初始狀態：所有元素未排序，即未排序（索引）區間為 $[0, n-1]$。
2. 第一輪：選取區間 $[0, n-1]$ 中的最小元素，將其與索引 $0$ 處的元素交換。完成後，陣列前 1 個元素已排序。
3. 第二輪：選取區間 $[1, n-1]$ 中的最小元素，將其與索引 $1$ 處的元素交換。完成後，陣列前 2 個元素已排序。
4. 以此類推：經過 $n - 1$ 輪選擇與交換後，陣列前 $n - 1$ 個元素已排序。
5. 收尾：僅剩的一個元素必定是最大元素，無須排序，因此陣列排序完成。

從流程可以看出，選擇排序的關鍵在於「未排序區間」的邊界逐步右移：每完成一輪，已排序區間就多一個元素，未排序區間則縮短一個元素。整個過程在原始碼中表現為「外迴圈控制輪數、內迴圈掃描最小元素」，如下圖所示：

在程式碼中，演算法用 $k$ 來記錄未排序區間內最小元素的索引，其對應的完整 Python 實作位於 zh-hant/codes/python/chapter_sorting/selection_sort.py，內容如下：

"""選擇排序""" def selection_sort(nums: list[int]): n = len(nums) # 外迴圈：未排序區間為 [i, n-1] for i in range(n - 1): # 內迴圈：找到未排序區間內的最小元素 k = i for j in range(i + 1, n): if nums[j] < nums[k]: k = j # 記錄最小元素的索引 # 將該最小元素與未排序區間的首個元素交換 nums[i], nums[k] = nums[k], nums[i] """Driver Code""" if __name__ == "__main__": nums = [4, 1, 3, 1, 5, 2] selection_sort(nums) print("選擇排序完成後 nums =", nums)

逐段解讀核心邏輯

• 外迴圈for i in range(n - 1)：i 從 0 遞增到 n-2，共 $n-1$ 輪。每輪開始前，區間 $[0, i-1]$ 已排序，未排序區間為 $[i, n-1]$。
• 內迴圈與k的更新：先令k = i，再讓j從i + 1掃描到n - 1，一旦發現nums[j] < nums[k]就更新k = j。注意比較用的是嚴格小於（<），因此遇到相等元素時k不會更新——這也正是非穩定性的來源之一（下文會詳細說明）。
• 交換：nums[i], nums[k] = nums[k], nums[i]將當前輪最小元素放到未排序區間首部，Python 的多重賦值語法讓交換一目瞭然。
• Driver Code 驗證：以nums = [4, 1, 3, 1, 5, 2]為輸入（刻意包含重複元素 1，用於觀察穩定性），排序完成後輸出選擇排序完成後 nums = [1, 1, 2, 3, 4, 5]。

PythonTutor 視覺化：逐步觀察變數變化

hello-algo 在 zh-hant/codes/pythontutor/chapter_sorting/selection_sort.md 提供了本程式碼對應的 PythonTutor 互動式逐步執行連結。將上述 Python 程式碼在瀏覽器中逐行執行時，可以即時觀察到：

• 每一輪外迴圈中i的取值與未排序區間邊界的移動；
• 內迴圈中k如何被j的掃描結果逐步更新（最小元素索引的「追蹤」過程）；
• 交換前後nums陣列的完整狀態變化。

對於初學者而言，這比單看靜態程式碼更能直觀理解「為什麼內迴圈結束後k就是最小元素的索引」這一關鍵細節。

演算法特性分析

時間複雜度為 $O(n^2)$、非自適應排序

外迴圈共 $n - 1$ 輪，第一輪內迴圈執行 $n - 1$ 次，最後一輪執行 $1$ 次，即各輪內迴圈分別執行 $n-1$、$n-2$、$\dots$、$2$、$1$ 次，求和為 $\frac{n(n-1)}{2}$。無論輸入陣列原本是否接近有序，內迴圈都必須完整掃描未排序區間才能確定最小元素，比較次數恆定，因此選擇排序是非自適應排序——輸入資料的有序程度不會影響其執行時間。不過它的交換次數很少，每輪最多 1 次、總共 $n-1$ 次，這一特性使它在「交換代價遠高於比較代價」的場景下具有相對優勢。

空間複雜度為 $O(1)$、原地排序

演算法僅使用指標i、j、k等常數大小的額外空間，所有交換都在原陣列上進行，屬於原地排序，無需額外陣列。

非穩定排序

選擇排序是非穩定排序：元素nums[i]有可能被交換至與其相等的元素的右邊，導致兩者的相對順序發生改變。其根源在於交換操作跨越了「中間」的元素——當未排序區間中存在與nums[i]相等、且更靠後的值，同時最小元素又位於更後方時，一次交換就可能把後方的相等元素「搬」到前方相等元素的前面。下圖給出了非穩定性的直觀示例：

這一特性決定了：當排序對象是包含多個相同鍵值、且需要保留其原有相對次序的資料（例如先按主鍵、再按次鍵排序的多欄位記錄）時，選擇排序並不適用，此時應改用穩定排序演算法。

13 種語言的實作對照與執行方式

hello-algo 的特色之一是「一鍵執行」的多語言程式碼庫，選擇排序在所有主流語言中均有完整實作，原始碼分佈於以下路徑：

各語言的核心邏輯完全一致（外迴圈 + 內迴圈找最小索引 + 交換），差異主要體現在語言自身的交換寫法上，從中可以觀察到不同語言的語法特色：

• C 語言使用臨時變數完成交換，且需手動傳入陣列長度n（見 selection_sort.c）：

void selectionSort(int nums[], int n) { for (int i = 0; i < n - 1; i++) { int k = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[k]) k = j; } int temp = nums[i]; nums[i] = nums[k]; nums[k] = temp; } }

• C++直接呼叫標準函式庫的swap(nums[i], nums[k])；Java / Kotlin / Dart / C則採用「臨時變數」三段式交換。
• Python / Go / Ruby使用多重賦值nums[i], nums[k] = nums[k], nums[i]一氣呵成；JavaScript / TypeScript使用解構賦值[nums[i], nums[k]] = [nums[k], nums[i]]；C#使用元組交換(nums[k], nums[i]) = (nums[i], nums[k])。
• Rust以&mut [i32]切片傳參、用nums.swap(i, k)內建方法交換，並在函式入口對空陣列做了防護處理（見 selection_sort.rs）：

fn selection_sort(nums: &mut [i32]) { if nums.is_empty() { return; } let n = nums.len(); for i in 0..n - 1 { let mut k = i; for j in i + 1..n { if nums[j] < nums[k] { k = j; } } nums.swap(i, k); } }

• Swift使用inout參數與nums.swapAt(i, k)；每個語言的main/Driver Code區塊都內建了[4, 1, 3, 1, 5, 2]的相同測試輸入與「選擇排序完成後 nums = [1, 1, 2, 3, 4, 5]」的驗證輸出，讀者可以直接編譯執行對照結果。

總結與適用場景

選擇排序是理解「選擇類」演算法的最佳入門案例：它思想直白、實現簡單、原地排序、交換次數少，適合資料量較小或交換成本昂貴的場景；但由於時間複雜度恆為 $O(n^2)$ 且不穩定，在大型資料集上表現遜於 $O(n \log n)$ 的進階排序演算法。完整圖文說明可見 zh-hant/docs/chapter_sorting/selection_sort.md，配合倉庫中的 PythonTutor 視覺化檔案（zh-hant/codes/pythontutor/chapter_sorting/selection_sort.md）與上述多語言程式碼逐行執行、對照學習，即可徹底掌握選擇排序的原理、實現與特性邊界。

• 教程
• 文档
• 示例工程
• 教育