演算法從入門到「放棄」（6）- 冒泡排序
演算法從入門到「放棄」（6）- 冒泡排序
來自專欄 AnotherWorld
1 人贊了文章
本系列文章
演算法從入門到「放棄」（1）- 什麼是演算法？
演算法從入門到「放棄」（2）- 分而治之和解決循環
排序系列
1. 演算法從入門到「放棄」（3）- 快速排序
2. 演算法從入門到「放棄」（4）- 插入排序
3. 演算法從入門到「放棄」（5）- 計數排序
本文提煉
冒泡排序演算法，一種通過交換數據元素位置來進行排序的交換排序演算法。
什麼是冒泡排序？
定義來自於維基百科，冒泡排序，Bubble Sort.
冒泡排序，有時被稱為「下沉排序」(sinking sort)，是一種簡單的排序演算法，它反覆地遍歷列表進行排序，遍歷過程中比較每一對相鄰的項，如果它們的順序是相反的，則交換它們。對列表的遍歷是持續進行的，一直到列表變成有序，不需要交換為止。該演算法是一種比較排序，它以更小或更大的元素（根據實際情況而定）「冒泡」到列表頂部的方式命名。該演算法的優點是很簡單，通俗易懂；但對於大多數問題來說，它太費時間且不切實際。如果輸入列表中大部分元素都是有序的，只有一些很少的無序元素，那麼氣泡排序是可行的。
簡而言之，我們假設要求是把輸入數組中的元素按照從小到大排好序；那麼從一個列表的頭部開始，比較兩個相鄰的元素，如果第一個比第二大，則交換它們的位置，如果第二個比第一個大，就不用管它們；接著比較第二個和第三個，第三個和第四個...直到倒數第二個和倒數最後一個；第一遍結束的時候，我們至少可以保證最後一個元素是最大的。然後再繼續重複這個過程（第二遍遍歷的時候可以加上「保證倒數第二個元素是第二大的」，第三遍遍歷的時候可以加上「保證倒數第三個元素是第三大的」......），直到列表中所有的元素都是有序，從小到大的。
基本思想
輸入：一系列的無序元素（比如說，數字）組成的輸入數組A
輸出：冒泡排序的經過比較通俗易懂，就像我在什麼是冒泡排序中介紹里說的一樣，我們假設要求是把輸入數組中的元素按照從小到大排好序；那麼從一個列表的頭部開始，比較兩個相鄰的元素，如果第一個比第二大，則交換它們的位置，如果第二個比第一個大，就不用管它們；接著比較第二個和第三個，第三個和第四個...直到倒數第二個和倒數最後一個；第一遍結束的時候，我們至少可以保證最後一個元素是最大的。然後再繼續重複這個過程（第二遍遍歷的時候可以加上「保證倒數第二個元素是第二大的」，第三遍遍歷的時候可以加上「保證倒數第三個元素是第三大的」......），直到列表中所有的元素都是有序，從小到大的。
結果：輸出數組B，裡面包含的元素都是A 中的但是已經按照要求拍好了順序（比如說，從小到大）
圖解
評價演算法好壞
分類：排序演算法
目標數據結構：數組
最壞時間複雜度：比較部分O(n^2)，交換部分O(n^2)；總體O(n^2)
最優時間複雜度：比較部分O(n)，交換部分O(1)；總體O(n) 【這裡解釋一下，最好情況也就是原本的輸入數組A 裡面的元素就是符合條件排好序了，只需要遍歷一遍就可以了】
平均時間複雜度：比較部分O(n^2)，交換部分O(n^2)；總體O(n^2)
最壞空間複雜度：O(1)
實例分析
假設現在有輸入數組 A{6,5,3,1,8,7,2,4}
第一遍遍歷，6和5對比，6比5大，所以交換位置；6和3對比，6比3大，再次交換位置；6和1比較，6比1大，交換位置；現在數組是{5,3,1,6,8,7,2,4}. 6和8對比，6比8小，不變；8和7對比，8比7大，交換位置；8和2對比，交換位置；8和4對比，交換位置；第一遍遍歷結果是{5,3,1,6,7,2,4,8}. 我們找出了最大值是8.
第二遍遍歷，過程和上述一樣，我們找出了第二大的值是7.
第三遍遍歷，過程和上述一樣，我們找出了第三大的值是6.
......
第八遍遍歷，過程和上述一樣，我們找出了最小的值是1.
至此，我們得到了輸出數組B{1,2,3,4,5,6,7,8}
流程展示圖
代碼展示
偽代碼
偽代碼來源：Bubble sort - Algorithmist
// 假設我們有一個array 名字是a，尺寸大小是nswapped = true //設定一個flag, 一開始是正確的 while swapped //開始交換循環 swapped = false for j from 0 to n - 1 //從0到n-1 if a[j] > a[j + 1] //如果前一個數大於後一個數 swap( a[j], a[j + 1] ) //交換兩個數的位置 swapped = true
優化？
1. 每次遍歷，都不需要考慮已經確定排序好的數。比如說，第一次遍歷後，我們知道最後一個數已經確定了，那麼最後一個數在下次遍歷就不需要考慮了；第二次便利後，倒數第二個數和倒數第一個數就在第三次遍歷中不需要被考慮了.....也就是說，第i 次遍歷後，倒數第i 個數及其之後的數都不需要在i+1 次遍歷中被考慮。
偽代碼
// 假設我們有一個array 名字是a，尺寸大小是nfor i from 1 to n //還是會有n 遍遍歷 swaps = 0 for j from 0 to n - i //常規交換步驟 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) swaps = swaps + 1 if swaps = 0 //當swaps 是0，退出該遍歷即可 break
2.
一個小小的改進就可以了。每次遍歷，我們都去追蹤數組中的元素是否交換了位置；如果沒有，我們就可以放心大膽地認為序列裡面的元素已經是有序排列好了的。
A small improvement can be made if each pass you keep track of whether or not an element was swapped. If not, you can safely assume the list is sorted.引自 Bubble sort - Algorithmist
偽代碼
// 假設我們有一個array 名字是a，尺寸大小是nfor i from 2 to n //第一遍遍歷我們追蹤不了元素是否交換了位置，要從第二遍開始進行對比 swaps = 0 for j from 0 to n - 2 //只追蹤到倒數第二大的數 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) swaps = swaps + 1 if swaps = 0 break
在下一篇文章中，將著重講的是選擇排序演算法。
如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！
推薦閱讀：
