目錄
從最簡單的操作開始
如何利用這個原子操作實現一個具體的小目標？
我們來手動模擬一下：
如何從一個小目標擴展到最終目標？
代碼的逐步完善
第一階段：定義函數框架和我們需要的“原子操作”
第二階段：實現“多趟”的邏輯（外層循環）
第三階段：實現每一趟的“比較交換”邏輯（內層循環）
思考與優化
從最簡單的操作開始
📌我們的目標： 將一個無序的數組，例如 [5, 1, 4, 2, 8]，變成有序的 [1, 2, 4, 5, 8]。
面對這個任務，最直接、最“笨”的思考方式是什么？不是去想什么宏大的整體策略，而是思考：
我能做的最小的、能讓數組變得“更”有序一點點的操作是什么？
這個最小的操作就是：只看相鄰的兩個元素。
比如，我們先看 [5, 1]。在最終排好序的數組里，1 肯定在 5 的前面。而現在它們的順序是錯的。怎么辦？很簡單：把它們換過來！?
[5, 1, 4, 2, 8] -> 交換 5 和 1 -> [1, 5, 4, 2, 8]
這個 “比較相鄰元素，如果順序錯了就交換” 的操作，就是冒泡排序算法最核心的原子操作。它非常簡單，但通過重復這個簡單的操作，我們就能完成整個排序的宏偉目標。
如何利用這個原子操作實現一個具體的小目標？
我們不能漫無目的地到處交換。我們需要一個策略。與其想著如何把整個數組排好序，不如先定一個更小、更容易實現的目標：
“我們能否通過這個原子操作，把數組中最大的那個元素，放到它最終應該在的位置上？”
答案是可以的。最大的元素最終應該在數組的最右邊。我們怎么把它“弄”過去呢？
我們可以從數組的左邊開始，一路向右，不停地執行我們的“原子操作”。
我們來手動模擬一下：
假設數組是 arr = [5, 1, 4, 2, 8]，長度 n = 5。
1. 比較 arr[0] 和 arr[1]:
-
[ **5, 1** , 4, 2, 8] -
5 > 1，順序錯了，交換。 -
數組變為:
[ **1, 5** , 4, 2, 8]
2. 比較 arr[1] 和 arr[2]:
-
[1, **5, 4** , 2, 8] -
5 > 4，順序錯了，交換。 -
數組變為:
[1, **4, 5** , 2, 8]
3. 比較 arr[2] 和 arr[3]:
-
[1, 4, **5, 2** , 8] -
5 > 2，順序錯了，交換。 -
數組變為:
[1, 4, **2, 5** , 8]
4. 比較 arr[3] 和 arr[4]:
-
[1, 4, 2, **5, 8** ] -
5 < 8，順序是正確的，什么都不做。 -
數組保持:
[1, 4, 2, 5, 8]
經過這樣從左到右的一整輪操作，我們觀察結果 [1, 4, 2, 5, 8]。我們成功了嗎？
是的！最大的元素 8 已經被我們“護送”到了數組的最末端，也就是它最終應該在的位置。
這個過程就像水中的氣泡，最大的那個總是最先“咕嚕咕嚕”地冒到水面。這就是“冒泡排序”這個名字的由來。我們把這樣一整輪從頭到尾的比較交換過程，稱為一趟 (Pass)。
如何從一個小目標擴展到最終目標？
我們已經完成了一趟，成功地將n個元素中最大的一個歸位了。現在數組是 [1, 4, 2, 5, | 8] (用 | 把已歸位的元素隔開)。
接下來怎么辦？
很簡單，我們把已經歸位的 8 忽略掉，把前面的 [1, 4, 2, 5] 看作是一個規模更小的新問題。
我們只需要對這個新的、長度為 n-1 的數組，重復剛才一模一樣的操作。
👉 我們來模擬第二趟：
-
比較
arr[0]和arr[1]:[ **1, 4** , 2, 5, | 8]->1 < 4，不交換。 -
比較
arr[1]和arr[2]:[1, **4, 2** , 5, | 8]->4 > 2，交換 ->[1, 2, 4, 5, | 8] -
比較
arr[2]和arr[3]:[1, 2, **4, 5** , | 8]->4 < 5，不交換。
第二趟結束后，數組變為 [1, 2, 4, | 5, 8]。看，現在次大的元素 5 也歸位了！
📈 這個邏輯可以一直重復下去。
-
第三趟，對
[1, 2, 4]操作，會把4歸位。 -
第四趟，對
[1, 2]操作，會把2歸位。 -
當只剩下
1的時候，它自然就在正確的位置了。
我們需要多少趟呢？對于一個有n個元素的數組，最多需要 n-1 趟，就能把所有元素都排好序。
這個“重復執行”的思路，在編程里天然就對應著循環?。
代碼的逐步完善
現在，我們把上面的推導翻譯成代碼。
第一階段：定義函數框架和我們需要的“原子操作”
我們知道肯定需要一個排序函數，并且排序過程中必然要用到“交換”這個原子操作。
// C/C++ 中，要在函數內部修改外部變量的值，需要使用指針
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 冒泡排序函數的整體框架
// arr 是要排序的數組，n 是數組的長度
void bubbleSort(int arr[], int n) {// 排序邏輯將在這里實現
}第二階段：實現“多趟”的邏輯（外層循環）
根據我們的推導，需要重復執行 n-1 趟排序。所以我們需要一個循環來控制這個“趟數”。
void bubbleSort(int arr[], int n) {// 這個外層循環控制總共需要多少“趟” (Pass)// i 表示已經有多少個元素在數組末尾歸位了for (int i = 0; i < n - 1; ++i) {// 在這里實現每一趟具體的比較和交換邏輯}
}第三階段：實現每一趟的“比較交換”邏輯（內層循環）
在每一趟中，我們從數組的第一個元素開始，向后兩兩比較。 關鍵點：比較到哪里為止？
-
第一趟 (i=0)，
n個元素都未排序，要比較n-1次，檢查到arr[n-2]和arr[n-1]為止。 -
第二趟 (i=1)，最后1個元素已歸位，只需要處理前面
n-1個元素，比較n-2次，檢查到arr[n-3]和arr[n-2]為止。 -
第
i趟，最后i個元素已歸位，比較范圍是n-1-i次。
這個邏輯正好可以用另一個循環，也就是內層循環來實現。
#include <iostream> // 為了方便打印結果void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}void bubbleSort(int arr[], int n) {// 外層循環，控制“趟數”for (int i = 0; i < n - 1; ++i) {// 內層循環，控制每一趟中的“比較與交換”// 范圍是 n - 1 - i，因為每過一趟，末尾就多一個排好的數for (int j = 0; j < n - 1 - i; ++j) {// 這就是我們的“原子操作”if (arr[j] > arr[j+1]) {swap(&arr[j], &arr[j+1]);}}// 我們可以加一句打印，來觀察每一趟之后的結果std::cout << "第 " << i + 1 << " 趟排序后: ";for(int k=0; k<n; ++k) std::cout << arr[k] << " ";std::cout << std::endl;}
}至此，一個可以正確工作的冒泡排序算法就完成了。它完美地復現了我們從第一性原理出發的推導過程。
復雜度分析
最好情況（數組有序）：只需要一趟掃描，比較 n?1?次，沒有交換 → 時間復雜度： O(n)
最壞情況（數組逆序）：每次都需要比較并交換 →?時間復雜度： O(n^2)
空間復雜度：冒泡排序是 原地排序，只需常數個輔助空間 →?O(1)
穩定性
冒泡排序是 穩定的。
-
原因：只有在
a[j] > a[j+1]時才交換，如果相等，不動。 -
因此相同元素的前后順序不會被破壞。
思考與優化
我們的算法已經能用了，但它是不是最聰明的？有沒有什么情況下它做了“無用功”？
💡設想一個情況：arr = [1, 2, 3, 5, 4]。
-
第一趟后，
4和5交換，數組變為[1, 2, 3, 4, 5]。 -
此時數組已經完全有序了。
但是，我們上面的代碼并不知道這一點。它會繼續傻傻地執行第二趟、第三趟、第四趟，雖然在這些趟中一次交換都不會發生。這顯然是浪費。
優化的第一性原理： 如果我們發現某一趟從頭到尾走下來，一次交換都沒有發生，這說明了什么？
這說明數組中每一個元素都已經不大于它的后一個元素了，也就是說，整個數組已經完全有序了！
那么，我們就可以提前結束排序，而不必執行后面多余的趟數。
最終階段：完善代碼，加入優化
我們可以在每一趟開始前，設置一個標志位 swapped = false。如果在這一趟中發生了交換，就把它設為 true。
一趟結束后，檢查這個標志位。如果它仍然是 false，說明沒發生任何交換，我們就可以直接 break 退出外層循環。
// 優化后的冒泡排序
void bubbleSortOptimized(int arr[], int n) {// 外層循環，控制“趟數”for (int i = 0; i < n - 1; ++i) {bool swapped = false; // 設立標志位// 內層循環for (int j = 0; j < n - 1 - i; ++j) {if (arr[j] > arr[j+1]) {swap(&arr[j], &arr[j+1]);swapped = true; // 只要發生一次交換，就將標志位置為true}}// 檢查標志位：如果在一整趟中都沒有發生交換，說明已經有序if (swapped == false) {std::cout << "在第 " << i + 1 << " 趟后提前結束。" << std::endl;break; // 退出外層循環}std::cout << "第 " << i + 1 << " 趟排序后: ";for(int k=0; k<n; ++k) std::cout << arr[k] << " ";std::cout << std::endl;}
}這樣，我們就從最基本的“交換相鄰錯誤元素”這個原子操作出發，通過“完成小目標 -> 重復操作 -> 發現冗余 -> 加入判斷”這一系列邏輯嚴謹的推導，最終構建出了一個完整且經過優化的冒泡排序算法。
