冒泡排序的簡單理解

• 2022 年 6 月 18 日
• 筆記
• 排序, 數據結構與演算法, 演算法

詳細描述

冒泡排序是一種交換排序，基本思想是在要排序的一組數中，對當前還未排好序的範圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。

即每當兩個相鄰的數比較後發現它們的順序與排序要求相反時，就將它們互換。

冒泡排序詳細的執行步驟如下：

1. 從第一個元素開始，比較相鄰的元素，如果前一個比後一個大，就交換它們兩個；
2. 從前往後，對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素就會是最大的數；
3. 將這次找出的最大元素放在最後一個元素位置上，然後針對除這個最大元素以外的其他所有元素重複以上 1~2 步驟；
4. 重複以上步驟，直到最後第一個元素和第二個元素完成比較、交換，則排序完成。

演算法圖解

問題解疑

冒泡排序是原地排序演算法嗎？

冒泡排序是一個原地排序演算法，過程只涉及相鄰數據的交換操作，只需要常量級的臨時空間，它的空間複雜度是 \(O(1)\)。

冒泡排序是穩定的排序演算法嗎？

為了保證冒泡排序演算法的穩定性，當有相鄰的兩個元素大小相等時可以不做交換，相同大小的數據在排序前後不會改變順序，所以冒泡排序是穩定的排序演算法。

冒泡排序的時間複雜度是多少？

使用最優時間複雜度解法，原序列是有序時的時間複雜度是 \(O(n)\)；最壞情況時間複雜度為 \(O(n^2)\)；平均時間複雜度是 \(O(n^2)\)。

程式碼實現

package cn.fatedeity.sort;

public class BubbleSort {
    private static void swap(int[] numbers, int src, int target) {
        int temp = numbers[src];
        numbers[src] = numbers[target];
        numbers[target] = temp;
    }

    public static int[] sort(int[] numbers) {
        for (int i = 0; i < numbers.length - 1; i++) {
            boolean doSwap = false;
            for (int j = 0; j + 1 < numbers.length - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    swap(numbers, j, j + 1);
                    doSwap = true;
                }
            }
            // 優化基礎冒泡排序的步驟
            if (!doSwap) {
                // 如果遍歷整個序列無需交換，則表示整個序列已經完全有序
                return numbers;
            }
        }
        return numbers;
    }
}