冒泡排序是入門排序算法的經典，通過相鄰元素兩兩比較、交換，將大元素像氣泡一樣逐步「浮」到數組末端。本文以 6 個數字為例圖解流程，給出標準 C 實現，並指出優化方向。
對無序區間 [0, n-1] 進行多輪掃描：
a[j] 和 a[j+1]。a[j] > a[j+1] 則交換。n-1 輪，第 i 輪比較次數 n-i。[9, 8, 5, 4, 2, 0]第 1 輪 (5次比較)：
9 8 5 4 2 0 → 8 9 5 4 2 0 → 8 5 9 4 2 0 → 8 5 4 9 2 0 → 8 5 4 2 9 0 → 8 5 4 2 0 9
最大值 9 沉底（右端），0 向左移一位。
第 2 輪 (4次比較，針對前5個)：
8 5 4 2 0 9 → 5 8 4 2 0 9 → 5 4 8 2 0 9 → 5 4 2 8 0 9 → 5 4 2 0 8 9
次大值 8 就位。
... 以此類推，共 5 輪完成排序，最終 [0, 2, 4, 5, 8, 9]。
規律： n 個元素需 n-1 輪；第 j 輪比較 n-j 次。
#include <stdio.h>
void bubble_sort(int arr[], int n) {
for (int pass = 0; pass < n - 1; pass++) { // 控制輪數
for (int i = 0; i < n - 1 - pass; i++) { // 每輪比較次數遞減
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
}
}
int main() {
int a[10] = {655, 23, 56, 2345, 3897, 36, 478, 31, 90, 208};
printf("原始：");
for (int i = 0; i < 10; i++) printf("%5d", a[i]);
bubble_sort(a, 10);
printf("\n排序後：");
for (int i = 0; i < 10; i++) printf("%5d", a[i]);
return 0;
}
輸出：
原始： 655 23 56 2345 3897 36 478 31 90 208 排序後： 23 31 36 56 90 208 478 655 2345 3897
若某輪未發生任何交換，說明數組已有序，可立即結束：
void bubble_sort_opt(int arr[], int n) {
for (int pass = 0; pass < n - 1; pass++) {
int swapped = 0;
for (int i = 0; i < n - 1 - pass; i++) {
if (arr[i] > arr[i + 1]) {
int tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp;
swapped = 1;
}
}
if (!swapped) break; // 本輪無交換，已有序
}
}
最佳情況（已有序數組）時間複雜度從 O(n²) 降為 O(n)。
最後一次交換的位置之後必然有序，下一輪只需掃描到該位置：
void bubble_sort_opt2(int arr[], int n) {
int bound = n - 1;
while (bound > 0) {
int last_swap = 0;
for (int i = 0; i < bound; i++) {
if (arr[i] > arr[i+1]) {
int tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp;
last_swap = i;
}
}
bound = last_swap; // 縮小邊界
}
}
| 指標 | 數值 |
|---|---|
| 時間複雜度 (平均/最壞) | O(n²) |
| 時間複雜度 (最佳/優化後) | O(n) |
| 空間複雜度 | O(1) 原地排序 |
| 穩定性 | 穩定 (相等元素不交換) |
| 適用場景 | 教學、極小規模數據、近乎有序數據 |
i < n 導致多一輪無意義比較。i < n 導致 arr[i+1] 越界。tmp 導致數據丟失。n <= 1 的邊界情況（雖然循環不進入也安全）。冒泡排序雖非工程首選（qsort/快排/歸併排序 O(n log n)），但其雙層循環邊界控制、相鄰交換邏輯、優化旗標思想 是算法入門必修課。掌握「每輪確定一個極值、邊界遞減、無交換提前退出」三大核心模式，舉一反三至選擇排序、插入排序、快速排序分區邏輯。
