Java 冒泡排序算法原理與實現詳解

冒泡排序是最經典的入門排序算法，雖然時間復雜度為 O(n²)，不適合大數據量場景，但其思路直觀、代碼簡潔，是理解排序核心思想、掌握雙重循環控制的最佳切入點。本文深度解析其原理、代碼實現與優化方向。

一、算法核心思想

像氣泡上浮一樣，通過相鄰元素兩兩比較，將大（或小）元素逐步「冒泡」到數組末端。

• 每輪比較 n-1、n-2、...、1 次
• 總比較次數：(n-1)+(n-2)+...+1 = n(n-1)/2
• 時間復雜度：O(n²)
• 空間復雜度：O(1)（原地排序）
• 穩定性：穩定（相等元素不交換位置）

二、標準實現代碼

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {56, 15, 10, 69, 1, 21, 6, 85, 30, 45, 73, 93};

        // 冒泡排序：升序
        for (int i = 0; i < array.length; i++) {
            // 優化點：每輪結束後，最後 i 個元素已有序，無需比較
            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;
                }
            }
        }

        System.out.print("排序結果: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
        // 輸出: 1 6 10 15 21 30 45 56 69 73 85 93
    }
}

三、關鍵細節解析

四、優化版：早期退出

若某輪無任何交換，說明數組已有序，可提前結束。

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 - 1 - i; 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)。

五、進階優化：雞尾酒排序

雙向冒泡：正向冒泡最大值到右端，反向冒泡最小值到左端，減少無效比較。適合「基本有序、少量逆序」的數據。

六、何時使用冒泡排序？

• 教學演示、面試基礎考察
• 極小數據量（n < 50）
• 數據基本有序（配合優化版）
• 嵌入式環境、極度受限內存（O(1) 空間）

生產環境大數據排序請使用：Arrays.sort()（雙軸快排/TimSort）、Collections.sort()、或專用庫（如 Parallel Sort）。

冒泡排序雖簡單，但蘊含「雙指針遍歷、原地交換、有序區擴展」等核心編程模式。徹底掌握它，為學習快排、歸併、堆排打下堅實基礎。