排序演算法是電腦科學中最基礎也最核心的課題之一。無論是面試、競賽還是實務開發，熟練掌握主流排序的原理、優缺點與適用場景，都是工程師的基本功。本文系統整理八大經典排序演算法，包含關係圖譜、核心邏輯、動態演示概念與完整 Java 程式碼，助你建立完整的排序知識體系。
從穩定性、時間複雜度、空間複雜度等維度切入，可將八大排序分為兩大陣營：
核心思想：將陣列分為「已排序區」與「未排序區」，每次從未排序區取出首個元素，在已排序區中由後向前掃描，找到插入位置並位移元素。
特性：穩定排序、最佳 O(n)、最差 O(n²)、空間 O(1)。適合資料量小或近乎有序的情境。
public class InsertSort {
public void sort(int[] a) {
for (int i = 1; i < a.length; i++) {
int temp = a[i];
int j = i - 1;
for (; j >= 0 && temp < a[j]; j--) {
a[j + 1] = a[j]; // 後移
}
a[j + 1] = temp; // 插入
}
}
}
核心思想：插入排序的改進版。先按增量 d (通常為 n/2) 分組進行插入排序，逐步縮小增量至 1，使陣列趨近有序，最後一次插入排序極快。
特性：不穩定、時間複雜度介於 O(n^1.3)~O(n²)、空間 O(1)。中等資料量表現優異。
核心思想：每輪從未排序區選出最小值，與未排序區首位交換。雖然比較次數固定，但交換次數極少 (O(n))。
特性：不穩定、固定 O(n²)、空間 O(1)。適合交換成本極高的場景。
核心思想：利用「大頂堆」特性。先建堆 (O(n))，再重複「交換堆頂與末尾元素 + 向下調整堆」n-1 次。
特性：不穩定、固定 O(n log n)、空間 O(1)。保證最差情況效能，適合即時系統。
核心思想：相鄰元素兩兩比較，大的「沉底」、小的「冒頂」。每輪將當前最大值推至末尾。可加旗標優化：若某輪無交換則提前結束。
特性：穩定、最佳 O(n)、最差 O(n²)、空間 O(1)。教學價值大於實務價值。
核心思想：分治法典範。選取基準值，一趟掃描將陣列分為「小於基準」與「大於等於基準」兩區，基準歸位，遞迴處理子區。
特性：不穩定、平均 O(n log n)、最差 O(n²)、空間 O(log n)。實務中最快的通用排序，JDK `Arrays.sort()` 基礎型別即採用雙軸快排。
核心思想：分治法。遞迴拆解至單元素，再兩兩合併有序子陣列。需額外 O(n) 空間作為暫存陣列。
特性：穩定、固定 O(n log n)、空間 O(n)。JDK `Arrays.sort()` 物件型別採用 TimSort (合併排序變體)，正是看中其穩定性。
核心思想：非比較排序。將整數統一位數 (不足補 0)，從最低位 (LSD) 到最高位，依序進行穩定的計數/桶排序。
特性：穩定、時間 O(d·n) (d 為位數)、空間 O(n+k)。適合大量整數、範圍已知的場景，效能極強。
| 演算法 | 平均時間 | 最差時間 | 空間 | 穩定性 | 推薦場景 |
|---|---|---|---|---|---|
| 插入排序 | 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) | 不穩定 | 即時系統/保證最差效能 |
| 氣泡排序 | 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(d·n) | O(d·n) | O(n+k) | 穩定 | 大量整數/固定位數/極致效能 |
掌握這八大排序，不僅能應付面試白板題，更能在面對海量資料、記憶體限制、穩定性需求等真實工程挑戰時，做出最優的技術決策。
