選擇排序算法的Java實現¶
什麼是選擇排序？¶
選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的核心思想就像我們整理撲克牌：每次從一堆未排序的牌中，挑出最小（或最大）的那張，放到已經排好序的牌堆末尾。重複這個過程，直到所有牌都排好序。
選擇排序的基本思路¶
假設我們有一個數組 arr，需要將其從小到大排序。步驟如下：
1. 外層循環：遍歷數組的每一個位置 i（從0開始），這個位置表示“已排序部分的末尾”，接下來要確定第 i 個位置的元素。
2. 內層循環：在未排序部分（從 i+1 到數組末尾）中，找到最小元素的索引 minIndex。
3. 交換元素：將 i 位置的元素與 minIndex 位置的元素交換，此時 i 位置的元素已確定爲未排序部分的最小值。
4. 重複：外層循環繼續，直到所有元素都排好序。
Java代碼實現¶
下面是選擇排序的Java代碼，附帶詳細註釋：
public class SelectionSort {
// 選擇排序方法
public static void selectionSort(int[] arr) {
int n = arr.length; // 數組長度
// 外層循環：遍歷每一個需要確定的位置i（從0到n-1）
for (int i = 0; i < n - 1; i++) {
// 初始化最小值的索引爲當前位置i
int minIndex = i;
// 內層循環：在未排序部分（i+1到n-1）中找最小值
for (int j = i + 1; j < n; j++) {
// 如果當前元素arr[j]比minIndex位置的元素小，更新minIndex
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 將未排序部分的最小值與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};
System.out.println("排序前的數組：");
for (int num : arr) {
System.out.print(num + " ");
}
selectionSort(arr); // 調用選擇排序
System.out.println("\n排序後的數組：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
代碼詳解¶
-
外層循環：
for (int i = 0; i < n - 1; i++)
- 變量i表示“已排序部分的末尾位置”。當i = 0時，需要確定第0個位置的元素；當i = n-2時，只剩最後一個元素未排序，循環結束。 -
內層循環：
for (int j = i + 1; j < n; j++)
- 在內層循環中，從i+1開始遍歷到數組末尾，尋找未排序部分的最小值。 -
找最小值：
if (arr[j] < arr[minIndex]) { minIndex = j; }
- 變量minIndex始終記錄當前找到的最小值的索引。初始時假設i位置是最小值，若後續發現更小的元素，則更新minIndex。 -
交換元素：
temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;
- 將i位置的元素與未排序部分的最小值交換，此時i位置的元素已確定爲最小值，進入下一輪循環。
排序過程示例¶
以數組 {64, 25, 12, 22, 11} 爲例，逐步演示排序過程：
- 初始數組：
[64, 25, 12, 22, 11] - 第1輪（i=0）：內層循環找
[1,2,3,4]中的最小值。最小元素是11（索引4），交換後數組變爲[11, 25, 12, 22, 64]。 - 第2輪（i=1）：內層循環找
[2,3,4]中的最小值。最小元素是12（索引2），交換後數組變爲[11, 12, 25, 22, 64]。 - 第3輪（i=2）：內層循環找
[3,4]中的最小值。最小元素是22（索引3），交換後數組變爲[11, 12, 22, 25, 64]。 - 第4輪（i=3）：內層循環找
[4]中的最小值（只有64），無需交換，數組保持不變。
最終排序結果：[11, 12, 22, 25, 64]。
時間複雜度¶
選擇排序的時間複雜度爲 O(n²)（n爲數組長度）。無論數組初始狀態如何，內層循環都需要執行約n²/2次比較，因此適合小規模數據排序。
總結¶
選擇排序的核心是“每次選最小值”，通過交換元素逐步構建有序數組。它的邏輯簡單，代碼易實現，適合初學者理解排序算法的基礎思想。通過上述示例和代碼，相信你已經掌握了選擇排序的Java實現方法！