這是數(shù)學(xué)

本文：https://blog.csdn.net/CrazyApes/article/details/117361637

冒泡排序 （Bubble Sort）

這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣蓝仲，故名“冒泡排序”。

基本思想

兩個數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來凛驮。

算法原理

冒泡排序算法的原理如下：

• 比較相鄰的元素约郁。如果第一個比第二個大，就交換他們兩個钠绍。
• 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對花沉。在這一點柳爽，最后的元素應(yīng)該會是最大的數(shù)。
• 針對所有的元素重復(fù)以上的步驟碱屁，除了最后一個磷脯。
• 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較娩脾。

冒泡排序.gif

實現(xiàn)方式

    /**
     * Java
     * 冒泡排序
     *
     * @param arr data source
     */
    public static void bubbleSort(int arr[]) {
        if (arr == null) {
            return;
        }
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

時間復(fù)雜度 O(n^2)

若文件的初始狀態(tài)是正序的赵誓，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動次數(shù)M均達到最小值：
C min = n - 1
M min = 0;
所以，冒泡排序最好的時間復(fù)雜度為O(n)俩功。

若初始文件是反序的隘冲，需要進行 n - 1 趟排序。每趟排序要進行 n - i 次關(guān)鍵字的比較(1 ≤ i ≤ n-1)绑雄，且每次比較都必須移動記錄三次來達到交換記錄位置展辞。
在這種情況下，比較和移動次數(shù)均達到最大值：
C max = n (n - 1) / 2 = O(n^2)
M max = 3n(n - 1) / 2 = O(n^2);
冒泡排序的最壞時間復(fù)雜度為O(n^2)万牺。

綜上罗珍，因此冒泡排序總的平均時間復(fù)雜度為O(n^2)。

空間復(fù)雜度 O(1)

冒泡排序排序過程中需要一個臨時變量進行兩兩交換脚粟，所需要的額外空間為1覆旱，因此空間復(fù)雜度為O(1)。

算法穩(wěn)定性 -- 穩(wěn)定

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)核无。
比較是相鄰的兩個元素比較扣唱，交換也發(fā)生在這兩個元素之間。
所以团南，如果兩個元素相等噪沙，是不會再交換的；
如果兩個相等的元素沒有相鄰吐根，那么即使通過前面的兩兩交換把兩個相鄰起來正歼，這時候也不會交換，
所以相同元素的前后順序并沒有改變拷橘，
所以冒泡排序是一種穩(wěn)定排序算法局义。

優(yōu)化

針對問題：
數(shù)據(jù)的順序排好之后，冒泡算法仍然會繼續(xù)進行下一輪的比較冗疮，直到arr.length-1次萄唇，后面的比較沒有意義的。

方案：
設(shè)置標(biāo)志位flag术幔，如果發(fā)生了交換flag設(shè)置為true另萤；如果沒有交換就設(shè)置為false。
這樣當(dāng)一輪比較結(jié)束后如果flag仍為false特愿，即：這一輪沒有發(fā)生交換仲墨，說明數(shù)據(jù)的順序已經(jīng)排好勾缭，沒有必要繼續(xù)進行下去揍障。

    /**
     * Java
     * 冒泡排序
     *
     * @param arr data source
     */
    public static void bubbleSort(int arr[]) {
        if (arr == null) {
            return;
        }
        int temp;//臨時變量
        boolean flag;//是否交換的標(biāo)志
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            // 每次遍歷標(biāo)志位都要先置為false，才能判斷后面的元素是否發(fā)生了交換
            flag = false;
            for (int j = 0; j < length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;    // 只要有發(fā)生了交換俩由，flag就置為true
                }
            }
            // 判斷標(biāo)志位是否為false毒嫡，如果為false，說明后面的元素已經(jīng)有序，就直接break
            if (!flag) break;
        }
    }

參考

百度百科 - 冒泡排序 (https://baike.baidu.com/item/冒泡排序)

值得收藏的十大經(jīng)典排序算法 (https://www.toutiao.com/a6593273307280179715)