# 氣泡排序 (Bubble sort)

## 簡介

氣泡排序法是一種比較基礎的算法，主要是透過比較前後兩數字的大小，並且兩兩交換，來完成排序動作。

冒泡排序法為**穩定排序法**。

## 算法

### 詳細步驟

1. 氣泡排序所需要的排序 **總回合數** 為 ***n - 1***
2. 透過創建兩個前後指針，來進行比對，如果前面的數字比後面的數字還要大，就把兩的數字對調

### 優化算法

在進行氣泡排序時，有時候會遇到中途已經排序好了(亦即這一輪前後比對的時候，前面的數字都比後面的數字來得小，沒有進行交換，這時候就可以判定已經排序完成)，但**總回合數**還沒有跑完的情況，
這時候就加入一個 **旗標** 來優化時間複雜度。

設定旗標初始值為 **False** ，只要在比較的時候，判斷這一回合如果有進行數字交換的話，就把旗標值設定為 **True** ，這樣在這一回合比較完成以後，判斷旗標為 **False** 的話，直接跳出迴圈即可，即可避免掉此類情況。

### 優化過後的詳細步驟

1. 氣泡排序所需要的排序**總回合數**為 ***n - 1***
2. 加入旗標，設定初始值為 **False**
3. 透過創建兩個前後指針，來進行比對，如果前面的數字比後面的數字還要大，就把兩的數字對調，並且設置旗標值為 **True**
4. 在總回合的迴圈裡(n-1)，判斷旗標值是否為 **True**，如果是的話即跳出迴圈，結束排序

## 時間複雜度
假設今天要對一陣列使用泡沫排序法由小到大排序。

### 最佳：O(n)
當資料順序恰好為由小到大時，第一輪排序未進行任何置換則提前結束。
### 平均：O(n^2^)
第 n 筆資料，平均需要比較 `(n-1)/2` 次
### 最差：O(n^2^)
當資料順序恰好為由大到小時，每輪分別執行：n-1、n-2、.. 、1次，`(n-1)+(n-2)+...+1 = n(n-1)/2` => O(n^2^)

## 參考資料
- [氣泡排序詳解](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FHyyCFRj9d)