冒泡排序法詳解

冒泡排序法

HTML5學堂-碼匠：本期繼續走入演算法 —— 冒泡排序法。冒泡排序演算法相對簡單，容易上手，穩定性也比較高, 算是一種較好理解的演算法，也是面試官高頻提問的演算法之一。

Tips：關於「演算法」及「排序」的基礎知識，在先前「選擇排序法」中已詳細講解，可點擊文後的相關文章連結查看，在此不再贅述。

冒泡排序法的原理

基本原理

從序列頭部開始遍歷，兩兩比較，如果前者比後者大，則交換位置，直到最後將最大的數（本次排序最大的數）交換到無序序列的尾部，從而成為有序序列的一部分；

下次遍歷時，此前每次遍歷後的最大數不再參與排序；

多次重複此操作，直到序列排序完成。

由於在排序的過程中總是小數往前放，大數往後放，類似於氣泡逐漸向上漂浮，所以稱作冒泡排序。

原理圖解

Tips：藍色代表在一輪排序中等待交換，黑色代表在該輪排序中已交換完成，紅色代表已排序完成

#實現冒泡的步驟分解

使用for迴圈來決定排序次數

#由於待排序的序列只剩下一個數時已經能夠確定順序，則無需進行排序，因此，排序次數為序列長度– 1。

 每次排序的比較次數控制

每次排序，序列中的多個數字要分別進行兩兩比較，多次的比較需要利用for語句來進行實作。此for迴圈嵌套於排序次數的for迴圈當中（形成雙for的巢狀）。

Tips：j 需要設定為小於len - i - 1，減i的原因是已經排序完成的數不再參與比較，減1的原因是數組下標索引值從0開始。

核心功能 — 兩兩比較並根據情況交換位置

比較兩數大小，如果前者比後者大，則進行數值的交換，也就是交換位置。

冒泡排序法完整程式碼

#冒泡排序法的最佳化

假如序列的數據為：[0, 1, 2, 3, 4, 5]；

使用上面的冒泡排序法進行排序，得到的結果肯定沒有問題，但是，待排序的序列是有序的，理論上是無需遍歷排序。

目前的演算法不管初始的序列是否有序，都會進行遍歷排序，效率會比較低，因此需要最佳化目前的排序演算法。

在如下的演算法中，引入一個swap變量，每一次排序之前初始化為false；若發生兩數交換位置，則將其設為true。

在每次排序結束時候判斷swap是否為false，如果是，則表示序列已排序完成或序列本身是有序序列，就不再進行下一次排序。

透過此方法，減少不必要的比較和位置交換，進一步提高演算法的效能。

冒泡排序法的效率

時間複雜度

最佳狀態：待排序的序列本身就是有序序列，排序次數根據優化後的程式碼，可以得出是n-1次，時間複雜度為O(n)；

#最壞的情況：待排序的序列是逆序的，此時需要排序1 + 2 +3 ……(n - 1) = n(n – 1 )/2次

時間複雜度為O(n^2)。

空間複雜度

冒泡排序法需要一個額外空間（temp變數）來交換元素的位置，所以空間複雜度為O(1)。

演算法的穩定性

當相鄰元素相等時，並不需要交換位置，也就不會出現相同元素的前後順序改變，所以，是穩定性排序。

O是個啥？ ！

時間複雜度，更精確的說該是描述演算法在問題規模不斷增加時所對應的時間成長曲線。所以，這些成長數量級並不是一個準確的效能評價，可以理解為一個近似值。 （空間複雜度同理）

O(n?)表示當n很大的時候，複雜度約等於Cn?，C是某個常數，簡單說就是當n夠大的時候，隨著n的線性增長複雜度將沿平方增長。

O(n)表示，n很大的時候複雜度約等於Cn，C是某個常數。簡言之：隨著n的線性增長，複雜度沿著線性等級增長。

O(1)表示，n很大的時候，複雜度基本上就不成長了。簡言之：隨著n的線性增長，複雜度不受n的影響，沿常數級別增長（此處的常數為1）。

Tips：圖中O(1)緊貼X軸，並看不太清楚。

Tips：此圖來自「Stack Overflow」網站。

相關文章連結

選擇排序法

開開心心每一天

生活艱辛，程式碼不易，但，不要忘記微笑！

以上是冒泡排序法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！