Java 冒泡排序算法完整實現與優化詳解

冒泡排序核心原理

冒泡排序是一種基礎的交換排序算法，其核心思想是重複遍歷待排序的數組，比較相鄰元素，若順序錯誤則交換它們。每一輪遍歷都會將當前未排序部分的最大元素「冒泡」到正確位置，因此得名。

標準實現代碼

public class BubbleSort {
    /**
     * 冒泡排序優化版本
     * @param arr 待排序數組
     * @return 排序後的數組
     */
    public int[] bubbleSort(int[] arr) {
        int n = arr.length;
        // 外層循環控制排序輪數
        for (int i = 0; i < n - 1; i++) {
            // 標記位：若某輪無交換，說明已有序，提前終止
            boolean swapped = false;
            
            // 內層循環從後向前比較相鄰元素
            for (int j = n - 1; j > 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;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] data = {25, 56, 32, 20, 1, 5, 89, 3, 8, 41};
        BubbleSort sorter = new BubbleSort();
        sorter.bubbleSort(data);
        
        System.out.print("排序結果: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

算法複雜度分析

• 時間複雜度：平均 O(n²)，最好 O(n)（已有序數組），最差 O(n²)（逆序數組）
• 空間複雜度：O(1)，原地排序
• 穩定性：穩定排序，相等元素相對位置不變

關鍵優化點

引入 swapped 標記位是關鍵優化。當某次遍歷未發生任何交換時，表明數組已完全有序，可立即終止外層循環，將最好情況時間複雜度從 O(n²) 降至 O(n)。這對近乎有序的數據集效果顯著。

適用場景

冒泡排序因其簡單易懂，適合教學演示及小規模數據（n < 50）排序。大規模數據建議使用快速排序、歸併排序等 O(n log n) 算法。