# 泡沫排序法(Bubble Sort)
應該是大部分人第一次接觸到的排序法。
## 作法
以升序泡沫排序法來說：將相鄰的元素兩兩比對，若左邊的數比右邊的數大，則將兩數交換，若沒有則換下一個元素對比，做完一輪之後序列中最大的數就會被排到最後一個位置，就像泡泡一樣慢慢冒出來，第一個冒出來的就是最大的泡泡。
### 舉例說明
比如說我今天有一陣列，我想將此陣列中的數**由小到大**排序：9 4 2 6 3 7 5
我先來對比 9 和 4，9 > 4所以將9和4做交換，此時陣列為：4 9 2 6 3 7 5
接著對比 9 2，我們發現9 > 2所以將9和2交換，此時陣列為：4 2 9 6 3 7 5
依此類推，後面我只將每次交換結果列出：
=> 4 2 6 9 3 7 5
=> 4 2 6 3 9 7 5
=> 4 2 6 3 7 9 5
=> 4 2 6 3 7 5 9
經過一輪排序後，此時結果為 4 2 6 3 7 5 9
但你會發現這並不是由小到大排序啊？
沒錯，當一輪結束後陣列沒有達到理想狀態時，我們還需要再繼續排序：
4 2 6 3 7 5 9
=> 2 4 6 3 7 5 9
=> 2 4 3 6 7 5 9
=> 2 4 3 6 5 7 9
再繼續下一輪
2 4 3 6 5 7 9
=> 2 3 4 6 5 7 9
=> 2 3 4 5 6 7 9
此時看起來排序已經結束了，但其實並沒有，每一輪排序我們會將一個數定下來，比如說第一輪我們會將 9 擺到最後因為它是陣列中最大的元素，第二輪是把 7 陣列中次大的元素定下來，第三輪則是把 6 陣列中第三大的元素定下來...以此類推。
由此我們可以得知，使用泡沫排序法一共需要進行 **n - 1** 輪(n為元素個數)。
### 優化
因為排序過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換就說明序列有序，就像我們前面的例子，其實在第三輪的時候就已經排序完畢，但是卻要進行六輪排序，因此要在此排序過程中設置一個標誌flag判斷元素是否進行過交換，從而減少不必要的比較。
### 規則小結
1. 一共進行 `陣列大小-1` 輪的比較
2. 每一趟排序的次數在逐漸減少
3. 如果我們發現在某趟排序中沒有發生一次交換，可以提前結束泡沫排序。
## 程式碼實現
```java=
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {9,4,2,6,3,7,5};
System.out.println("原陣列: "+Arrays.toString(arr));
//泡沫排序，將最大的數排在最後
int temp = 0; //臨時變數
for(int j = 0; j < arr.length -1; j++) {
for(int i = 0; i < arr.length - 1 - j; i++) {
//如果當前的數比後一位的數大則交換
if(arr[i] > arr[i+1]) {
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
System.out.println("第 "+(j+1)+" 輪排序: "+Arrays.toString(arr));
}
}
}
```
output
```java=
原陣列: [9, 4, 2, 6, 3, 7, 5]
第 1 輪排序: [4, 2, 6, 3, 7, 5, 9]
第 2 輪排序: [2, 4, 3, 6, 5, 7, 9]
第 3 輪排序: [2, 3, 4, 5, 6, 7, 9]
第 4 輪排序: [2, 3, 4, 5, 6, 7, 9]
第 5 輪排序: [2, 3, 4, 5, 6, 7, 9]
第 6 輪排序: [2, 3, 4, 5, 6, 7, 9]
```
時間複雜度為 O($n^2$)，因為是兩個for迴圈。
### 優化
從上面的輸出結果可以看到，第三輪到第六輪的結果都相同，所以我們需要進行優化，一旦排序完便不再繼續排序。
定義一個變數 flag 預設為 false
```java=
boolean flag = false; //標示變數，表示是否進行交換
```
一旦交換則將 flag設為true，若一輪排序後flag仍為false代表這一輪中都沒有交換過，即結束排序。
```java=
for(int j = 0; j < arr.length -1; j++) {
for(int i = 0; i < arr.length - 1 - j; i++) {
//如果當前的數比後一位的數大則交換
if(arr[i] > arr[i+1]) {
flag = true;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
if(!flag) { //在一輪排序中一次交換都沒有發生過
break;
} else {
flag = false; //重置flag進行下一輪排序
}
System.out.println("第 "+(j+1)+" 輪排序: "+Arrays.toString(arr));
}
```
output
```java=
原陣列: [9, 4, 2, 6, 3, 7, 5]
第 1 輪排序: [4, 2, 6, 3, 7, 5, 9]
第 2 輪排序: [2, 4, 3, 6, 5, 7, 9]
第 3 輪排序: [2, 3, 4, 5, 6, 7, 9]
```
接著來測試一把若有八萬筆資料排序要花多少時間：
```java=
public static void main(String[] args) {
// int arr[] = {7,2,5,4,5,8,7};
// System.out.println("原陣列: "+Arrays.toString(arr));
int arr[] = new int[80000];
for(int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random() * 80000);
}
Instant startTime = Instant.now();
bubbleSort(arr);
Instant endTime = Instant.now();
System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}
```
output
```java=
共耗時：7015 毫秒
共耗時：7012 毫秒
共耗時：7331 毫秒
共耗時：7062 毫秒
```
還滿穩定的，測了四次都是差不多 7 秒多。
## 時間複雜度
假設今天要對一陣列使用泡沫排序法由小到大排序。
### 最佳：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^)
Sign in with Wallet
Connect another wallet