選擇排序算法需綜合考量四大指標：
| 指標 | 說明 | 關鍵點 |
|---|---|---|
| 時間複雜度 | 平均/最好/最壞情況 | O(n²) vs O(n log n) |
| 空間複雜度 | 額外內存消耗 | 原地排序 O(1) vs 輔助數組 O(n) |
| 穩定性 | 相等元素相對順序是否保持 | 穩定：冒泡/插入/歸並；不穩定：選擇/快排/堆排 |
| 常數因子 | 同階複雜度下的實際速度差 | 快排常數小於堆排，工程中常優選 |
核心思想：相鄰比較，大元素沉底，每輪冒泡出一個最大值
// 優化：有序標記提前終止
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean sorted = true;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
sorted = false;
}
}
if (sorted) break; // 本輪無交換，已有序
}
}特點：穩定、原地、最好 O(n)、最壞 O(n²)
核心思想：每輪在無序區選最小值，與無序區首位交換
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx != i) swap(arr, i, minIdx);
}
}特點：不穩定、原地、交換次數最少 (O(n))、無論輸入如何皆 O(n²)
核心思想：構建有序區，將新元素插入合適位置（類似整理撲克牌）
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}特點：穩定、原地、近乎有序數據極快 O(n)、小數據量優於 O(n log n) 算法
核心思想：分組插入排序，間距 d 逐漸縮小至 1，減少元素移動距離
public static void shellSort(int[] arr) {
for (int d = arr.length / 2; d > 0; d /= 2) {
for (int i = d; i < arr.length; i++) {
int temp = arr[i], j = i - d;
while (j >= 0 && arr[j] > temp) {
arr[j + d] = arr[j];
j -= d;
}
arr[j + d] = temp;
}
}
}特點：不穩定、原地、時間複雜度取決於間距序列 (約 O(n^1.3~1.5))
核心思想：分治法，選基準值分區，左小右大，遞歸排序子區間
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int i = low, j = high, pivot = arr[low];
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
swap(arr, i, j);
}
swap(arr, low, i); // 基準歸位
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}關鍵優化：隨機選基準/三數取中、小區間改插入排序、尾遞歸優化、三向切分處理大量重複元素
特點：不穩定、原地、平均 O(n log n)、最壞 O(n²)（可通過隨機化避免）
核心思想：分治法，遞歸拆分至單元素，歸併時有序合併
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) >>> 1;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int l, int m, int r) {
int[] temp = new int[r - l + 1];
int i = l, j = m + 1, k = 0;
while (i <= m && j <= r) temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
while (i <= m) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, l, temp.length);
}特點：穩定、需 O(n) 輔助空間、鏈表上可 O(1) 空間、時間複雜度固定 O(n log n)
核心思想：構建大頂堆，反復交換堆頂與末尾元素，調整堆
public static void heapSort(int[] arr) {
// 構建大頂堆
for (int i = arr.length / 2 - 1; i >= 0; i--) heapify(arr, i, arr.length);
// 依次取出堆頂
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i);
}
}
private static void heapify(int[] arr, int i, int size) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, size);
}
}特點：不穩定、原地、時間複雜度固定 O(n log n)、常數因子較大
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + ((right - left) >>> 1);
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}前提：數組必須有序；複雜度：O(log n)；變體：查找首次/最後一次出現位置、查找插入位置
排序算法是演算法設計的縮影，理解其分治、隨機化、空間換時間等思想，對解決複雜工程問題大有裨益。實際開發中優先使用 Arrays.sort() (雙軸快排) 或 Collections.sort() (TimSort)，僅在特殊場景手寫優化。
