冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
**1、算法思想**
1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
3、 針對所有的元素重復以上的步驟，除了最后一個。
4、 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。
**2、代碼實現**
~~~
public static void bubbleSort(int[] source) {
int length = source.length;
for (int i = 0; i < length - 1; i++) { // N個數需N-1趟,每趟完成之后,較大元素將冒到數組最末端
for (int j = 0; j < length - 1 - i; j++) { // 每趟需要比較N-i次比較
if (source[j] > source[j + 1]) {
swap(source, j, j + 1);
}
// System.out.print("\n外循環第" + (i + 1) + "次,內循環第" + (j + 1) + "次,排序結果：");
// printArray(source);
}
System.out.println("");
}
}
~~~
**3、算法分析**
### 算法穩定性
冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。
**4、算法改進**
對冒泡排序常見的改進方法是加入一標志性變量exchange，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程。
本文再提供以下兩種改進算法：
1）．設置一標志性變量pos,用于記錄每趟排序中最后一次進行交換的位置。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。
改進后算法如下:
~~~
/**
* 設置一標志性變量pos,用于記錄每趟排序中最后一次進行交換的位置。
*
* 由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。
*/
public static void bubbleSort2(int[] source) {
int high = source.length - 1;
while (high > 0) { // high=0時證明最后一次進行交換的位置為0
int pos = 0;// 每趟開始，無記錄交換
for (int i = 0; i < high; i++) {
if (source[i] > source[i + 1]) {
swap(source, i, i + 1);
pos = i; // 有交換則令pos=i
}
}
high = pos; // 每趟for循環結束，pos、length變更一次
// System.out.println(high);
}
}
~~~
2）．傳統冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者)?,?從而使排序趟數幾乎減少了一半。
改進后的算法實現為:
~~~
/**
* 每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大值和最小值),
*
* 從而使排序趟數幾乎減少了一半。
*/
public static void bubbleSort3(int[] source) {
int low = 0;
int high = source.length - 1;
while (low < high) {
for (int i = low; i < high; i++) { // 正向找最大
if (source[i] > source[i + 1]) {
swap(source, i, i + 1);
}
}
high--; // 一次for循環結束，最大數冒出
for (int i = high; i > low; i--) { // 逆向找最小
if (source[i] < source[i - 1]) {
swap(source, i, i - 1);
}
}
low++;
}
}
~~~
swap
~~~
private static void swap(int[] source, int x, int y) {
int temp = source[x];
source[x] = source[y];
source[y] = temp;
}
~~~
源碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/BubbleSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/BubbleSort.java)
