一、選擇排序的基本概念
選擇排序（Selection Sort）是一種簡單直觀的排序算法，其核心思想是每次從待排序元素中找到最值（最小值或最大值），將其放到已排序序列的末尾，重復此過程直到所有元素完成排序。
與冒泡排序通過相鄰元素交換逐步"浮"出最值不同，選擇排序通過"選擇"最值并一次性交換到目標位置，減少了交換操作的次數。這種特性使選擇排序在某些場景下（如交換成本較高的情況）表現優于冒泡排序。
二、選擇排序的工作原理
選擇排序的工作過程可分為以下步驟，我們以升序排序（找最小值）為例說明：
- 劃分區域：將數組分為"已排序區域"和"未排序區域"。初始狀態下，已排序區域為空，未排序區域為整個數組。
- 查找最值：在未排序區域中找到最小元素，記錄其索引。
- 交換元素：將找到的最小元素與未排序區域的第一個元素交換，此時該元素被納入已排序區域。
- 重復迭代：縮小未排序區域的范圍（左邊界右移一位），重復步驟2和3，直到未排序區域為空。
示例演示：
對數組 [64, 25, 12, 22, 11] 進行升序排序的過程：
- 第1輪：未排序區域為
[64, 25, 12, 22, 11]，最小值為11（索引4），與未排序區域第一個元素64交換 → 數組變為[11, 25, 12, 22, 64]（已排序區域：[11]）。 - 第2輪：未排序區域為
[25, 12, 22, 64]，最小值為12（索引2），與25交換 → 數組變為[11, 12, 25, 22, 64]（已排序區域：[11, 12]）。 - 第3輪：未排序區域為
[25, 22, 64]，最小值為22（索引3），與25交換 → 數組變為[11, 12, 22, 25, 64]（已排序區域：[11, 12, 22]）。 - 第4輪：未排序區域為
[25, 64]，最小值為25（索引3），無需交換 → 數組保持[11, 12, 22, 25, 64]（已排序區域：[11, 12, 22, 25]）。 - 結束：未排序區域僅剩最后一個元素64，排序完成。
三、算法特性分析
-
時間復雜度
選擇排序的時間復雜度不受輸入數據的影響，始終為 O(n2)：- 外層循環需要執行
n-1次（每次確定一個元素的位置）。 - 內層循環在第
i輪需要遍歷n-i個元素（尋找未排序區域的最值）。 - 總操作次數為
(n-1) + (n-2) + ... + 1 = n(n-1)/2，近似為n2/2，因此時間復雜度為 O(n2)。
- 外層循環需要執行
-
空間復雜度
選擇排序僅使用常數級別的額外空間（如存儲最值索引和臨時交換變量），因此空間復雜度為 O(1)，是一種"原地排序"算法。 -
穩定性
選擇排序是不穩定的排序算法。例如，對數組[2, 2, 1]排序時，第一個2會與1交換，導致兩個2的相對位置發生改變（原順序為[2?, 2?, 1]，排序后為[1, 2?, 2?]）。 -
優缺點
- 優點：實現簡單，空間復雜度低，交換操作次數少（最多
n-1次）。 - 缺點：時間復雜度高，不適合處理大規模數據；穩定性差，不適用于要求保持相等元素相對順序的場景。
- 優點：實現簡單，空間復雜度低，交換操作次數少（最多
四、C/C++代碼實現
下面是選擇排序的C++實現，包含完整的排序函數、測試用例和打印函數：
#include <iostream>
#include <vector>using namespace std;// 選擇排序函數（升序）
void selectionSort(int arr[], int n) {// 外層循環：控制已排序區域的邊界（0 ~ i-1為已排序）for (int i = 0; i < n - 1; i++) {int minIndex = i; // 記錄未排序區域中最小值的索引，初始假設為i// 內層循環：在未排序區域（i ~ n-1）中尋找最小值for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 更新最小值索引}}// 將找到的最小值與未排序區域的第一個元素（arr[i]）交換if (minIndex != i) { // 若最小值就是當前元素，無需交換int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}// 打印數組元素
void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;
}int main() {// 測試用例1：整數數組int arr1[] = {64, 25, 12, 22, 11};int n1 = sizeof(arr1) / sizeof(arr1[0]);cout << "排序前的數組：";printArray(arr1, n1);selectionSort(arr1, n1);cout << "排序后的數組：";printArray(arr1, n1);// 測試用例2：包含重復元素的數組int arr2[] = {3, 1, 4, 1, 5, 9, 2, 6};int n2 = sizeof(arr2) / sizeof(arr2[0]);cout << "\n排序前的數組（含重復元素）：";printArray(arr2, n2);selectionSort(arr2, n2);cout << "排序后的數組（含重復元素）：";printArray(arr2, n2);return 0;
}五、代碼解析
-
排序函數
selectionSort- 外層循環變量
i表示已排序區域的邊界（0 ~ i-1為已排序元素），循環范圍為0 ~ n-2（最后一個元素無需排序）。 - 內層循環從
i+1開始遍歷未排序區域，通過minIndex記錄最小值的位置。 - 找到最小值后，若其位置與
i不同，則交換arr[i]和arr[minIndex]，將最小值放入已排序區域的末尾。
- 外層循環變量
-
輔助函數
printArray
用于打印數組元素，方便觀察排序前后的變化。 -
測試用例
- 第一個測試用例驗證基本排序功能，第二個測試用例驗證對含重復元素數組的排序效果（可觀察到選擇排序的不穩定性）。
六、優化方向
標準選擇排序可通過以下方式優化：
-
雙向選擇排序
每次迭代同時尋找未排序區域的最小值和最大值，分別放到已排序區域的兩端，減少循環次數（迭代次數從n-1減少到n/2）。void bidirectionalSelectionSort(int arr[], int n) {int left = 0, right = n - 1;while (left < right) {int minIndex = left, maxIndex = right;// 找最小值和最大值for (int i = left; i <= right; i++) {if (arr[i] < arr[minIndex]) minIndex = i;if (arr[i] > arr[maxIndex]) maxIndex = i;}// 交換最小值到左側swap(arr[left], arr[minIndex]);// 若最大值在左側（被交換過），更新maxIndexif (maxIndex == left) maxIndex = minIndex;// 交換最大值到右側swap(arr[right], arr[maxIndex]);left++;right--;} } -
優化交換操作
對于大型元素（如結構體），交換操作成本較高，可先記錄最值位置，最后一次性移動元素（減少復制次數）。
七、適用場景
選擇排序適合以下場景：
- 數據量較小（如
n < 100），對排序效率要求不高。 - 內存空間有限，需要原地排序（空間復雜度O(1)）。
- 交換操作成本較高（選擇排序的交換次數最少）。
對于大規模數據（n > 1000），建議使用快速排序、歸并排序等O(n log n)級別的算法。
選擇排序是一種基礎的排序算法，其核心思想是"選擇最值并交換"，實現簡單但效率較低。
在實際開發中，需根據數據規模、空間限制和穩定性要求，選擇合適的排序算法。
