C 語言氣泡排序演算法詳解與優化實作

演算法核心流程

1. 從陣列起始位置開始，比較相鄰兩元素。
2. 若前者大於後者，交換位置。
3. 第一趟結束後，最大元素「浮」至末尾。
4. 後續各趟比較範圍逐次縮減一，共需 n-1 趟。

基礎實作

#include 
#include 

#define N 10

int main(void) {
    int a[N], i, j, t;
    printf("隨機產生 10 個 100 以內的數:\n");
    for (i = 0; i < N; i++) {
        a[i] = rand() % 100;
        printf("%d ", a[i]);
    }
    printf("\n");

    for (j = 1; j <= N-1; j++) {          /* 趟數 */
        for (i = 0; i <= N-1-j; i++) {    /* 比較次數遞減 */
            if (a[i] > a[i+1]) {
                t = a[i]; a[i] = a[i+1]; a[i+1] = t;
            }
        }
    }

    printf("排序後:\n");
    for (i = 0; i < N; i++) printf("%d ", a[i]);
    return 0;
}

執行結果示例

關鍵優化策略

1. 提前終止旗標

for (j = 1; j <= N-1; j++) {
    int swapped = 0;
    for (i = 0; i <= N-1-j; i++) {
        if (a[i] > a[i+1]) {
            t = a[i]; a[i] = a[i+1]; a[i+1] = t;
            swapped = 1;
        }
    }
    if (!swapped) break;  /* 本趟無交換，已有序 */
}

2. 雞尾酒排序

雙向交替掃描，將最小元素「沉」至前端，最大元素「浮」至後端，減少龜兔速度差異。

3. 記錄最後交換位置

下一趟只需掃描至上一趟最後交換位置，因其後必已有序。

複雜度總結

適用場景

• 教學示範、極小資料集（n < 50）。
• 近乎有序資料（配合旗標可達 O(n)）。
• 嵌入式系統中記憶體極受限、程式碼體積敏感場合。