Java 實現冒泡排序與雞尾酒排序（雙向冒泡）算法詳解

冒泡排序

核心思想：相鄰元素兩兩比較，逆序則交換。每輪將最大/最小元素「冒泡」到末端。
比較次數：(n-1)+(n-2)+...+1 = n(n-1)/2，時間複雜度 O(n²)。

三種寫法對比（升序）

// 寫法 1：雙層固定循環，比較次數 n²-n
static void orderAsc(int[] ary) { ... }

// 寫法 2：外層遞減，內層 0~j-1，比較次數 (n²-n)/2
static void orderAsc2(int[] ary) { ... }

// 寫法 3：外層遞增，內層 len-1 遞減到 j+1，比較次數 (n²-n)/2（推薦）
static void orderAsc1(int[] ary) {
    int count = 0, len = ary.length;
    for (int j = 0; j < len; j++) {
        for (int k = len - 1; k > j; k--) {
            if (ary[k] < ary[k - 1]) {
                ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0; // 位運算交換
            }
            count++;
        }
    }
    System.out.println("比較次數: " + count);
}

運行結果

-------排序前------
898 7 862 286 879 660 433 724 316 737
-----orderAsc1升序排序後------次數：45
7 286 316 433 660 724 737 862 879 898

雞尾酒排序

又稱雙向冒泡排序。單向冒泡每輪只能將一個極值移至正確位置；雞尾酒排序雙向交替：左→右冒泡最大值到右端，右→左冒泡最小值到左端，邊界收縮。
時間複雜度仍為 O(N²)，但對部分有序數據交換次數較少，實際性能略優於普通冒泡。

核心實現

static void orderAsc1(int[] ary) {
    int compareCount = 0, changeCount = 0, len = ary.length;
    int left = 0, right = len - 1, tl, tr;
    while (left < right) {
        tl = left + 1; tr = right - 1;
        // 左→右，大元素右移
        for (int k = left; k < right; k++) {
            if (ary[k] > ary[k + 1]) {
                swap(ary, k, k + 1);
                changeCount++; tr = k;
            }
            compareCount++;
        }
        right = tr;
        // 右→左，小元素左移
        for (int k = right; k > left; k--) {
            if (ary[k] < ary[k - 1]) {
                swap(ary, k, k - 1);
                changeCount++; tl = k;
            }
            compareCount++;
        }
        left = tl;
    }
    System.out.println("比較:" + compareCount + " 交換:" + changeCount);
}

運行結果

-------排序前------
783 173 53 955 697 839 201 899 680 677
-----orderAsc1升序排序後------比較次數：34, 交換次數：22
53 173 201 677 680 697 783 839 899 955

總結

• 冒泡排序教學價值大，工程實際極少直接使用。
• 雞尾酒排序通過雙向掃描減少不必要的比較，是冒泡家族的優化版本。
• 生產環境排序請直接使用 Arrays.sort() / Collections.sort()。