Java 冒泡排序完整解析：邏輯優化演示、雙語言實作與進階優化技巧

冒泡排序核心思想

相鄰元素兩兩比較，大的「冒泡」到右側。每一輪將當前未排序區間的最大值移動到正確位置。

邏輯逐步優化演示

版本一：朴素雙層迴圈 (含越界與冗餘)

for (int x = 0; x < arr.length - 1; x++) {
    for (int y = 0; y < arr.length; y++) {
        if (arr[y] > arr[y + 1]) { /* 交換 */ }
    }
}
// 問題：y 到 length-1 時，y+1 越界；已排序區 (右側) 仍被掃描

版本二：內層排除已排序區

for (int x = 0; x < arr.length - 1; x++) {
    for (int y = 0; y < arr.length - x; y++) { // 每輪少掃一個
        if (arr[y] > arr[y + 1]) { /* 交換 */ }
    }
}
// 問題：y 到 length-x-1 時，y+1 仍越界

版本三：邊界修正 (最終標準形態)

for (int x = 0; x < arr.length - 1; x++) {
    for (int y = 0; y < arr.length - x - 1; y++) { // 確保 y+1 不越界
        if (arr[y] > arr[y + 1]) {
            int temp = arr[y];
            arr[y] = arr[y + 1];
            arr[y + 1] = temp;
        }
    }
}

完整可執行程式碼 (Java + PHP)

Java 版

public class BubbleSortDemo {
    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1};
        int[] sorted = bubbleSort(arr);
        System.out.print("排序結果: ");
        for (int n : sorted) System.out.print(n + " "); // 1 2 4 5
    }
    
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
}

PHP 版

<?php
class ArrayDemo {
    public static function main() {
        $arr = [2, 5, 4, 1];
        print_r(self::bubbleSort($arr)); 
        // Array ( [0] => 1 [1] => 2 [2] => 4 [3] => 5 )
    }
    
    public static function bubbleSort($arr) {
        for ($i = 0; $i < count($arr) - 1; $i++) {
            for ($j = 0; $j < count($arr) - $i - 1; $j++) {
                if ($arr[$j] > $arr[$j + 1]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j + 1];
                    $arr[$j + 1] = $temp;
                }
            }
        }
        return $arr;
    }
}
ArrayDemo::main();

進階優化：早期終止旗標

public static void bubbleSortOptimized(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean swapped = false; // 本輪是否發生交換
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // 本輪無交換，說明已有序，提前結束
    }
}

效果：最好情況 (已有序陣列) 時間複雜度從 O(n²) 降為 O(n)。

進階優化：記錄最後交換位置 (縮小掃描範圍)

public static void bubbleSortAdvanced(int[] arr) {
    int n = arr.length;
    while (n > 1) {
        int lastSwap = 0;
        for (int j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastSwap = j; // 記錄最後交換位置
            }
        }
        n = lastSwap + 1; // 下一輪只需掃描到最後交換位置
    }
}

效能特徵分析

選擇排序 vs 冒泡排序

希爾排序：本文提到的「最快」O(n²) 級改進演算法

public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

希爾排序是插入排序的分組改進版，平均時間複雜度約 O(n^1.3)~O(n^1.5)，是 O(n²) 級中效能最佳者，但仍不及 O(n log n) 的快排/歸併/堆排。

生產環境建議

• ✅ 學習演算法原理、理解邊界條件、迴圈不變式
• ✅ 極小資料 (n < 20) 且極度簡單場景
• ❌ 一般應用：Arrays.sort() (基本型別 Dual-Pivot Quicksort / 物件 TimSort)
• ❌ 大資料、高效能要求：選擇 O(n log n) 演算法