冒泡排序法

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”網站。

相關文章鏈接

選擇排序法

開開心心每一天

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

版權聲明：該圖來自“【美】莉茲·克裡莫 (author)”的書籍《你今天真好看》