大家好！今天我們來學習一個簡單又經典的排序算法——冒泡排序，並且用C++語言實現它。冒泡排序的名字聽起來很有趣，它的核心思想就像水中的氣泡會向上浮一樣，小的元素會逐漸“冒”到數組的頂端，最終讓整個數組變得有序。
一、冒泡排序的基本思想¶
冒泡排序的核心是重複比較相鄰的兩個元素，如果它們的順序錯誤就交換位置。具體來說：
- 從數組的第一個元素開始，依次比較相鄰的兩個元素。
- 如果前一個元素比後一個元素大，就交換它們的位置。
- 這樣一輪比較下來，數組中最大的元素會“冒泡”到數組的末尾。
- 重複上述過程，每一輪都能確定一個最大元素的最終位置，直到整個數組有序。
二、舉個例子理解過程¶
假設我們有一個數組：[5, 2, 9, 1, 5, 6]，我們用冒泡排序來讓它有序。
第一輪（確定最大元素9的位置）：
- 比較5和2：5>2，交換 → [2, 5, 9, 1, 5, 6]
- 比較5和9：5<9，不交換
- 比較9和1：9>1，交換 → [2, 5, 1, 9, 5, 6]
- 比較9和5：9>5，交換 → [2, 5, 1, 5, 9, 6]
- 比較9和6：9>6，交換 → [2, 5, 1, 5, 6, 9]
此時最大元素9已“冒泡”到數組末尾，無需再比較。
第二輪（確定第二大元素6的位置）：
- 比較2和5：2<5，不交換
- 比較5和1：5>1，交換 → [2, 1, 5, 5, 6, 9]
- 比較5和5：相等，不交換
- 比較5和6：5<6，不交換
此時第二大元素6已確定位置。
後續輪次類似，直到所有元素有序。
三、C++代碼實現¶
下面是冒泡排序的C++代碼實現，附帶詳細註釋：
#include <iostream>
using namespace std;
// 冒泡排序函數：參數爲數組和數組長度
void bubbleSort(int arr[], int n) {
// 外層循環：控制需要進行多少輪比較（n個元素需n-1輪）
for (int i = 0; i < n - 1; ++i) {
bool swapped = false; // 標記本輪是否發生交換
// 內層循環：每輪比較相鄰元素，範圍爲數組前n-i-1個元素（已排好的最大元素不需要再比較）
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 = true; // 標記發生了交換
}
}
// 優化：如果本輪沒有交換，說明數組已完全有序，提前退出
if (!swapped) {
break;
}
}
}
// 主函數：測試冒泡排序
int main() {
int arr[] = {5, 2, 9, 1, 5, 6}; // 待排序數組
int n = sizeof(arr) / sizeof(arr[0]); // 計算數組長度
cout << "排序前數組：";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
bubbleSort(arr, n); // 調用冒泡排序函數
cout << "排序後數組：";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
四、代碼解釋¶
-
外層循環：
for (int i = 0; i < n - 1; ++i)
控制排序的輪數。由於n個元素最多需要n-1輪（每輪確定一個最大元素的位置），所以循環次數爲n-1。 -
內層循環：
for (int j = 0; j < n - i - 1; ++j)
控制每輪的比較次數。每輪結束後，最大元素已“冒泡”到末尾，因此下一輪無需比較最後i個元素（i爲當前輪次），比較範圍縮小到n - i - 1。 -
交換邏輯：
int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
使用臨時變量temp交換相鄰元素，確保交換過程中數據不丟失。 -
優化點：
bool swapped = false
如果某一輪沒有發生交換，說明數組已完全有序，可提前退出外層循環，避免無效比較，提升效率。
五、運行結果¶
上述代碼運行後，輸出如下：
排序前數組：5 2 9 1 5 6
排序後數組：1 2 5 5 6 9
六、複雜度分析¶
- 時間複雜度：
- 最壞情況（完全逆序）：O(n²)（需完整n-1輪，每輪比較n-i次）。
- 最好情況（已排序）：O(n)（優化後僅需1輪，無交換直接退出）。
-
平均情況：O(n²)。
-
空間複雜度：O(1)（僅使用1個臨時變量，原地排序）。
-
穩定性：穩定排序（相等元素不會交換位置）。
七、總結¶
冒泡排序是學習排序算法的入門首選，它的核心思想簡單直觀，容易理解。雖然效率不如快速排序、歸併排序等高級算法，但通過它能幫助我們掌握“比較交換”的基本排序邏輯。如果你想進一步優化，可以嘗試調整數組的初始化、修改交換條件等。動手實踐是理解算法的最好方式，不妨嘗試修改代碼中的數組元素，看看不同情況下冒泡排序的表現吧！