目錄

1、選擇排序

1.1、介紹

1.2、穩定性

2、執行流程

3、java實現

4、優缺點

---

總結：Java 排序算法進階路線

1. O(n2) 算法（適合學習原理）

   • 冒泡排序（最慢）→ 選擇排序 →?插入排序（推薦先學）

2. O(n log n) 算法（實際應用）

   • 歸并排序（穩定）→ 快速排序（最快，但不穩定）→ 堆排序（空間省）

3. Java 內置排序

   • Arrays.sort()：對基本類型用?快速排序，對象類型用?歸并排序（保證穩定性）。

---

1、選擇排序

1.1、介紹

（Selection Sort）—— 比冒泡“聰明”一點。

每一次從未排序的數據中選出最小（或最大）的元素，放到已排序序列的末尾。

就像你有一堆亂序的書，每次從中挑出最薄的一本，放到書架上，直到所有書排好序。

1.2、穩定性

穩定排序要求：所有值相同的元素，排序后必須保持它們在原數組中的先后順序。

有這樣一個數組（用 A、B 標記兩個相同的 5，以便追蹤它們的位置）：

原始數組：[5A, 2, 3, 5B, 1]

目標是用?選擇排序?把它從小到大排序。

我們要關注的是：排序后，5A 和 5B 的相對順序是否保持不變？

如果保持?5A?在?5B?前面 → 穩定 ?
如果變成?5B?在?5A?前面 → 不穩定 ?

選擇排序的執行過程（逐輪分析）

?第 0 輪：在 [5A, 2, 3, 5B, 1] 中找最小值

• 從索引 0 到 4 遍歷，找出最小值是?1，它在索引 4。
• 把?1?和?5A（索引 0）交換：

交換前：[5A, 2, 3, 5B, 1]
交換后：[1, 2, 3, 5B, 5A]

關鍵來了：

• 原來的?5A?被換到了最后（索引 4）
• 原來的?5B?還在原地（索引 3）
  👉 所以現在：5B?在索引 3，5A?在索引 4 →?5B?在?5A?前面！

雖然它們的值都是 5，但?原來 5A 在前，現在 5B 在前，相對順序被改變了。

總結

冒泡排序是穩定的，（因為只在?>?時才交換，==?不動）。

? 選擇排序是不穩定的！

---

2、執行流程

如下圖所示：

1. 在數組?[0...n-1]?中找到最小元素，與第 0 個元素交換。
2. 在?[1...n-1]?中找到最小元素，與第 1 個元素交換。
3. 在?[2...n-1]?中找到最小元素，與第 2 個元素交換。
4. … 重復直到整個數組有序。

每一輪確定一個位置的最終值。

---

3、java實現

public class SelectionSort {/*** 選擇排序：升序* @param arr 待排序的整型數組*/public static void selectionSort(int[] arr) {// 邊界判斷if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 外層循環：控制排序的位置（0 ~ n-2）for (int i = 0; i < n - 1; i++) {int minIndex = i; // 假設當前位置就是最小值的索引// 內層循環：在未排序部分 [i+1, n-1] 中找真正的最小值for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 更新最小值的索引}}// 將找到的最小值與位置 i 的元素交換if (minIndex != i) {swap(arr, i, minIndex);}}}/*** 交換數組中兩個元素*/private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 測試方法public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11, 90};System.out.println("排序前：" + java.util.Arrays.toString(arr));selectionSort(arr);System.out.println("排序后：" + java.util.Arrays.toString(arr));}
}

輸出結果：

排序前：[64, 25, 12, 22, 11, 90]
排序后：[11, 12, 22, 25, 64, 90]

---

4、優缺點

🔍 和冒泡的區別：

• 冒泡：不斷交換，把最大值“冒”到最后。
• 選擇：每輪只記錄最小值的下標，最后只交換一次。

? 優點：

• 交換次數少（最多 n-1 次），適合寫操作代價高的場景（如寫入閃存）。

---

參考文章：

1、六大排序算法：插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序-CSDN博客文章瀏覽閱讀10w+次，點贊6.3k次，收藏3.4w次。本文詳細介紹了排序算法中的插入排序、希爾排序、選擇排序、冒泡排序、堆排序以及兩種快速排序方法（Hoare版本和挖坑法）。通過動圖演示和代碼實現，展示了這些算法的工作原理和時間復雜度，幫助讀者深入理解排序算法的內部機制。https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220faf03d22b2d125d5f49a4649ad59c85%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=0faf03d22b2d125d5f49a4649ad59c85&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v102^control&utm_term=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187