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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法之旅 | 選擇排序法

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

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