VC++ 冒泡排序法優化：雙向冒泡演算法實作與分析

傳統單向冒泡回顧

void BubbleSort(int* pData, int Count) {
    int iTemp;
    for (int i = 1; i < Count; i++) {
        for (int j = Count - 1; j >= i; j--) {
            if (pData[j] < pData[j-1]) {
                iTemp = pData[j-1];
                pData[j-1] = pData[j];
                pData[j] = iTemp;
            }
        }
    }
}

每輪將最小值「浮」至左端，需 n-1 輪完成排序。

雙向冒泡優化思路

單輪迴圈同時執行：

• 正向掃描（右→左）： 將最小值移至左界。
• 反向掃描（左→右）： 將最大值移至右界。

每輪確定兩個元素最終位置，輪數減半，交換次數顯著降低。

雙向冒泡實作

void Bubble2Sort(int* pData, int Count) {
    int iTemp, left = 1, right = Count - 1, t;
    do {
        // 正向：找最小值移至 left
        for (int i = right; i >= left; i--) {
            if (pData[i] < pData[i-1]) {
                iTemp = pData[i];
                pData[i] = pData[i-1];
                pData[i-1] = iTemp;
                t = i; // 記錄最後交換位置
            }
        }
        left = t + 1; // 縮小左界

        // 反向：找最大值移至 right
        for (int i = left; i <= right; i++) {
            if (pData[i] < pData[i-1]) {
                iTemp = pData[i];
                pData[i] = pData[i-1];
                pData[i-1] = iTemp;
                t = i;
            }
        }
        right = t - 1; // 縮小右界
    } while (left <= right);
}

效能分析

雙向冒泡雖同屬 O(n²)，但常數因子較小，對中小型資料集（< 1000 筆）效能提升明顯。並記錄最後交換位置動態縮小掃描範圍，進一步減少比較次數。

適用場景與建議

• 教學示範、資料量小、簡單實作場合。
• 大量資料請改用 qsort、std::sort (O(n log n))。
• 近似有序資料雙向冒泡表現優異。

總結

雙向冒泡透過單輪雙掃描+邊界動態收縮，將傳統冒泡排序效能提升約 2 倍，是簡單排序演算法的經典優化範例。理解其邊界更新邏輯（left = t+1, right = t-1）有助於掌握演算法優化的核心思想：利用已知資訊減少冗餘計算。