知識星球（點選上方公號，快速關註我們）
來源：靜默虛空
www.cnblogs.com/jingmoxukong/p/4302718.html
氣泡排序是一種交換排序。
什麼是交換排序呢？
交換排序：兩兩比較待排序的關鍵字，並交換不滿足次序要求的那對數，直到整個表都滿足次序要求為止。
演演算法思想
它重覆地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重覆地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，故名。
假設有一個大小為 N 的無序序列。氣泡排序就是要每趟排序過程中透過兩兩比較，找到第 i 個小（大）的元素，將其往上排。
圖-氣泡排序示例圖
以上圖為例，演示一下氣泡排序的實際流程：
假設有一個無序序列 { 4. 3. 1. 2, 5 }
第一趟排序：透過兩兩比較，找到第一小的數值 1 ，將其放在序列的第一位。
第二趟排序：透過兩兩比較，找到第二小的數值 2 ，將其放在序列的第二位。
第三趟排序：透過兩兩比較，找到第三小的數值 3 ，將其放在序列的第三位。
至此，所有元素已經有序，排序結束。
要將以上流程轉化為程式碼，我們需要像機器一樣去思考，不然編譯器可看不懂。
假設要對一個大小為 N 的無序序列進行升序排序（即從小到大）。
(1) 每趟排序過程中需要透過比較找到第 i 個小的元素。
所以，我們需要一個外部迴圈，從陣列首端(下標 0) 開始，一直掃描到倒數第二個元素（即下標 N – 2) ，剩下最後一個元素，必然為最大。
(2) 假設是第 i 趟排序，可知，前 i-1 個元素已經有序。現在要找第 i 個元素，只需從陣列末端開始，掃描到第 i 個元素，將它們兩兩比較即可。
所以，需要一個內部迴圈，從陣列末端開始（下標 N – 1），掃描到 (下標 i + 1)。
核心程式碼
public void bubbleSort(int[] list) {
int temp = 0; // 用來交換的臨時數
// 要遍歷的次數
for (int i = 0; i list.length - 1; i++) {
// 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把陣列中第i小的數放在第i個位置上
for (int j = list.length - 1; j > i; j--) {
// 比較相鄰的元素，如果前面的數大於後面的數，則交換
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
}
}
System.out.format("第 %d 趟： ", i);
printAll(list);
}
}
氣泡排序演演算法的效能
時間複雜度
若檔案的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數C和記錄移動次數M均達到最小值：Cmin = N – 1, Mmin = 0。所以，氣泡排序最好時間複雜度為O(N)。
若初始檔案是反序的，需要進行 N -1 趟排序。每趟排序要進行 N – i 次關鍵字的比較(1 ≤ i ≤ N – 1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：
Cmax = N(N-1)/2 = O(N2)
Mmax = 3N(N-1)/2 = O(N2)
氣泡排序的最壞時間複雜度為O(N2)。
因此，氣泡排序的平均時間複雜度為O(N2)。
總結起來，其實就是一句話：當資料越接近正序時，氣泡排序效能越好。
演演算法穩定性
氣泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。
所以相同元素的前後順序並沒有改變，所以氣泡排序是一種穩定排序演演算法。
對氣泡排序常見的改進方法是加入標誌性變數exchange，用於標誌某一趟排序過程中是否有資料交換。
如果進行某一趟排序時並沒有進行資料交換，則說明所有資料已經有序，可立即結束排序，避免不必要的比較過程。
核心程式碼
// 對 bubbleSort 的最佳化演演算法
public void bubbleSort_2(int[] list) {
int temp = 0; // 用來交換的臨時數
boolean bChange = false; // 交換標誌
// 要遍歷的次數
for (int i = 0; i list.length - 1; i++) {
bChange = false;
// 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把陣列中第i小的數放在第i個位置上
for (int j = list.length - 1; j > i; j--) {
// 比較相鄰的元素，如果前面的數大於後面的數，則交換
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
bChange = true;
}
}
// 如果標誌為false，說明本輪遍歷沒有交換，已經是有序數列，可以結束排序
if (false == bChange)
break;
System.out.format("第 %d 趟： ", i);
printAll(list);
}
}
JAVA版本
程式碼實現
1 package notes.javase.algorithm.sort;
2
3 import java.util.Random;
4
5 public class BubbleSort {
6
7 public void bubbleSort(int[] list) {
8 int temp = 0; // 用來交換的臨時數
9
10 // 要遍歷的次數
11 for (int i = 0; i list.length - 1; i++) {
12 // 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把陣列中第i小的數放在第i個位置上
13 for (int j = list.length - 1; j > i; j--) {
14 // 比較相鄰的元素，如果前面的數大於後面的數，則交換
15 if (list[j - 1] > list[j]) {
16 temp = list[j - 1];
17 list[j - 1] = list[j];
18 list[j] = temp;
19 }
20 }
21
22 System.out.format("第 %d 趟： ", i);
23 printAll(list);
24 }
25 }
26
27 // 對 bubbleSort 的最佳化演演算法
28 public void bubbleSort_2(int[] list) {
29 int temp = 0; // 用來交換的臨時數
30 boolean bChange = false; // 交換標誌
31
32 // 要遍歷的次數
33 for (int i = 0; i list.length - 1; i++) {
34 bChange = false;
35 // 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把陣列中第i小的數放在第i個位置上
36 for (int j = list.length - 1; j > i; j--) {
37 // 比較相鄰的元素，如果前面的數大於後面的數，則交換
38 if (list[j - 1] > list[j]) {
39 temp = list[j - 1];
40 list[j - 1] = list[j];
41 list[j] = temp;
42 bChange = true;
43 }
44 }
45
46 // 如果標誌為false，說明本輪遍歷沒有交換，已經是有序數列，可以結束排序
47 if (false == bChange)
48 break;
49
50 System.out.format("第 %d 趟： ", i);
51 printAll(list);
52 }
53 }
54
55 // 列印完整序列
56 public void printAll(int[] list) {
57 for (int value : list) {
58 System.out.print(value + " ");
59 }
60 System.out.println();
61 }
62
63 public static void main(String[] args) {
64 // 初始化一個隨機序列
65 final int MAX_SIZE = 10;
66 int[] array = new int[MAX_SIZE];
67 Random random = new Random();
68 for (int i = 0; i 69 array[i] = random.nextInt(MAX_SIZE);
70 }
71
72 // 呼叫氣泡排序方法
73 BubbleSort bubble = new BubbleSort();
74 System.out.print("排序前: ");
75 bubble.printAll(array);
76 // bubble.bubbleSort(array);
77 bubble.bubbleSort_2(array);
78 System.out.print("排序後: ");
79 bubble.printAll(array);
80 }
81 }
執行結果
排序前： 2 9 9 7 1 9 0 2 6 8
第 0 趟： 0 2 9 9 7 1 9 2 6 8
第 1 趟： 0 1 2 9 9 7 2 9 6 8
第 2 趟： 0 1 2 2 9 9 7 6 9 8
第 3 趟： 0 1 2 2 6 9 9 7 8 9
第 4 趟： 0 1 2 2 6 7 9 9 8 9
第 5 趟： 0 1 2 2 6 7 8 9 9 9
排序後： 0 1 2 2 6 7 8 9 9 9
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：
http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
