Java 排序算法詳解：合併、冒泡、選擇、插入、快速排序原理與過程圖解

算法五大特徵

1. 有窮性：有限步驟結束
2. 確定性：每步驟定義明確
3. 輸入：0 或多個
4. 輸出：1 或多個
5. 可行性：原則上可人工執行

一、合併排序—— 分治法典範

核心思想

將陣列視為 N 個長度 1 的有序子序列，兩兩合併 → 長度 2/1 有序子序列 → 重複直到整個陣列有序。

過程示意（7 元素）

初始：  [49] [38] [65] [97] [76] [13] [27]
第1輪： [38 49] [65 97] [13 76] [27]
第2輪： [38 49 65 97] [13 27 76]
第3輪： [13 27 38 49 65 76 97]

複雜度

• 時間：O(N log N)（穩定）
• 空間：O(N)（需輔助陣列）
• 穩定排序

二、冒泡排序—— 逐步將最大值「浮」到末尾

單輪邏輯

for (int i = 0; i < n-1; i++)
    if (a[i] > a[i+1]) swap(a[i], a[i+1]);

每輪結束最大值固定在最後，下一輪範圍縮減 1。

複雜度

• 時間：O(N²)
• 空間：O(1)
• 穩定

三、選擇排序—— 每輪選最小值放前面

邏輯

for (int i = 0; i < n-1; i++) {
    int minIdx = i;
    for (int j = i+1; j < n; j++)
        if (a[j] < a[minIdx]) minIdx = j;
    swap(a[i], a[minIdx]);
}

複雜度

• 時間：O(N²)
• 空間：O(1)
• 不穩定（交換可能改變相等元素相對順序）

四、插入排序—— 將新元素插入已排序序列

邏輯

for (int i = 1; i < n; i++) {
    int key = a[i], j = i-1;
    while (j >= 0 && a[j] > key) {
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = key;
}

複雜度

• 時間：O(N²)（最佳 O(N) 已排序）
• 空間：O(1)
• 穩定、適合小規模/近乎有序資料

五、快速排序—— 冒泡改進版分治法

單輪分區（以首元素為基準）

int i = 0, j = n-1, pivot = a[0];
while (i < j) {
    while (i < j && a[j] >= pivot) j--;
    if (i < j) a[i++] = a[j];
    while (i < j && a[i] <= pivot) i++;
    if (i < j) a[j--] = a[i];
}
a[i] = pivot; // 基準歸位

遞歸處理左、右兩部分。

複雜度

• 時間：平均 O(N log N)，最壞 O(N²)（已排序陣列）
• 空間：O(log N) 遞歸棧
• 不穩定
• 實務常用隨機基準或三數取中避免最壞情況

六、總結對照表

七、實務建議

• 生產代碼直接用 Arrays.sort() / Collections.sort()（TimSort：合併+插入混合，O(N log N)、穩定）。
• 面試手寫重點：合併排序合併邏輯、快速排序分區邏輯、插入排序位移邏輯。
• 理解穩定性對業務影響（如先按部門再按薪資排序）。