排序算法的“速度密碼”：時間複雜度與冒泡排序¶

一、爲什麼要研究排序算法的速度？¶

想象一下，如果你有1000個電話號碼需要按順序排列，用一個很慢的算法可能要等幾分鐘，而用一個快的算法可能只需要幾秒。排序算法的“速度”，其實就是它處理數據的效率——數據越多，算法的快慢差異越明顯。所以，理解排序算法的“速度密碼”，本質上就是理解時間複雜度（衡量算法執行時間隨數據量增長的規律）。

二、時間複雜度：算法速度的“密碼本”¶

時間複雜度用大O表示法描述，比如O(n)、O(n²)，它不代表具體時間，而是數據量n增長時，算法執行步驟的“量級”。舉幾個最常見的例子：

• O(n)（線性複雜度）：數據量n越大，步驟數也線性增加。比如“從頭到尾檢查每個數”，n=1000需要1000步，n=100萬需要100萬步。
• O(n²)（平方複雜度）：數據量n越大，步驟數是n的平方。比如“兩兩比較所有數”，n=1000需要1000×1000=100萬步，n=100萬需要1億步，速度會明顯變慢。
• O(log n)（對數複雜度）：比如“二分查找”，數據量翻倍，步驟數只增加1（比如100萬步到200萬步，只需多1步），速度極快。

排序算法的“速度密碼”，就是看它的時間複雜度是O(n²)還是更低（比如O(n log n)）。

三、冒泡排序：最基礎的“氣泡”排序法¶

冒泡排序是最簡單的排序算法之一，原理像“氣泡上浮”：把較小的元素像氣泡一樣慢慢“浮”到數列頂端，較大的元素“沉”到末尾。

核心邏輯：重複遍歷要排序的數組，每次比較相鄰的兩個元素，如果順序錯誤就交換它們。遍歷直到沒有需要交換的元素，說明數組已排序。

四、冒泡排序的實戰演示¶

以數組 [5, 3, 8, 4, 2] 爲例，一步步看冒泡排序如何“冒泡”：

初始數組：[5, 3, 8, 4, 2]

第一輪（找最大數）：
從第一個元素開始，依次比較相鄰元素，把大的數“冒”到末尾：
- 5和3比較：3小，交換 → [3, 5, 8, 4, 2]
- 5和8比較：不用交換 → 保持 [3, 5, 8, 4, 2]
- 8和4比較：4小，交換 → [3, 5, 4, 8, 2]
- 8和2比較：2小，交換 → [3, 5, 4, 2, 8]
結果：最大的8已“冒”到最後，數組變爲 [3, 5, 4, 2, 8]。

第二輪（找第二大的數）：
排除最後一個已排好的8，繼續比較前4個元素：
- 3和5比較：不用交換 → [3, 5, 4, 2, 8]
- 5和4比較：4小，交換 → [3, 4, 5, 2, 8]
- 5和2比較：2小，交換 → [3, 4, 2, 5, 8]
結果：第二大的5已“冒”到倒數第二個位置，數組變爲 [3, 4, 2, 5, 8]。

第三輪（找第三大的數）：
排除最後兩個已排好的數（5和8），比較前3個元素：
- 3和4比較：不用交換 → [3, 4, 2, 5, 8]
- 4和2比較：2小，交換 → [3, 2, 4, 5, 8]
結果：第三大的4已“冒”到倒數第三個位置，數組變爲 [3, 2, 4, 5, 8]。

第四輪（找第四大的數）：
排除最後三個已排好的數，比較前2個元素：
- 3和2比較：2小，交換 → [2, 3, 4, 5, 8]
結果：所有元素已排序完成！

五、冒泡排序的時間複雜度¶

冒泡排序需要兩層循環：
- 外層循環：遍歷n個元素，共n次；
- 內層循環：每輪比較相鄰元素，最多n-1次（每輪少比較1個已排好的元素）。

總比較次數爲：(n-1) + (n-2) + ... + 1 = n(n-1)/2，約等於 n²/2，因此時間複雜度是 O(n²)。

六、冒泡排序的優缺點¶

優點：
- 簡單易懂，邏輯直觀，適合初學者理解排序思想；
- 不需要額外存儲空間（原地排序），空間複雜度爲O(1)。

缺點：
- 時間複雜度高（O(n²)），數據量大時速度極慢；
- 效率低，實際應用中很少直接使用（如百萬級數據排序會耗時極久）。

總結¶

時間複雜度是衡量算法“速度”的核心指標，冒泡排序作爲最簡單的排序算法，雖然速度慢（O(n²)），但它是理解排序思想和時間複雜度的絕佳入門工具。真正高效的排序算法（如快速排序、歸併排序）會將時間複雜度優化到O(n log n)，但它們的核心邏輯仍與“比較交換”相關。通過冒泡排序，我們能更直觀地理解“數據量增長如何影響算法速度”，爲學習更復雜的排序算法打下基礎。