氣泡排序的簡單理解

語言: CN / TW / HK

詳細描述

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

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

氣泡排序詳細的執行步驟如下:

  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;
    }
}