Bubble Sort詳解：一個(gè)簡(jiǎn)單的排序演算法

冒泡排序是最簡(jiǎn)單的排序演算法之一。它的工作原理是反覆比較相鄰元素，如果它們順序不對(duì)，則交換它們。例如，如果排序順序是升序，則比較相鄰元素，並將較大的元素放在右邊。每次迭代中，我們只比較未排序的元素，並將最大的元素放在數(shù)組未排序元素的最後一個(gè)位置。

演算法恰如其分地命名為冒泡排序，因?yàn)樵卦诿看蔚卸紩?huì)向數(shù)組的右側(cè)移動(dòng)，就像水泡上升到水面一樣。

冒泡排序的工作原理

假設(shè)我們要以升序排列這個(gè)陣列：

第一次迭代

在第一次迭代中，我們嘗試將最大元素移到陣列的末端。因此，我們將重複比較相鄰元素，如果它們順序不對(duì)，則交換它們。

已移動(dòng)到正確位置的元素被認(rèn)為已排序。

後續(xù)迭代

這個(gè)過程對(duì)所有迭代重複進(jìn)行，直到陣列排序完畢。在每次迭代中，我們只比較未排序的元素，因?yàn)橐雅判虻脑匾呀?jīng)按正確的順序排列。

我們迭代遍歷數(shù)組 n-1 次，其中 n 是數(shù)組的長(zhǎng)度。也就是說，由於我們的陣列有六個(gè)元素，我們只迭代遍歷數(shù)組五次。這是因?yàn)?，在第五次迭代之後，五個(gè)元素已經(jīng)放置在其正確的位置，因此最終的未排序元素被認(rèn)為已排序。所有迭代完成後，我們將得到一個(gè)排序後的陣列。

冒泡排序的實(shí)作

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循環(huán)遍歷數(shù)組 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比較相鄰元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

執(zhí)行此程式碼將在控制臺(tái)中列印以下輸出：

<code>未排序數(shù)組: [8, 2, 6, 4, 9, 1]
已排序數(shù)組: [1, 2, 4, 6, 8, 9]</code>

在這個(gè)冒泡排序的實(shí)作中，即使數(shù)組已經(jīng)排序，我們也會(huì)每次都迭代遍歷數(shù)組。我們可以進(jìn)一步優(yōu)化程式碼，以便一旦數(shù)組已排序就停止排序。

最佳化的冒泡排序

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循環(huán)遍歷數(shù)組 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比較相鄰元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果沒有交換，則數(shù)組已排序
        if(!swapped) break;
    }
}

透過這個(gè)實(shí)現(xiàn)，如果我們嘗試對(duì)一個(gè)已經(jīng)排序的數(shù)組進(jìn)行排序，我們將只迭代一次，並在沒有進(jìn)行排序時(shí)停止。

冒泡排序的複雜度

時(shí)間複雜度：

最佳情況 (O(n))：

最佳情況是輸入陣列已經(jīng)排序。演算法只迭代一次數(shù)組以檢查它是否已排序，並且不執(zhí)行任何交換。

平均情況 (O(n2))：

當(dāng)輸入數(shù)組元素處?kù)峨S機(jī)順序時(shí)。演算法必須進(jìn)行多次迭代並執(zhí)行交換以對(duì)數(shù)組進(jìn)行排序。

最壞情況 (O(n2))：

最壞情況是輸入數(shù)組依反向順序排序。演算法進(jìn)行 n-1 次迭代並執(zhí)行最大數(shù)量的交換。

空間複雜度 O(1)：

冒泡排序是一種就地排序演算法，也就是說，它不需要任何與輸入數(shù)組大小成比例的額外記憶體。

結(jié)論

冒泡排序是一種易於理解且實(shí)現(xiàn)的演算法。但是，由於其時(shí)間複雜度高，因此不適合用於處理大型資料集。在處理小型資料集時(shí)，或者當(dāng)你不關(guān)心複雜度時(shí)，可以使用冒泡排序。

以上是了解冒泡排序演算法（附Java範(fàn)例）的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！