前言
氣泡排序（Bubble Sort）是一種簡單但效能較低的排序演算法。它的核心概念是「兩兩比較、交換」。
演算法流程
如果要對 n 個數，(或者陣列長度為 n)進行氣泡排序，那麼就要進行n-1 輪的比較，每一輪遍歷時，比較相鄰元素並交換，使本輪最大元素「浮」到最後。實際範例
原始陣列如下:
[64, 25, 86, 77, 14]排序步驟如下所示:
- 第一輪(外層迴圈)，比較4次
- 第二輪，比較3次
- 第三輪，比較2次
- 第四輪，完成排序
程式碼實作
#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; // 若無交換，提前結束
}
}
- 這種優化方式可以減少排序已接近完成時的執行時間。
