一、算法基礎

1.1 什么是選擇排序

選擇排序是一種簡單直觀的排序算法，它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再從剩余未排序元素中繼續尋找最小（或最大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

1.2 選擇排序的基本思想

選擇排序的核心思想是：

• 將輸入數據分為已排序區域和未排序區域
• 不斷從未排序區域選擇最小元素，放入已排序區域的末尾
• 重復上述過程直到全部排序完成

1.3 時間復雜度

選擇排序的時間復雜度分析如下：

• 最好情況時間復雜度：O(n2)
• 最壞情況時間復雜度：O(n2)
• 平均時間復雜度：O(n2)

無論輸入數據是否已經部分排序，選擇排序始終需要進行 n(n-1)/2 次比較，因此其時間復雜度總是 O(n2)。

1.4 空間復雜度

選擇排序是一種原地排序算法，它只需要一個用于交換的臨時變量，因此空間復雜度為 O(1)。

二、Java實現

2.1 基礎實現

public class SelectionSort {public static void selectionSort(int[] arr) {int n = arr.length;// 外層循環控制已排序區域的邊界for (int i = 0; i < n - 1; i++) {// 找出未排序區域中的最小值索引int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 將找到的最小值與未排序區域的第一個元素交換if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}// 測試代碼public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};selectionSort(arr);System.out.println("排序后的數組：");for (int i : arr) {System.out.print(i + " ");}}
}

2.2 算法步驟解析

1. 初始狀態：整個數組視為未排序區域
2. 第一次迭代：
   • 在整個數組中找到最小元素
   • 將其與數組第一個元素交換位置
   • 數組第一個元素現在位于正確位置
3. 第二次迭代：
   • 從第二個元素開始，在剩余未排序元素中找到最小值
   • 將其與數組第二個元素交換位置
4. 重復過程：繼續執行，直到所有元素都排序完畢

三、選擇排序的特點

3.1 優點

• 實現簡單，易于理解和編碼
• 交換次數少：每次內循環只需要進行一次交換操作，最多進行 n-1 次交換
• 原地排序：不需要額外的存儲空間
• 穩定性可控：可以實現為穩定排序算法（通過特定實現方式）

3.2 缺點

• 時間效率低：無論輸入如何，時間復雜度始終為 O(n2)
• 不適合大規模數據：當數據量大時，性能顯著下降
• 不會提前終止：即使數組已經排序，算法仍會執行完所有步驟

四、算法優化方案

4.1 雙向選擇排序

雙向選擇排序在每次迭代中同時查找最小值和最大值，減少了循環次數：

public static void bidirectionalSelectionSort(int[] arr) {int left = 0;int right = arr.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;// 找出最小值和最大值for (int i = left + 1; i <= right; i++) {if (arr[i] < arr[minIndex]) {minIndex = i;}if (arr[i] > arr[maxIndex]) {maxIndex = i;}}// 將最小值放到左邊if (minIndex != left) {int temp = arr[left];arr[left] = arr[minIndex];arr[minIndex] = temp;// 如果最大值是left，那么交換后最大值位置變為minIndexif (maxIndex == left) {maxIndex = minIndex;}}// 將最大值放到右邊if (maxIndex != right) {int temp = arr[right];arr[right] = arr[maxIndex];arr[maxIndex] = temp;}left++;right--;}
}

4.2 使用堆數據結構

可以使用最小堆來優化選擇排序：

1. 構建一個最小堆 O(n)
2. 依次取出堆頂元素 O(log n)

這種方法實際上就是堆排序，時間復雜度降低到 O(n log n)。

五、實例分析

5.1 示例數組排序過程

以數組 [64, 25, 12, 22, 11] 為例：

1. 第一次迭代：
   • 找到最小值 11（索引 4）
   • 交換11和64：[11, 25, 12, 22, 64]
   • 已排序：[11]，未排序：[25, 12, 22, 64]
2. 第二次迭代：
   • 在剩余部分找到最小值 12（索引 2）
   • 交換12和25：[11, 12, 25, 22, 64]
   • 已排序：[11, 12]，未排序：[25, 22, 64]
3. 第三次迭代：
   • 在剩余部分找到最小值 22（索引 3）
   • 交換22和25：[11, 12, 22, 25, 64]
   • 已排序：[11, 12, 22]，未排序：[25, 64]
4. 第四次迭代：
   • 在剩余部分找到最小值 25（索引 3）
   • 不需要交換（已在正確位置）
   • 已排序：[11, 12, 22, 25]，未排序：[64]
5. 排序完成：[11, 12, 22, 25, 64]

5.2 性能分析

對比不同輸入規模的性能表現：

• 小規模數據（n ≤ 50）：選擇排序性能可接受
• 中等規模數據（50 < n ≤ 1000）：性能明顯下降
• 大規模數據（n > 1000）：性能嚴重下降，不推薦使用

六、應用場景

6.1 適用場景

• 小規模數據排序：當數據量較小時，選擇排序簡單易實現
• 對交換操作敏感的場景：選擇排序的交換次數最多為 n-1 次
• 輔助教學：作為排序算法的基礎教學示例
• 內存受限的嵌入式系統：實現簡單且空間復雜度低

6.2 不適用場景

• 大規模數據排序：性能太低，應選擇更高效的算法
• 幾乎已排序的數據：選擇排序無法利用數據的部分有序性

七、總結

選擇排序是一種簡單直觀的排序算法，核心思想是不斷從未排序區域中選擇最小元素放入已排序區域。

核心要點：

• 時間復雜度始終為 O(n2)，無論輸入如何
• 空間復雜度為 O(1)，是一種原地排序算法
• 交換次數較少，最多進行 n-1 次交換
• 實現簡單，代碼易于理解和編寫
• 對于大型數據集不推薦使用

選擇排序雖然不是最高效的排序算法，但它的簡單性和低空間復雜度使其在特定場景下仍有價值。對于編程初學者來說，理解選擇排序有助于掌握排序算法的基本概念及其實現方法。