摘要：學堂碼匠本期繼續(xù)走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優(yōu)化假如序列的數(shù)據(jù)為使用上面的冒泡排序法進行排序，得到的結(jié)果肯定沒有問題，但是，待排序的序列是有序的，理論上是無需遍歷排序。

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

Tips：關(guān)于“算法”及“排序”的基礎知識，在此前“選擇排序法”中已詳細講解，可點擊文后的相關(guān)文章鏈接查看，在此不再贅述。

從序列頭部開始遍歷，兩兩比較，如果前者比后者大，則交換位置，直到最后將最大的數(shù)（本次排序最大的數(shù)）交換到無序序列的尾部，從而成為有序序列的一部分；
下次遍歷時，此前每次遍歷后的最大數(shù)不再參與排序；
多次重復此操作，直到序列排序完成。
由于在排序的過程中總是小數(shù)往前放，大數(shù)往后放，類似于氣泡逐漸向上漂浮，所以稱作冒泡排序。

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

由于待排序的序列只剩下一個數(shù)時已經(jīng)能夠確定順序，則無需進行排序，因此，排序次數(shù)為序列長度 – 1。

每次排序，序列中的多個數(shù)字要分別進行兩兩比較，多次的比較需要利用for語句來進行實現(xiàn)。該for循環(huán)嵌套于排序次數(shù)的for循環(huán)當中（形成雙for的嵌套）。

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

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

假如序列的數(shù)據(jù)為：[0, 1, 2, 3, 4, 5]；
使用上面的冒泡排序法進行排序，得到的結(jié)果肯定沒有問題，但是，待排序的序列是有序的，理論上是無需遍歷排序。
當前的算法不管初始的序列是否有序，都會進行遍歷排序，效率會比較低，因此需要優(yōu)化當前的排序算法。
在如下的算法中，引入一個swap變量，每一次排序之前初始化為false；若發(fā)生兩數(shù)交換位置，則將其設置為true。
在每次排序結(jié)束時候判斷swap是否為false，如果是，則說明序列已排序完成或者序列本身是有序序列，就不再進行下一次排序。
通過此方法，減少不必要的比較和位置交換，進一步提高算法的性能。

最佳狀態(tài)：待排序的序列本身是有序序列，排序次數(shù)根據(jù)優(yōu)化后的代碼，可以得出是n-1次，時間復雜度為O(n)；
最壞的情況：待排序的序列是逆序的，此時需要排序1 + 2 +3 ……(n - 1) = n(n – 1 )/2次，
時間復雜度為O(n^2)。

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

當相鄰元素相等時，并不需要交換位置，也就不會出現(xiàn)相同元素的前后順序發(fā)生改變，所以，是穩(wěn)定性排序。

時間復雜度，更準確的說該是描述一個算法在問題規(guī)模不斷增大時對應的時間增長曲線。所以，這些增長數(shù)量級并不是一個準確的性能評價，可以理解為一個近似值。（空間復雜度同理）
O(n2)表示當n很大的時候，復雜度約等于Cn2，C是某個常數(shù)，簡單說就是當n足夠大的時候，隨著n的線性增長復雜度將沿平方增長。
O(n)表示，n很大的時候復雜度約等于Cn，C是某個常數(shù)。簡言之：隨著n的線性增長，復雜度沿線性級別增長。
O(1)表示，n很大的時候，復雜度基本就不增長了。簡言之：隨著n的線性增長，復雜度不受n的影響，沿常數(shù)級別增長（此處的常數(shù)是1）。

Tips：圖中O(1)緊貼著X軸，并看不太清楚。
Tips：該圖來源于“Stack Overflow”網(wǎng)站。

算法之旅 | 選擇排序法

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

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