C 語言冒泡排序優化：標誌位提前結束，減少無效比較

C 語言冒泡排序優化：標誌位提前結束，減少無效比較

冒泡排序通過相鄰比較交換，將大元素逐步「冒泡」到陣列末尾。基本版無論數據是否有序皆執行完所有輪次。優化關鍵：若某輪無任何交換，說明已有序，立即結束。

一、 優化代碼

void bubble_sort_opt(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) { // 升序
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 本輪無交換，提前結束
    }
}

二、 效果對比

• 已有序陣列：基本版 O(N²) 比較；優化版 1 輪掃描 O(N) 即結束。
• 部分有序：提前若干輪結束。
• 完全逆序：無提前結束機會，仍 O(N²)。

三、 進一步優化：記錄最後交換位置

下一輪內層迴圈只需掃描至上輪最後交換位置，因其後必已有序。

void bubble_sort_opt2(int arr[], int n) {
    int lastSwap = n - 1;
    while (lastSwap > 0) {
        int currSwap = 0;
        for (int j = 0; j < lastSwap; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;
                currSwap = j;
            }
        }
        lastSwap = currSwap;
    }
}

四、 總結

• 標誌位優化極簡、收益大（特別是近乎有序數據），必加。
• 記錄最後交換位置進一步縮小掃描範圍，代碼稍長，效果更佳。
• 冒泡排序教學價值大（簡單、穩定、原地），工程實務 N > 50 建議改用 qsort/快速排序/歸併排序。