冒泡排序優化版 C 實現：雙向標誌位提前終止

算法優化點

1. 標誌位優化：若某輪無交換，說明已有序，提前終止
2. 逆序掃描：內層循環從後向前，將大元素「冒泡」到末尾
3. 邊界收縮：外層每輪減少一次比較範圍

完整代碼

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void swap(int *a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void BubbleSort(int *a, int n) {
    int i, j;
    bool flag = true;  // 標誌位：是否發生交換

    for (i = 0; i < n - 1 && flag; i++) {
        flag = false;  // 每輪重置
        // 從後向前，將最大元素推到 i 位置
        for (j = n - 2; j >= i; j--) {
            if (a[j] > a[j + 1]) {
                swap(a, j, j + 1);
                flag = true;  // 發生交換，標記需繼續
            }
        }
    }
}

int main() {
    int i = 0;
    int a[13] = {5, 4, 9, 8, 7, 6, 3, 0, 1, 2, 15, 24, 100};

    BubbleSort(a, 13);

    for (; i < 13; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    system("pause");
    return 0;
}

執行流程演示

初始：[5,4,9,8,7,6,3,0,1,2,15,24,100]

i=0: j=11→0, 最大值 100 沉底
[5,4,9,8,7,6,3,0,1,2,15,24,100]  (無交換? 有)
i=1: j=11→1, 次大 24 定位
...
最終：[0,1,2,3,4,5,6,7,8,9,15,24,100]

複雜度分析

關鍵代碼解析

for (i = 0; i < n - 1 && flag; i++) {  // flag 為 false 直接跳出外層
    flag = false;
    for (j = n - 2; j >= i; j--) {     // 逆序掃描，j+1 不越界
        if (a[j] > a[j + 1]) {
            swap(a, j, j + 1);
            flag = true;
        }
    }
}

本文整理自「年少輕狂」博客，原文地址：https://shpshao.blog.51cto.com/1931202/1297431