一、算法核心概念

冒泡排序是一種簡單的交換排序算法，其核心思想是：通過重復遍歷待排序數組，每次比較相鄰的兩個元素，若它們的順序錯誤（如升序排序中前一個元素大于后一個），則交換它們的位置。經過多輪遍歷后，較大的元素會像“氣泡”一樣逐漸“上浮”到數組的末尾，最終使整個數組有序。

二、基本工作原理

以升序排序為例，冒泡排序的工作流程可概括為：

1. 初始狀態：整個數組為“未排序區間”（需排序的元素范圍）；
2. 每輪遍歷：從數組頭部開始，依次比較相鄰元素（arr[j]與arr[j+1]），若arr[j] > arr[j+1]，則交換兩者位置；
3. 范圍收縮：每輪遍歷結束后，當前未排序區間中最大的元素會“浮”到區間的末尾，因此下一輪的未排序區間可縮小1個元素（無需再檢查已“浮”到末尾的元素）；
4. 終止條件：當某輪遍歷中沒有發生任何元素交換時，說明數組已完全有序，排序結束。

三、步驟演示（實例解析）

以數組[5, 3, 8, 4, 2]為例，演示升序冒泡排序的過程：

輪次	未排序區間	遍歷中的比較與交換	本輪結束后數組	是否發生交換
1	[0,4]（全數組）	比較5&3→交換→[3,5,8,4,2]； 比較5&8→不交換； 比較8&4→交換→[3,5,4,8,2]； 比較8&2→交換→[3,5,4,2,8]	[3,5,4,2,8]	是
2	[0,3]（前4個元素）	比較3&5→不交換； 比較5&4→交換→[3,4,5,2,8]； 比較5&2→交換→[3,4,2,5,8]	[3,4,2,5,8]	是
3	[0,2]（前3個元素）	比較3&4→不交換； 比較4&2→交換→[3,2,4,5,8]	[3,2,4,5,8]	是
4	[0,1]（前2個元素）	比較3&2→交換→[2,3,4,5,8]	[2,3,4,5,8]	是
5	[0,0]（僅第1個元素）	無相鄰元素可比較	[2,3,4,5,8]	否（排序結束）

四、時間復雜度與空間復雜度

• 時間復雜度：

  • 最壞情況：數組完全逆序，需執行n-1輪遍歷，每輪比較n-i次（i為輪次），總操作次數為n+(n-1)+...+1 = n(n-1)/2，故為O(n2)；
  • 最好情況：數組已完全有序，若添加“交換標志”優化，僅需1輪遍歷（n-1次比較）即可判斷有序，故為O(n)；
  • 平均情況：O(n2)（適用于隨機無序數組）。

• 空間復雜度：
  僅需常數個臨時變量（用于交換元素和記錄標志），故為O(1)（原地排序）。

五、穩定性分析

冒泡排序是穩定的排序算法。

• 穩定性定義：若數組中存在相等元素，排序后它們的相對順序與原數組一致，則算法穩定。
• 原因：冒泡排序僅在相鄰元素嚴格逆序（如arr[j] > arr[j+1]）時才交換，若arr[j] == arr[j+1]，不會觸發交換，因此相等元素的相對順序保持不變。

六、優化策略

基礎版冒泡排序在數組已部分有序時仍會執行不必要的遍歷，可通過以下優化提升效率：

1. 交換標志優化（核心優化）

添加一個布爾變量（如swapped），記錄每輪是否發生交換。若某輪未發生交換，說明數組已有序，可直接終止排序。

2. 記錄最后交換位置（進階優化）

每輪遍歷中，記錄最后一次發生交換的位置lastSwapIndex。下一輪遍歷的終點可設為lastSwapIndex（因為該位置之后的元素已有序），減少無效比較。

七、C++實現代碼

1. 基礎版實現

#include <iostream>
#include <vector>
using namespace std;// 基礎版冒泡排序（升序）
void bubbleSortBasic(vector<int>& arr) {int n = arr.size();// 外層循環：控制輪次（最多n-1輪）for (int i = 0; i < n - 1; ++i) {// 內層循環：遍歷未排序區間[0, n-1-i]for (int j = 0; j < n - 1 - i; ++j) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j + 1]); // 交換逆序元素}}}
}int main() {vector<int> arr = {5, 3, 8, 4, 2};bubbleSortBasic(arr);for (int num : arr) {cout << num << " "; // 輸出：2 3 4 5 8}return 0;
}

2. 優化版實現（交換標志+最后交換位置）

#include <iostream>
#include <vector>
using namespace std;// 優化版冒泡排序（升序）
void bubbleSortOptimized(vector<int>& arr) {int n = arr.size();int lastSwapIndex = 0; // 記錄最后一次交換的位置int border = n - 1;    // 當前未排序區間的右邊界（初始為數組末尾）for (int i = 0; i < n - 1; ++i) {bool swapped = false; // 標志位：本輪是否發生交換// 內層循環僅遍歷到border（減少無效比較）for (int j = 0; j < border; ++j) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j + 1]);swapped = true;lastSwapIndex = j; // 更新最后交換位置}}border = lastSwapIndex; // 收縮未排序區間右邊界if (!swapped) break;    // 未交換，數組已有序，提前終止}
}int main() {vector<int> arr = {5, 3, 8, 4, 2};bubbleSortOptimized(arr);for (int num : arr) {cout << num << " "; // 輸出：2 3 4 5 8}return 0;
}

八、適用場景與局限性

適用場景：

1. 小規模數據排序：數據量較小時（如n < 100），冒泡排序實現簡單，性能可接受；
2. 幾乎有序的數據：若數組已接近有序（僅少數元素逆序），優化后的冒泡排序可快速完成排序（接近O(n)復雜度）；
3. 教學場景：算法邏輯直觀，易于理解，適合作為入門排序算法講解。

局限性：

1. 大規模數據效率低：時間復雜度為O(n2)，對于n > 1000的數組，排序速度遠低于O(nlogn)級算法（如快速排序、歸并排序）；
2. 交換操作頻繁：每輪可能發生多次相鄰元素交換，實際運行時間比同復雜度的選擇排序更長（選擇排序每輪僅1次交換）。

---

冒泡排序是一種直觀、簡單的排序算法，核心通過“相鄰元素比較交換”使大元素逐步上浮。盡管其時間復雜度較高（O(n2)），但在小規模或近乎有序的數據場景中仍有應用價值。通過“交換標志”和“收縮邊界”優化，可顯著提升其在部分有序數據上的性能。