選擇排序與氣泡排序是入門級原地比較排序，雖時間複雜度均為 O(n²)，但交換次數與適應性不同。本文提供完整可運行代碼、核心邏輯解析與實測效能對比。
package com.db2;
public class Demo3 {
public static void main(String[] args) {
int[] arr = {3,1,8,2,9,100,33,22,11,18,14,17,15,3};
// selectSort(arr); // 選擇排序
bubbleSort(arr); // 氣泡排序
printArr(arr);
}
/** 選擇排序：每輪從未排序區選最小值，與首位交換 */
public static void selectSort(int[] arr) {
for (int x = 0; x < arr.length - 1; x++) {
for (int y = x + 1; y < arr.length; y++) {
if (arr[x] > arr[y]) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}
/** 氣泡排序：相鄰比較，大值逐步「冒泡」至末尾 */
public static void bubbleSort(int[] arr) {
for (int x = 0; x < arr.length - 1; x++) {
for (int y = 0; y < arr.length - x - 1; y++) {
if (arr[y] > arr[y + 1]) {
int temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
}
public static void printArr(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + (i != arr.length - 1 ? "," : "]\n"));
}
}
}
| 維度 | 選擇排序 | 氣泡排序 |
|---|---|---|
| 核心思想 | 每輪鎖定一個最小值位置 | 相鄰交換，大值後移 |
| 交換次數 | O(n) —— 每輪最多 1 次 | O(n²) —— 可能頻繁交換 |
| 最佳情況 | O(n²) —— 無提前結束機制 | O(n) —— 可加旗標檢測有序提前結束 |
| 穩定性 | 不穩定（交換可能改變相同元素相對序） | 穩定（僅交換嚴格大於） |
| 適應場景 | 寫入成本高（如 Flash 記憶體） | 近乎有序資料、教學示範 |
boolean swapped 標記，若某輪無交換直接跳出。Arrays.sort()（雙軸快排/TimSort），僅在教學、嵌入式極簡環境手寫 O(n²) 排序。理解基礎排序的機制與取捨，是演算法思維訓練的必經之路。
