雙向氣泡排序（雞尾酒排序）C 語言實現：優化版冒泡的原理與代碼詳解

從冒泡到雙向：為什麼要雙向？

標準冒泡排序每輪只將最大元素「冒泡」到右端，小元素像「烏龜」一樣慢速向左移動。雙向氣泡排序（Cocktail Sort / Shaker Sort）每輪雙向掃描：先右向左將最小元素移至左端，再左向右將最大元素移至右端，雙向縮小無序區，顯著減少「烏龜」元素的移動次數。

演算法邏輯與 C 語言實現

#include <stdio.h>

typedef int Elem;
typedef struct { Elem key; int data; } Sqlist;

// 雙向氣泡排序
void cocktailsort(Sqlist R[], int n) {
    int left = 0, right = n - 1;
    int swapped = 1;

    while (swapped && left < right) {
        swapped = 0;

        // 右向左：將最小元素移到 left
        for (int j = right; j > left; --j) {
            if (R[j].key < R[j-1].key) {
                Sqlist tmp = R[j];
                R[j] = R[j-1];
                R[j-1] = tmp;
                swapped = 1;
            }
        }
        ++left; // 左邊界收縮

        // 左向右：將最大元素移到 right
        for (int j = left; j < right; ++j) {
            if (R[j].key > R[j+1].key) {
                Sqlist tmp = R[j];
                R[j] = R[j+1];
                R[j+1] = tmp;
                swapped = 1;
            }
        }
        --right; // 右邊界收縮
    }
}

int main() {
    Sqlist arr[10];
    for (int i = 0; i < 10; ++i) {
        arr[i].key = 10 - i;
        arr[i].data = i;
    }
    cocktailsort(arr, 10);
    for (int i = 0; i < 10; ++i)
        printf("key:%d  data:%d\n", arr[i].key, arr[i].data);
    return 0;
}

關鍵優化點解析

1. 雙向掃描：解決標準冒泡「烏龜」元素移動慢的問題。
2. 邊界收縮：每輪確定左/右邊界各一個元素最終位置，left++/right-- 減少比較次數。
3. 早期退出：若某輪無交換（swapped==0），說明已有序，立即結束。
4. 記錄最後交換位置（進階優化）：下一輪邊界可直接設為最後交換位置，進一步減少比較。

複雜度分析

雙向氣泡在隨機資料下比標準冒泡快約 20%-30%，但在大規模資料下仍不如快排、堆排、歸併排。適合小規模、近乎有序、教學演示場景。

測試輸出

key:1  data:9
key:2  data:8
key:3  data:7
key:4  data:6
key:5  data:5
key:6  data:4
key:7  data:3
key:8  data:2
key:9  data:1
key:10 data:0

總結

雙向氣泡排序是冒泡排序的經典優化變體，通過雙向掃描與邊界收縮顯著改善「烏龜」元素移動效率。代碼簡潔、原地排序、穩定，是理解排序演算法優化思想的優秀教學案例，但工程上大數據量請使用 O(N log N) 演算法。