目錄
從學生排隊開始
算法的初始狀態和核心操作
代碼的逐步完善
第一階段：定義函數框架和外層循環
第二階段：實現“尋找最小元素”的邏輯（內層循環）
第三階段：完成“交換”操作
復雜度與特性分析
時間復雜度 (Time Complexity)
空間復雜度 (Space Complexity)
穩定性 (Stability)
從學生排隊開始
我們已經探討了兩種排序思路：
-
冒泡排序：不斷比較相鄰的元素，像“本地微調”，慢慢把大的元素換到后面。
-
插入排序：始終維護一個有序的局部，然后把新元素插入進去。
現在我們思考一種完全不同的、更具“全局觀”的策略。想象一下，老師讓一隊學生按身高從矮到高排隊。老師會怎么做？
一種非常直接的方法是：
-
老師先掃視所有未排隊的學生，從中找出最矮的那一個。
-
然后指著隊伍的最前面說：“你，站到這里來。”
-
接著，老師在剩下的學生中，再掃視一遍，找出剩下人里最矮的。
-
然后指著隊伍的第二個位置說：“你，站到這里來。”
-
重復這個過程，直到所有學生都排好隊。
這個“每次選擇一個最值，放到它最終應該在的位置”的思路，就是選擇排序的靈魂。
算法的初始狀態和核心操作
和插入排序一樣，我們也將數組在邏輯上分為兩個部分：
左邊是已經排好序、元素都已在最終位置的有序區。
右邊是還未處理、元素位置都是臨時的無序區。
算法開始時，有序區是空的，整個數組都是無序區。
📌?核心操作（一輪迭代）：
-
在無序區中，通過一次完整的掃描，找到值最小的那個元素。
-
將這個最小的元素與無序區的第一個元素交換位置。
-
交換完成后，無序區的第一個元素就變成了有序區的最后一個元素。有序區長度加一，無序區長度減一。
我們來手動模擬一下。假設數組是 arr = [64, 25, 12, 22, 11]
-
有序區:
[] -
無序區:
[64, 25, 12, 22, 11]
1???第一輪 (i=0)：
-
掃描無序區
[64, 25, 12, 22, 11]。 -
發現最小的元素是
11，它的索引是4。 -
將
11與無序區的第一個元素64交換。
-
??結果：
[**11**, 25, 12, 22, 64]。現在11已經在它的最終位置了。 -
有序區:
[11], 無序區:[25, 12, 22, 64]
2???第二輪 (i=1)：
-
掃描無序區
[25, 12, 22, 64]。 -
發現最小的元素是
12，它的索引是2。 -
將
12與無序區的第一個元素25交換。
-
? 結果：
[11, **12**, 25, 22, 64]。現在12也歸位了。 -
有序區:
[11, 12], 無序區:[25, 22, 64]
這個過程持續
n-1輪，當n-1個元素都歸位后，剩下的最后一個元素自然也在正確的位置上了。
代碼的逐步完善
現在，我們將這個“選擇-交換”的策略翻譯成代碼。
第一階段：定義函數框架和外層循環
外層循環的職責是控制輪次，也就是每次為哪個位置尋找正確的元素。
i 將代表當前“坑位”的索引，我們要在無序區中找到元素來填這個“坑”。
#include <iostream>void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 選擇排序函數框架
void selectionSort(int arr[], int n) {// 外層循環控制輪次，i 是當前要放置正確元素的目標位置// 我們需要為 arr[0], arr[1], ..., arr[n-2] 依次尋找元素// 當 arr[n-2] 也正確時，arr[n-1] 必然也正確了for (int i = 0; i < n - 1; ++i) {// 在這里，我們將找到無序區 arr[i...n-1] 中的最小元素，// 然后把它放到 arr[i] 這個位置上。}
}第二階段：實現“尋找最小元素”的邏輯（內層循環）
在每一輪中，我們需要一個內層循環來掃描整個無序區，目的是找到最小元素的索引。
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {// 1. 先假設當前無序區的第一個元素就是最小的int min_idx = i;// 2. 用內層循環掃描無序區的其他元素for (int j = i + 1; j < n; ++j) {// 如果發現了更小的元素...if (arr[j] < arr[min_idx]) {// ...就更新最小元素的索引min_idx = j;}}// 當這個內層循環結束后，min_idx 就一定指向了// 整個無序區中最小元素的實際位置。// 接下來就是交換操作了。}
}第三階段：完成“交換”操作
找到了最小元素的索引 min_idx 后，我們只需要將它和當前輪次的目標位置 i 的元素進行一次交換。這個交換操作發生在內層循環結束之后。
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {std::cout << arr[i] << " ";}std::cout << std::endl;
}// 最終的選擇排序代碼
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {// 尋找 [i, n-1] 區間里的最小元素int min_idx = i;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 將找到的最小元素與 i 位置的元素交換swap(&arr[min_idx], &arr[i]);std::cout << "第 " << i + 1 << " 輪排序后: ";printArray(arr, n);}
}至此，一個從“全局選擇最優”這個第一性原理出發的選擇排序算法就清晰地構建完成了。
復雜度與特性分析
我們用之前建立的評判標準來分析它。
時間復雜度 (Time Complexity)
-
算法的主要耗時在于嵌套的循環。
-
外層循環執行
n-1次。 -
內層循環的執行次數：
-
當
i=0時，比較n-1次。 -
當
i=1時，比較n-2次。 -
...
-
當
i=n-2時，比較1次。
-
-
-
總的比較/移動次數大約是 1 + 2 + ... + (n?1) = n * (n?1) / 2。
?? 請注意，無論輸入的數組是已經有序、還是完全逆序，選擇排序的這個比較次數是固定不變的。
因為它必須完整地掃描完無序區，才能確認哪個是最小的。它無法像插入排序或優化后的冒泡排序那樣提前結束。
因此，選擇排序的最好、最壞和平均情況的時間復雜度都是：O(n^2)
空間復雜度 (Space Complexity)
-
在排序過程中，我們只使用了
i,j,min_idx這幾個輔助變量。 -
變量數量是固定的常數，不隨
n的增長而增長。 -
因此，空間復雜度是：O(1)
-
它也是一個原地排序 (In-place Sort) 算法。
穩定性 (Stability)
-
這是選擇排序一個非常重要的特性。我們來舉個例子判斷一下。
-
假設數組是
[5a, 8, 5b, 2](這里5a和5b值相等，但我們為了區分，加上了標記)。 -
第一輪 (i=0)：
-
掃描整個數組，發現最小元素是
2。 -
將
2與無序區的第一個元素arr[0](也就是5a) 進行交換。 -
交換后，數組變為
[2, 8, 5b, 5a]。
-
-
觀察結果：在原始數組中，
5a在5b的前面。但在第一輪排序后，5a跑到了5b的后面。它們的相對位置發生了改變。 -
僅僅一個反例就足以證明，選擇排序不是一個穩定的排序算法。
-
因此，選擇排序是?不穩定排序 (Unstable Sort)。
選擇排序的特點非常鮮明：它的時間復雜度很“死板”，不受輸入數據的影響，始終是 O(n^2)。
但它有一個優點，就是數據交換的次數非常少，最多只有 n-1 次。在一些“寫”操作遠比“讀”操作昂貴的場景下，這可能成為一個考慮因素。
