排序算法是計算機科學基石，也是面試高頻考點。本文系統梳理 8 種經典排序的核心思想、適用場景與 Java 實現要點，助你建立完整知識體系。
維護一個有序區間，每輪從無序區取出首個元素，在有序區中由後向前掃描找到插入位置，並將後續元素後移騰出空位。時間複雜度 O(n²)，最好情況（已有序）O(n)，穩定排序。
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}將數組按增量 gap 分組（初始 n/2），對每組進行直接插入排序；逐步縮小增量（gap/=2）至 1，最終完成整體排序。利用插入排序對近乎有序數組高效的特性，平均複雜度約 O(n^1.3)，不穩定。
常用序列：Shell 原始序列、Hibbard、Sedgewick、Ciura 序列，後者實測性能最優。
每輪從無序區選出最小元素，與無序區首位交換。雙重循環，比較次數固定 n(n-1)/2，交換次數最少（O(n)），時間複雜度 O(n²)，不穩定。
利用完全二叉樹堆特性：
① 建立大頂堆（父節點 ≥ 子節點）
② 將堆頂（最大值）與末尾元素交換，堆尺寸 -1
③ 對新堆頂執行 siftDown（下沉）恢復堆性質
④ 重複 ②③ 直到堆尺寸為 1
時間複雜度 O(n log n)，空間 O(1)，不穩定。關鍵點：建堆從最後一個非葉節點（(n-2)/2）開始下沉，而非從根節點。
public static void heapSort(int[] arr) {
// 1. 建堆
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
siftDown(arr, i, arr.length);
}
// 2. 依次取出堆頂
for (int end = arr.length - 1; end > 0; end--) {
swap(arr, 0, end);
siftDown(arr, 0, end);
}
}
private static void siftDown(int[] arr, int root, int heapSize) {
int val = arr[root];
for (int child = 2 * root + 1; child < heapSize; child = 2 * child + 1) {
if (child + 1 < heapSize && arr[child] < arr[child + 1]) child++;
if (val >= arr[child]) break;
arr[root] = arr[child];
root = child;
}
arr[root] = val;
}相鄰元素兩兩比較，大者後移（沉底），小者前移（冒頂）。每輪將當前最大值「冒泡」到未排序區末尾。可加入 swapped 標誌優化最好情況至 O(n)。穩定排序。
分治法：選基準值，一次掃描將數組分為 < pivot、≥ pivot 兩區，遞歸處理子區。平均 O(n log n)，最壞 O(n²)（有序數組），不穩定。
工程優化：三數取中法選基準、小區間改用插入排序、尾遞歸消除、隨機化基準防退化。
分治法：遞歸拆分至單元素，再合併兩個有序子陣列。時間複雜度穩定 O(n log n)，空間 O(n)，穩定排序。適用於鏈表、外部排序、求逆序對等場景。
private static void merge(int[] arr, int left, int mid, int right, int[] tmp) {
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; // <= 保證穩定性
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= right) tmp[k++] = arr[j++];
System.arraycopy(tmp, 0, arr, left, k);
}非比較排序：將整數統一位數（不足前導補 0），從最低位（LSD）到最高位（MSD）依次進行穩定計數排序。時間複雜度 O(d*(n+k))，d 為位數，k 為基數（通常 10 或 256）。要求：數據可映射為定長鍵值，且各位數範圍較小。
| 算法 | 平均時間 | 最壞時間 | 空間 | 穩定 | 適用場景 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | ✓ | 小規模、近乎有序 |
| 希爾排序 | O(n^1.3) | O(n²) | O(1) | ✗ | 中等規模、嵌入式環境 |
| 選擇排序 | O(n²) | O(n²) | O(1) | ✗ | 交換成本極高時 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ✗ | 實時系統、嵌入式、求 Top-K |
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✓ | 教學、極小數據 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ✗ | 通用內存排序首選 |
| 歸並排序 | O(n log n) | O(n log n) | O(n) | ✓ | 外部排序、鏈表、需穩定性 |
| 基數排序 | O(dn) | O(dn) | O(n+k) | ✓ | 大量整數、定長字符串、IP 排序 |
Arrays.sort()：基本類型用雙軸快速排序，對象數組用TimSort（歸並+插入混合），保證穩定Collections.sort()：委託 List.toArray() 後同 Arrays.sortArrays.parallelSort()：Fork/Join 框架並行歸並/快排，大數據顯著加速掌握排序算法不僅為應試，更是理解分治、隨機化、空間換時間、穩定性權衡等核心思想的最佳切入點。實際開發中優先使用標準庫，但在性能敏感、特殊數據分佈或受限環境下，手寫優化排序往往能帶來數量級提升。
