# Bubble Sort 泡沫排序法 + 是 **O(n^2)** 的排序演算法，也是排序法的始祖。 + 左右 **相鄰** 的元素如果是在錯誤的位置，就交換他們的位置。 + 因為浪費較多資源，並不是很常被使用的排序演算法，但作為教育用途非常容易理解。 + 正確的值會一路被推到它該出現的位置，有點像浮上去的泡沫，因此被稱為 Bubble Sort。 &emsp; ``` Bubble Sort 的原理為： 從第一筆資料開始，逐一比較相鄰兩筆資料，若不符合排序則做交換，反之則不動，接者前進一筆直到陣列結束，這樣算一個回合。 第 1 回合結束時，可以確保 最後一筆 資料是正確的； 第 2 回合再從第一筆開始重複動作，可以確保 倒數第二筆 會是正確的，整體要做 整個陣列長度-1 個回合。 有些寫法是先推到第一筆、第二筆這樣下去，端看程式怎麼設計。 ```  ``` python arr = [1, 5, 2, 99, -7, 7, 15, -3, 0, -11] def bubbleSort(arr): for i in range(len(arr)-1): for j in range(1, len(arr)-i): if arr[j-1] > arr[j]: arr[j-1], arr[j] = arr[j], arr[j-1] return arr # [-11, -7, -3, 0, 1, 2, 5, 7, 15, 99] ``` ## 介紹 在泡沫排序法中： **i** 代表需要排序的回合，也就是從整體資料長度-1，就是 `len(arr)-1` **j** 代表陣列 **相鄰** 位置的資料，在第一個回合 ( i = 0 )，最大值會一路推到最後一格，i = 1 時第二大值會被推到倒數第二格， 所以迴圈的終止值放 ```len(arr) - i``` ```if arr[j-1] > arr[j]:``` 如果左邊數字大於相鄰的右邊數字 ```arr[j-1], arr[j] = arr[j], arr[j-1]``` 就交換兩個數字的位置 因此這是個 **由小排到大** 的陣列，如果要由大排到小，就要改成 ```if arr[j-1] < arr[j]:``` ## BigO 泡沫排序對 *n* 個項目需要 O(n^2) 的比較次數 因為使用到雙重迴圈，運用到資料長度平方的運算邏輯，因此不是效率較佳的演算法 Worst Case Performance: O(n^2) Best Case Performance: O(n) Average Performance: O(n^2) &emsp; ## 參考資料： [[演算法] 氣泡排序法(Bubble Sort)](http://notepad.yehyeh.net/Content/Algorithm/Sort/Bubble/1.php) [【Day21】[演算法]-排序Sort & 氣泡排序法Bubble Sort](https://ithelp.ithome.com.tw/articles/10276184) [泡沫排序 - 維基百科](https://zh.m.wikipedia.org/zh-tw/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F) Udemy - 資料結構與演算法 (JavaScript)