氣泡排序法

前言

氣泡排序（Bubble Sort）是一種簡單但效能較低的排序演算法。它的核心概念是「兩兩比較、交換」。

演算法流程

如果要對 n 個數，(或者陣列長度為 n)進行氣泡排序，那麼就要進行n-1 輪的比較，每一輪遍歷時，比較相鄰元素並交換，使本輪最大元素「浮」到最後。

實際範例

[64, 25, 86, 77, 14]

排序步驟如下所示:

1. 第一輪(外層迴圈)，比較4次

2. 第二輪，比較3次

3. 第三輪，比較2次

4. 第四輪，完成排序

程式碼實作

#include <stdio.h>

// 氣泡排序函式
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { 
        for (int j = 0; j < n - 1 - i; j++) { 
            if (arr[j] > arr[j + 1]) { 
                // 交換元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 輔助函式：列印陣列
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;
}

而如果某一輪沒有發生交換，表示陣列已經排序完成，可以提前結束。

void optimizedBubbleSort(int arr[], int n) {
    int swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = 0;  // 交換標誌
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;  // 標記發生交換
            }
        }
        if (swapped == 0) break;  // 若無交換，提前結束
    }
}

• 這種優化方式可以減少排序已接近完成時的執行時間。