基本概念

冒泡排序是一種簡單的排序算法，通過重復比較相鄰的元素并交換它們的位置來實現排序。它的名稱來源于較小的元素像氣泡一樣逐漸“浮”到數組的頂端。

工作原理

介紹

冒泡排序是交換排序的一種，了解其基本思想對學習這種算法至關重要。

所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。重復這個過程直到整個數組有序。

具體實現

以該數組為例，我們每次只關注相鄰兩個元素的大小關系

1. 我們先關注3和44，很明顯，此時的數組[3，44]是有序的，無需交換
   

2. 此時，44和38需要交換
   
   
   此時數組[3，38，44]有序，從44的位置繼續向后比較

3. 找到44和5時同理，需要交換44和5保證升序順序
   
   
   你可能疑問？此時數組[3，38，5，44]不是有序的！
   不要緊，我們先繼續往后交換

4. 我們省略幾步，直接來看這趟比較的結束狀態
   
   此時我們發現，數組中最大的元素47來到了最后面，這就是單趟冒泡排序的效果，一次選出數組中最大或最小的一個數放到應該在的位置上。

5. 我們來分析此時的數組
   
   數組被紅線分割，紅線左邊為無序區，右邊為有序區。
   此時的效果可能不明顯，我們再模擬幾次交換
   
   目前我們又執行了兩次交換，可以看到：有序區的在增加，無序區在減少
   意識到這點之后，你就已經明白了冒泡排序的原理了：通過重復遍歷無序區，對相鄰元素依次比較并交換逆序對，使當前無序區的最值逐步‘浮’到其最終位置；每輪結束后，無序區長度減 1；直至無序區僅剩 1 個元素時，數組完全有序。

代碼實現

因為冒泡排序是較為簡單的經典排序算法，我們直接來看代碼實現。

void BubbleSort(int arr[], int n)
{if (n <= 1) return;int i, j;for (int i = n - 1; i >= 0; i--){for (int j = 0; j < i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);}}}
}

最壞情況：數組完全逆序，需要進行 n(n-1)/2 次比較和交換，時間復雜度O(N^2)

此時可以對冒泡排序做出優化

void BubbleSort(int arr[], int n)
{if (n <= 1) return;int i, j;for (int i = n - 1; i >= 0; i--){bool flag = false;for (int j = 0; j < i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);flag = true;}}if (flag == false)break;}
}

通過提前終止優化，如果在某次循環中沒有發生元素交換，代表此時數組已經有序，直接退出。此時為最優情況，僅需一次遍歷，時間復雜度為 O(N)

總結

冒泡排序是入門級排序算法，核心是通過相鄰元素比較交換，讓最值逐步 “浮” 到對應位置，隨無序區收縮實現有序。?
其時間復雜度為 O (n2)（優化后最好情況 O (n)），空間復雜度 O (1)，是穩定排序。優勢在于簡單易實現，適配接近有序數據；但效率偏低，僅適合小規模場景。?
雖被高效算法替代，但其迭代邏輯仍是理解排序本質的基礎