C語言冒泡排序怎么實現

# C語言冒泡排序怎么實現

冒泡排序（Bubble Sort）是最基礎的排序算法之一，其核心思想是通過相鄰元素的比較和交換，將較大的元素逐步"浮"到數組末端。本文將詳細講解C語言中冒泡排序的實現原理、代碼示例及優化方法。

## 一、算法原理

冒泡排序的工作流程如下：
1. 從數組第一個元素開始，比較相鄰的兩個元素
2. 如果前一個元素大于后一個元素（升序排序），則交換它們的位置
3. 對每一對相鄰元素重復上述操作，直到數組末尾
4. 重復以上步驟，每次遍歷將最大的元素"冒泡"到最終位置
5. 持續進行直到整個數組有序

## 二、基礎實現

以下是標準的冒泡排序C語言實現：

```c
#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {       // 外層循環控制輪次
        for (int j = 0; j < n - i - 1; j++) {  // 內層循環進行比較
            if (arr[j] > arr[j + 1]) {     // 相鄰元素比較
                // 交換元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前數組：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    bubbleSort(arr, n);
    
    printf("\n排序后數組：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

三、算法優化

基礎實現存在效率問題，可以通過以下兩種方式優化：

1. 提前終止優化

當某一輪遍歷沒有發生任何交換時，說明數組已經有序，可以提前終止排序。

void optimizedBubbleSort(int arr[], int n) {
    int swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = 0;  // 交換標志
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 如果沒有交換則提前退出
    }
}

2. 記錄最后交換位置

記錄每輪最后一次交換的位置，后續遍歷只需處理到這個位置即可。

void advancedBubbleSort(int arr[], int n) {
    int lastSwapPos, k = n - 1;
    for (int i = 0; i < n - 1; i++) {
        lastSwapPos = 0;
        for (int j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastSwapPos = j;  // 記錄最后交換位置
            }
        }
        k = lastSwapPos;  // 更新遍歷邊界
        if (k == 0) break;
    }
}

四、算法分析

五、實際應用建議

1. 教學演示：非常適合作為排序算法的入門教學案例
2. 小型數據集：當數據量<1000時性能尚可接受
3. 特殊場景：對基本有序的數組效率較高（接近O(n)）

六、總結

冒泡排序雖然效率不高，但其簡單直觀的實現方式使其成為學習算法的重要起點。理解冒泡排序有助于掌握更復雜的排序算法。在實際開發中，對于性能要求較高的場景建議使用快速排序或歸并排序等更高效的算法。 “`