分類 -------------- 內部比較排序
數(shù)據(jù)結構 ---------- 數(shù)組
最差時間復雜度 ---- O(n^2)
最優(yōu)時間復雜度 ---- 如果能在內部循環(huán)第一次運行時,使用一個旗標來表示有無需要交換的可能,可以把最優(yōu)時間復雜度降低到O(n)
平均時間復雜度 ---- O(n^2)
所需輔助空間 ------ O(1)
穩(wěn)定性 ------------ 穩(wěn)定

原理

???????它重復地走訪過要排序的元素，依次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到?jīng)]有元素再需要交換，排序完成。這個算法的名字由來是因為越小(或越大)的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

步驟

1. 比較相鄰的元素，如果前一個比后一個大，就把它們兩個調換位置。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
3. 針對所有的元素重復以上的步驟，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

代碼實現(xiàn)

public class BubbleSort {
    void sort(Integer[] array){
          // 每次最大元素就像氣泡一樣"浮"到數(shù)組的最后
          for (int i = 0; i < array.length - 1 ; i++){
              // 依次比較相鄰的兩個元素,使較大的那個向后移
            for(int j = 0; j < array.length - 1 - i;j++){
                // 判斷是否當前位置的數(shù)值大于下一個位置的數(shù)值，如果條件改成A[i] >= A[i + 1],則變?yōu)椴环€(wěn)定的排序算法
                if (array[j] > array[j+1]){
                    //交換
                    Tool.exchange(array,j,j+1);
                }
            }
          }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        BubbleSort sort = new BubbleSort();
        sort.sort(a);
        System.out.println("array by BubbleSort is " + Tool.arrayToString(a));
    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

實現(xiàn)結果：

array by BubbleSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]