算法描述:

1.臨近的數(shù)字兩兩進行比較,按照從小到大順序進行交換,直到到達有序區(qū)域。
2.如果未排序區(qū)域非空，重復(fù)步驟1。

舉個例子：以下是{5, 1, 12, -5, 16}的排序過程

排序過程

復(fù)雜度分析

時間：最優(yōu)平均和最差都是O(n2)
空間：O(1).
是穩(wěn)定的排序算法。

在前文的描述中，可以看到對于已經(jīng)排序的數(shù)列而言，即最優(yōu)情況下，O(n2)次的比較是不必要的。如果在某趟遍歷過程中并沒有發(fā)生任何的交換，則可以認為數(shù)列已經(jīng)有序，程序可以終止。查看優(yōu)化后的冒泡排序代碼請參考2。

冒泡排序代碼(未優(yōu)化)

public void bubbleSort(int[] arr) {
    int temp;
    for (int j = arr.length - 1; j > 0; j--) {
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

冒泡排序代碼(優(yōu)化)

public void  bubbleSort( int [] arr) {
       boolean swapped = true;
       int j = 0;
       int tmp;
       while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < arr.length - j; i++) {                                       
                  if (arr[i] > arr[i + 1]) {                          
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }                
      }
}