Java 冒泡排序演算法詳解與優化

演算法基本思想

冒泡排序屬於交換排序：兩兩比較相鄰元素，順序錯誤即交換，直到無逆序為止。將陣列視為垂直排列的氣泡，較輕（數值較小）的氣泡向上「飄浮」，每趟掃描將當前無序區最小元素移至有序區頂端。

排序過程示例

對序列 49 38 65 97 76 13 27 49 排序：

• 第 1 趟：最小值 13 浮至索引 0
• 第 2 趟：次小值 27 浮至索引 1
• ……經 n-1 趟完成

標準實作（含提前終止優化）

void BubbleSort(SeqList R) {
    int i, j;
    boolean exchange;
    for (i = 1; i < n; i++) {
        exchange = false;
        for (j = n-1; j >= i; j--)
            if (R[j+1].key < R[j].key) {
                swap(R, j+1, j);
                exchange = true;
            }
        if (!exchange) return; // 本趟無交換，提前結束
    }
}

複雜度分析

屬於就地排序，且穩定（相等元素相對位置不變）。

兩種改進方向

1. 記錄最後交換位置

下一趟只需掃描到 lastExchange，可一次擴充多個有序元素，減少趟數。

2. 雙向掃描（雞尾酒排序）

交替「向上飄浮」與「向下沉降」，解決「最重氣泡在頂端需 n-1 趟」的不對稱問題。

Java 通用實作（支援 Comparable）

public class BubbleSort implements SortStrategy {
    public void sort(Comparable[] obj) {
        if (obj == null) throw new NullPointerException("The argument can not be null!");
        Comparable tmp;
        for (int i = 0; i < obj.length; i++)
            for (int j = 0; j < obj.length - i - 1; j++)
                if (obj[j].compareTo(obj[j+1]) > 0) {
                    tmp = obj[j];
                    obj[j] = obj[j+1];
                    obj[j+1] = tmp;
                }
    }
}

此版本使用正向掃描（大值後移），邏輯與教科書反向掃描等價，適用於任何實作 Comparable 的物件陣列。