Java 冒泡排序法演算法詳解與優化實作

冒泡排序核心邏輯與程式碼實作

冒泡排序透過相鄰元素兩兩比較、交換，將最大（或最小）元素逐輪「冒泡」至序列末端。時間複雜度 O(n²)，適合教學與小規模資料。

逐輪演示過程

陣列：{2, 4, 9, 7, 6, 5}

• 第 1 輪：9 依次與 7、6、5 交換 → 2, 4, 7, 6, 5, 9
• 第 2 輪：7 與 6、5 交換 → 2, 4, 6, 5, 7, 9
• 第 3 輪：6 與 5 交換 → 2, 4, 5, 6, 7, 9（已有序）

優化版完整代碼

package com.test;

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] array = {2, 4, 9, 7, 6, 5};
        new BubbleSortTest().bubbleSort(array);
    }

    public int[] bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean swapped = false; // 優化旗標：若無交換提前結束
            
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // 若本輪無交換，代表已排序完成
            if (!swapped) break;

            // 觀察用輸出
            System.out.print("第 " + (i + 1) + " 趟排序: ");
            for (int k : array) System.out.print(k + " ");
            System.out.println();
        }
        return array;
    }
}

執行結果

第 1 趟排序: 2 4 7 6 5 9
第 2 趟排序: 2 4 6 5 7 9
第 3 趟排序: 2 4 5 6 7 9

複雜度與優化總結

進階變體：雞尾酒排序

雙向冒泡：奇數輪左→右冒最大值，偶數輪右→左冒最小值，減少來回移動次數，適合「海龜」（小值在右端）情況。

實務建議

• 生產環境排序請使用 Arrays.sort() (雙軸快速排序) 或 Collections.sort() (TimSort)，效能遠優於冒泡。
• 教學階段可作為演算法入門、循環不變式講解範例。
• 面試常考：手寫冒泡、快速排序、合併排序，並說明穩定性與複雜度。