為何叫冒泡

越大的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）唠叛，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣浪箭，故名“冒泡排序”控漠。

原理

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大全肮，就交換他們兩個(gè)敞咧。
2. 對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)辜腺。在這一點(diǎn)休建，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 針對(duì)所有的元素重復(fù)以上的步驟哪自，除了最后一個(gè)丰包。
4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟禁熏，直到?jīng)]有任何一對(duì)數(shù)字需要比較壤巷。

時(shí)間復(fù)雜度分析

• 最好的時(shí)間復(fù)雜度
  若數(shù)組的順序是正序的，一趟掃描即可完成排序瞧毙。所需的關(guān)鍵字比較次數(shù)C和記錄移動(dòng)的次數(shù)M都是最小的值胧华，如：arrays{1,2,3,4,5,6}
  和記錄移動(dòng)次數(shù)
  
  故：最好的時(shí)間復(fù)雜度O(n)
• 最壞的時(shí)間復(fù)雜度分析
  若數(shù)組的順序是反序的，需要進(jìn)行n-1趟排序宙彪，每趟需要n-1次的比較（1<=i<n-1）矩动，每次需要移動(dòng)記錄三次來(lái)交互位置，所以释漆，比較和移動(dòng)次數(shù)均達(dá)到最大值：
  
  
  故：冒泡排序的最壞時(shí)間復(fù)雜度為：
  
• 平均時(shí)間復(fù)雜度分析
  所以：冒泡排序總的平均時(shí)間復(fù)雜度為：
  

java代碼實(shí)現(xiàn)（一般寫(xiě)法）

private static void sort(int[] values) {
        int temp;
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length - 1 - i; j++) {
                if (values[j] > values[j + 1]) {
                    temp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = temp;
                }
            }
        }
    }

java代碼實(shí)現(xiàn)（優(yōu)化悲没，存在有序情況）

/**
     * 冒泡排序
     * 存在有序情況定義boolean類(lèi)型，如果沒(méi)有交換表示是有序的
     * @param values
     */

   private static void bubbleSort(int[] values) {
        boolean sorted = true;
        int temp;
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length - 1 - i; j++) {
                if (values[j] > values[j + 1]) {
                    temp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = temp;
                    sorted = false;
                }
            }
            if (sorted) {
                break;
            }
        }
    }

測(cè)試

 public static void main(String[] args) {
        int[] arrays = {1, 4, 3, 45, 8, 10};
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

[1, 3, 4, 8, 10, 45]

Process finished with exit code 0