什麼是選擇排序？¶
選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的核心思想是：每一次從待排序的元素中選出最小（或最大）的一個元素，將其放到已排序序列的末尾，直到所有元素都排序完成。
舉個生活中的例子：假設你要整理一堆雜亂的撲克牌，每次從剩下的牌中找出最小的那張，放到最左邊，直到所有牌都排好序。
選擇排序的基本思路¶
- 外層循環：控制當前需要排序的起始位置（例如第i個位置，i從0開始）。
- 內層循環：在剩餘未排序的元素中（從i到數組末尾），找到最小元素的位置。
- 交換操作：將找到的最小元素與當前起始位置的元素交換，確保最小元素被放到正確的位置。
- 重複步驟：直到外層循環結束，所有元素排序完成。
步驟分析¶
以數組 arr = {64, 25, 12, 22, 11} 爲例：
1. 初始狀態：未排序部分爲整個數組，已排序部分爲空。
2. 第一次外層循環（i=0）：
- 內層循環從 j=1 到 4，找到最小值 11，位置在 4。
- 交換 arr[0] 和 arr[4]，數組變爲 {11, 25, 12, 22, 64}。此時第0位已排好。
3. 第二次外層循環（i=1）：
- 內層循環從 j=2 到 4，找到最小值 12，位置在 2。
- 交換 arr[1] 和 arr[2]，數組變爲 {11, 12, 25, 22, 64}。此時第1位已排好。
4. 第三次外層循環（i=2）：
- 內層循環從 j=3 到 4，找到最小值 22，位置在 3。
- 交換 arr[2] 和 arr[3]，數組變爲 {11, 12, 22, 25, 64}。此時第2位已排好。
5. 第四次外層循環（i=3）：
- 內層循環從 j=4 到 4，最小值是 25（位置3），無需交換。
6. 結束：數組已完全排序。
C++代碼實現¶
#include <iostream>
using namespace std;
// 選擇排序函數：對數組arr進行排序，n爲數組長度
void selectionSort(int arr[], int n) {
// 外層循環：控制當前需要放置最小值的位置（i從0到n-2，最後一個元素無需排序）
for (int i = 0; i < n - 1; i++) {
// 初始假設第i個元素是最小值
int minIndex = i;
// 內層循環：在剩餘元素中找到最小值的位置
for (int j = i + 1; j < n; j++) {
// 如果當前元素比minIndex位置的元素小，更新minIndex
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交換當前i位置元素與最小值元素
// 如果minIndex == i，交換後數組不變（無影響）
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 主函數：測試選擇排序
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]); // 計算數組長度
// 輸出排序前的數組
cout << "排序前的數組：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 調用選擇排序函數
selectionSort(arr, n);
// 輸出排序後的數組
cout << "排序後的數組：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
代碼解釋¶
- 外層循環：
i從0到n-2（因爲最後一個元素無需排序），表示當前要放置最小值的位置。 - 內層循環：
j從i+1開始遍歷剩餘元素，找到最小值的索引minIndex。 - 交換操作：通過臨時變量
temp交換arr[i]和arr[minIndex]，確保最小值被放到第i個位置。 - 時間複雜度：兩層循環，時間複雜度爲 O(n²)（n爲數組長度），空間複雜度爲 O(1)（僅用臨時變量交換）。
運行結果¶
排序前的數組：64 25 12 22 11
排序後的數組：11 12 22 25 64
總結¶
選擇排序的核心是每次找到最小值並交換，適合小規模數據排序。雖然時間複雜度較高，但實現簡單，無需額外空間，是理解排序算法的基礎之一。初學者可以通過手動模擬排序過程（如上面的例子）加深對算法邏輯的理解。