Java 冒泡排序演算法完整實作與優化版本

基本版

public static void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) swap(a, j, j + 1);
        }
    }
}

private static void swap(int[] a, int i, int j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

優化版：提早結束旗標

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

進階優化：記錄最後交換位置

public static void bubbleSortAdvanced(int[] a) {
    int n = a.length;
    int lastSwap = n - 1;
    while (lastSwap > 0) {
        int currentSwap = 0;
        for (int j = 0; j < lastSwap; j++) {
            if (a[j] > a[j + 1]) { swap(a, j, j + 1); currentSwap = j; }
        }
        lastSwap = currentSwap;  // 之後區段已有序
    }
}

複雜度分析

教學用途提醒

冒泡排序僅適合教學示意，實務專案嚴禁用於大量資料。
生產環境請直接使用 Arrays.sort()（雙軸快排/TimSort）或 Collections.sort()。

測試主程式

public static void main(String[] args) {
    int[] data = {4, 2, 1, 8, 9, 4, 2};
    bubbleSortOptimized(data);
    System.out.println(Arrays.toString(data));  // [1, 2, 2, 4, 4, 8, 9]
}