從排序學演算法( 2 ) — Bubble Sort

Photo by Kind and Curious on Unsplash

這次要來介紹的排序演算法是 Bubble Sort，之所以會叫這個可愛的名字是因為使用這個演算法會慢慢將元素移動到最右側，有點像是水中的泡泡慢慢往水面漂一樣，現在還無法領會沒關係，相信跟著步驟走過一遍就會了解這個名字為什麼這樣取了！

Bubble Sort

💡 兩兩一組依序進行比較，慢慢把數值大的元素換到陣列最右側

步驟：

1. 未分類陣列兩兩一組依序做比較
2. 若左側元素大於右側元素則互相交換位置，否則繼續進行比較
3. 一輪排序結束後若還沒完成整個陣列的排序則回到步驟1，反覆執行直到完成排序

陣列一開始為 const array = [67, 14, 28, 2, 35]

初始陣列

首先從最左邊開始兩兩一組進行比較，67 比較大，要和 14 交換位置

67 和 14 要交換位置

交換完後接著往下，換成 67 和 28 進行比較。67較大，和 28 交換位置

67 和 28 要交換位置

換好後再來是 67 和 2 交換位置

67 和 2 要交換位置

67 和 35 交換位置

67 和 35 要交換位置

交換好位置後如下圖，會發現只有 35 和 67 排序好，其他元素還沒排序完成，因此繼續從頭進行步驟 1

第一輪排序後陣列尚未排序完畢

14 比 28 小，不必更動位置

14 和 28 維持不動

28 比 2 小，兩個要交換位置

28 和 2 互換位置

此時第二輪的排序結束，再差一步陣列就快排序完了

第二輪排序結束，還差一點點就要結束了

14 和 2 再進行交換後，整個陣列就大功告成了

14 和 2 位置交換

整個陣列完成排序

程式碼：

Bubble Sort

時間複雜度：

Worst case: O(n²)

Best case: O(n)

如果陣列已經先排序好了，在第一輪兩兩比較時沒有任何 swap 就會提前結束排序

空間複雜度：O(1)

看著數值最大的元素隨著每次的排序慢慢移動到陣列最右邊，應該不難理解 Bubble Sort 這個名稱的由來了吧！

以上就是 Bubble Sort 的介紹，如果有興趣看 Selection Sort 的介紹可以點這裡，有任何問題或心得歡迎留言告訴我！