Bubble Sort詳解：一個簡單的排序演算法

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

演算法恰如其分地命名為冒泡排序，因為元素在每次迭代中都會向數(shù)組的右側移動，就像水泡上升到水面一樣。

冒泡排序的工作原理

假設我們要以升序排列這個陣列：

第一次迭代

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

已移動到正確位置的元素被認為已排序。

後續(xù)迭代

這個過程對所有迭代重複進行，直到陣列排序完畢。在每次迭代中，我們只比較未排序的元素，因為已排序的元素已經(jīng)按正確的順序排列。

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

冒泡排序的實作

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í)行此程式碼將在控制臺中列印以下輸出：

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

在這個冒泡排序的實作中，即使數(shù)組已經(jīng)排序，我們也會每次都迭代遍歷數(shù)組。我們可以進一步優(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;
    }
}

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

冒泡排序的複雜度

時間複雜度：

最佳情況 (O(n))：

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

平均情況 (O(n2))：

當輸入數(shù)組元素處於隨機順序時。演算法必須進行多次迭代並執(zhí)行交換以對數(shù)組進行排序。

最壞情況 (O(n2))：

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

空間複雜度 O(1)：

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

結論

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

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