排序演算法 | 泡沫排序
泡沫排序（英語：Bubble Sort）又稱為泡式排序，是一種簡單的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名「泡沫排序」。
泡沫排序演算法的運作如下：
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
- 針對所有的元素重複以上的步驟，除了最後一個。
- 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
使用泡沫排序為一列數字進行排序的過程：
實作範例(Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| @Test
public void bubbleSort() {
int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
int count = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
count++;
}
}
System.out.println(Arrays.toString(arr));
System.out.println("一共比較了:" + count + "次");
}
|
結果：
1
2
| [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比較了:105次
|
這段程式相信大家都能夠寫出來，一般泡沫排序也就是這樣寫。但是這段程式有個缺點，就是當排序過程中已經將數組元素排序完成，但此時它仍然會去比較，這就做了無用功了，所以我們可以通過一個boolean變量來優化這段代，上面的程式中我們已經得出了比較次數為105次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| @Test
public void bubbleSort() {
int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
int count = 0;
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
count++;
}
if(flag) {
break;
}
}
System.out.println(Arrays.toString(arr));
System.out.println("一共比較了:" + count + "次");
}
|
結果：
1
2
| [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比較了:95次
|
我們首先在開始循環時定義了一個boolean變量為true，然後如果元素之間進行了交換，就將值置為false。所以，我們就可以通過這個boolean變量來判斷是否有元素進行了交換。如果boolean變量為true，則證明沒有元素進行交換，那麼久說明此時的數組元素已經完成排序，那麼跳出外層循環即可，否則就繼續排序。通過結果也可以看出，比較次數確實是減少了很多。
註：以上參考了
維基百科-泡沫排序
演算法筆記
程式员必须掌握的核心算法有哪些？
程式员那些必须掌握的排序算法(上)
程式员那些必须掌握的排序算法(下)
