排序演算法詳解：氣泡排序法

氣泡排序演算法完整解析

氣泡排序是最基礎的排序演算法之一，透過相鄰元素比較交換，將最大值逐步「浮」至陣列末端。

演算法核心邏輯

1. 依序遍歷陣列
2. 每輪從頭開始比較相鄰元素
3. 若前者大於後者則交換
4. 每輪結束最大值會移至當前未排序區域最右端
5. 重複 n-1 輪完成排序

Java 實作程式碼

package com.robert.paixu;

public class BubbleSortAlgorithm {
    public static void main(String[] args) {
        int[] arrays = {1, 9, 2, 8, 3, 7, 4, 5, 0, 10, 18, 11};
        bubbleSort(arrays);
        display(arrays);
    }
    
    private static void bubbleSort(int[] arrays) {
        int temp = 0;
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 0; j < arrays.length - i - 1; j++) {
                if (arrays[j] > arrays[j + 1]) {
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
    }
    
    private static void display(int[] arrays) {
        for (int val : arrays)
            System.out.print(val + " ");
    }
}

執行流程圖解

初始: [1, 9, 2, 8, 3, 7, 4, 5, 0, 10, 18, 11]
第1輪: [1, 2, 8, 3, 7, 4, 5, 0, 9, 10, 11, 18]  ← 18 浮至最右
第2輪: [1, 2, 3, 7, 4, 5, 0, 8, 9, 10, 11, 18]  ← 11 就位
...
最終: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 18]

複雜度分析

優化版本：提前終止檢測

private static void bubbleSortOptimized(int[] arrays) {
    boolean swapped;
    for (int i = 0; i < arrays.length - 1; i++) {
        swapped = false;
        for (int j = 0; j < arrays.length - i - 1; j++) {
            if (arrays[j] > arrays[j + 1]) {
                swap(arrays, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break;  // 本輪無交換，已有序
    }
}

優化後最佳情況（已排序）時間複雜度降為 O(n)。

特性總結

• 穩定性：穩定排序（相等元素相對位置不變）
• 適用場景：教學示範、小規模資料、近乎有序資料（配合優化）
• 缺點：大量資料效能極差，實務極少直接使用

教學價值

雖實務價值有限，但氣泡排序是理解以下概念的絕佳入門：

1. 雙層迴圈控制排序輪數與比較範圍
2. 原地交換技巧
3. 演算法優化思維（提前終止旗標）
4. 時間複雜度分析基礎