交換排序演算法之冒泡排序

八種排序演算法可以按照如圖分類，本文主要介紹冒泡排序，

交換排序

所謂交換，就是序列中任意兩個元素進行比較，根據比較結果來交換各自在序列中的位置，以此達到排序的目的，

冒泡排序

冒泡排序是一種簡單的交換排序演算法，以升序排序為例，其核心思想是：

1. 從第一個元素開始，比較相鄰的兩個元素，如果第一個比第二個大，則進行交換，
2. 輪到下一組相鄰元素，執行同樣的比較操作，再找下一組，直到沒有相鄰元素可比較為止，此時最后的元素應是最大的數，
3. 除了每次排序得到的最后一個元素，對剩余元素重復以上步驟，直到沒有任何一對元素需要比較為止，

用 Java 實作的冒泡排序如下

/**
 * 冒泡排序常規版
 *
 * <p>沒有經過任何優化操作的版本
 * @param arr 待排序的整型陣列
 * @return 比較次數
 */
public static int bubbleSortOpt1(int[] arr) {

    if (arr == null) {
        throw new NullPointerException();
    } else if (arr.length < 2) {
        return 0;
    }

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

演算法優化

現在有個問題，假如待排序陣列是 2、1、3、4、5 這樣的情況，按照上述代碼實作，第一次回圈即可得出正確結果，但回圈并不會停止，而是繼續執行，直到結束為止，顯然，之后的回圈遍歷是沒有必要的，

為了解決這個問題，我們可以設定一個標志位，用來表示當前次回圈是否有交換，如果沒有，則說明當前陣列已經完全排序，

/**
 * 冒泡排序優化第一版
 *
 * <p>設定了一個標志位，用來表示當前次回圈是否有交換，如果沒有，則說明當前陣列已經完全排序
 * @param arr 待排序的整型陣列
 * @return 比較次數
 */
public static int bubbleSortOpt2(int[] arr) {

    if (arr == null) {
        throw new NullPointerException();
    } else if (arr.length < 2) {
        return 0;
    }

    int temp;
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        int flag = 1;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = 0;
            }
            count++;
        }
        // 沒有發生交換，排序已經完成
        if (flag == 1) {
            return count;
        }
    }
    return count;
}

演算法還可以再優化，比如 3、4、2、1、6、7、8 這個陣列，第一次回圈后，變為 3、2、1、4、6、7、8 的順序，我們發現，1 之后的 4 、6、7、8 已經有序了，第二次回圈就沒必要對后面這段再遍歷比較，

假設一次回圈后陣列第 i 個元素后所有元素已經有序，優化目標就是下次回圈不再花費時間遍歷已經有序的部分，關鍵在于如何定位 i 這個分界點，其實并不難，可以想象，由于 i 之前的元素是無序的，所以一定有交換發生，而 i 之后的元素已經有序，不會發生交換，最后發生交換的地點，就是我們要找的分界點，

/**
 * 冒泡排序優化第二版
 *
 * <p>定位最后發生交換的分界點，之后的元素無需遍歷，
 * @param arr 待排序的整型陣列
 * @return 比較次數
 */
public static int bubbleSortOpt3(int[] arr) {

    if (arr == null) {
        throw new RuntimeException();
    } else if (arr.length < 2) {
        return 0;
    }

    int temp;
    int count = 0;
    int len = arr.length - 1;
    for (int i = 0; i < len; i++) {
        // 記錄最后一次交換位置
        int lastChange = 0;
        for (int j = 0; j < len; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 每交換一次更新一次
                lastChange = j;
            }
            count++;
        }
        // 沒有發生交換，排序已經完成
        if (lastChange == 0) {
            return count;
        }
        len = lastChange;
    }
    return count;
}

我們同樣可以用 lastChange 來判斷當前次回圈是否發生交換，這樣就結合了第一種優化方案了，各位可以自行設計測驗資料，看看回傳的比較次數大小是否減少，

性能分析

冒泡排序演算法是穩定的，因為相同元素的前后順序并不會變，

分析最優版本演算法，最好的情況是一開始已經排好序，那就沒必要交換了，直接回傳，此時只走了外層的第一次回圈，最優時間復雜度為 O(n)，

最壞的情況當然是陣列是逆序的，這樣里外兩層回圈都走了遍，最壞時間復雜度為 O( n^2 )，

空間復雜度則是用于交換的臨時變數，至于標志位和其他的因演算法的不同實作有差異，

標籤：其他

上一篇：0258. Add Digits (E)

下一篇：0106. Construct Binary Tree from Inorder and Postorder Traversal (M)