Java 冒泡排序算法詳解與代碼實現

冒泡排序簡介

冒泡排序是一種基礎的排序算法，其核心思想是重複遍歷待排序的數列，比較相鄰的兩個元素，若順序錯誤則交換它們。這個過程就像氣泡從水底向上浮升一樣，較大的元素會逐漸「冒泡」到數列末端，因此得名。

算法特點

• 時間複雜度：平均與最壞情況均為 O(n²)，最好情況（已有序）為 O(n)
• 空間複雜度：O(1)，屬於原地排序
• 穩定性：穩定排序，相等元素的相對位置不變
• 實現難度：代碼簡單，適合教學與小規模數據排序

算法原理圖解

假設數組垂直豎立，每個元素視為有重量的氣泡。根據「輕氣泡不能在重氣泡之下」的原則，從下往上掃描數組，發現違反原則的輕氣泡則向上「漂浮」。重複此過程，直到任意兩個氣泡都符合輕者在上、重者在下為止。

Java 代碼實現（帶優化標記）

public class BubbleSort {
    public static void sort(Comparable[] data) {
        int len = data.length;
        for (int i = 0; i < len - 1; i++) {
            Comparable temp = null;
            boolean isExchanged = false; // 交換標記
            
            for (int j = len - 1; j > i; j--) {
                if (data[j].compareTo(data[j - 1]) < 0) {
                    temp = data[j];
                    data[j] = data[j - 1];
                    data[j - 1] = temp;
                    isExchanged = true; // 發生交換
                }
            }
            
            // 本趟無交換，提前終止
            if (!isExchanged) {
                return;
            }
        }
    }

    public static void main(String[] args) {
        Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
        sort(c);
        for (Comparable data : c) {
            System.out.println(data);
        }
    }
}

優化說明

引入 isExchanged 標記，若某趟遍歷未發生任何交換，說明數組已有序，可直接結束算法，避免不必要的比較，提升最好情況性能至 O(n)。

適用場景與總結

冒泡排序因 O(n²) 的時間複雜度，不適合大數據量排序。但其代碼極簡、穩定且無需額外空間，常用於教學演示、極小規模數據或近乎有序的數據排序。實際工程中，優先選擇快速排序、歸併排序等 O(n log n) 算法。