C語言冒泡排序實作與常見邏輯錯誤分析

編輯：關於C語言

C語言冒泡排序實作與常見邏輯錯誤分析

冒泡排序是最基礎的排序演算法，但初學者極易寫錯迴圈邊界、交換邏輯、優化條件。本文提供標準正確實作、原始碼中常見的四大錯誤分析、優化版本（提前結束、雞尾酒排序）、複雜度分析與教學建議。

標準正確實作

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {           // 趟數
        bool swapped = false;                   // 優化旗標
        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 = true;
            }
        }
        if (!swapped) break;  // 本趟無交換，已有序，提前結束
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始: "); printArray(arr, n);
    bubbleSort(arr, n);
    printf("排序: "); printArray(arr, n);
    return 0;
}

原始碼四大錯誤分析

// 原始錯誤碼
int arr[10] = {1,2,4,3,4,3,2,5,6,7};
int len = sizeof(arr)/sizeof(arr[0]);
for (i = 0; i < len; i++) {
    if (arr[i] < arr[i + 1]);   // 錯誤 1: 分號導致 if 空執行，且 i+1 越界
    for (j = 0; j < len - i -1; j++) {
        if (arr[j] >= arr[j + 1]) {  // 錯誤 2: >= 破壞穩定性
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
        }
    }
}

錯誤	代碼	後果	修正
1. if 後多餘分號	`if (arr[i] < arr[i+1]);`	條件判斷失效，永遠執行內層迴圈；`i=len-1` 時 `arr[i+1]` 越界	移除分號，或刪除此行（無意義）
2. 外層迴圈多跑一次	`i < len`	第 `len` 趟無意義，且內層 `j < len-i-1` 變負數	`i < len - 1`
3. 比較用 >= 破壞穩定性	`arr[j] >= arr[j+1]`	相等元素也交換，改變相對順序	`arr[j] > arr[j+1]`
4. 缺少提前結束優化	無 `swapped` 旗標	已排序陣列仍跑完 O(n²)	加入 `swapped` 旗標

進階優化版本

1. 雞尾酒排序：雙向冒泡

void cocktailSort(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left < right) {
        // 正向：大的沉底
        for (int i = left; i < right; i++)
            if (arr[i] > arr[i+1]) swap(&arr[i], &arr[i+1]);
        right--;

        // 反向：小的浮頂
        for (int i = right; i > left; i--)
            if (arr[i] < arr[i-1]) swap(&arr[i], &arr[i-1]);
        left++;
    }
}

2. 記錄最後交換位置

void bubbleSortOptimized(int arr[], int n) {
    int lastSwap = n - 1;
    while (lastSwap > 0) {
        int currentSwap = 0;
        for (int j = 0; j < lastSwap; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                currentSwap = j;
            }
        }
        lastSwap = currentSwap;  // 之後無需比較
    }
}

複雜度與特性總結

指標	數值	說明
最好時間	O(n)	已排序，提前結束
平均時間	O(n²)
最壞時間	O(n²)	逆序
空間複雜度	O(1)	原地排序
穩定性	穩定	僅用 > 比較
適應性	強	接近有序極快