Java中怎么實現 冒泡排序

Java中怎么實現 冒泡排序

冒泡排序（Bubble Sort）是一種簡單的排序算法，它通過重復地遍歷要排序的列表，比較相鄰的元素并交換它們的位置，直到整個列表有序為止。冒泡排序的名字來源于較小的元素會像氣泡一樣逐漸“浮”到列表的頂端。

在Java中，冒泡排序可以通過嵌套的for循環來實現。下面我們將詳細介紹如何在Java中實現冒泡排序，并提供一個完整的代碼示例。

冒泡排序的基本思想

冒泡排序的基本思想是通過多次遍歷數組，每次遍歷時比較相鄰的兩個元素，如果它們的順序不正確（例如，前一個元素大于后一個元素），則交換它們的位置。通過多次遍歷，最大的元素會逐漸“冒泡”到數組的末尾，最終整個數組會被排序。

Java實現冒泡排序的步驟

1. 外層循環：控制遍歷的次數。每次遍歷后，最大的元素會被放到正確的位置，因此外層循環的次數為數組長度減一。

2. 內層循環：負責比較相鄰的元素并交換它們的位置。每次內層循環結束后，最大的元素會被放到當前未排序部分的末尾。

3. 交換元素：如果發現相鄰元素的順序不正確，則交換它們的位置。

Java代碼示例

下面是一個完整的Java代碼示例，展示了如何實現冒泡排序：

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交換 arr[j] 和 arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果沒有發生交換，說明數組已經有序，提前退出
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.println("排序前的數組:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("排序后的數組:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

代碼解釋

1. bubbleSort方法：這是實現冒泡排序的核心方法。它接受一個整數數組作為參數，并通過嵌套的for循環來排序數組。

2. swapped變量：用于優化算法。如果在某次遍歷中沒有發生任何交換，說明數組已經有序，可以提前退出循環。

3. printArray方法：用于打印數組的內容，方便查看排序前后的結果。

運行結果

運行上述代碼后，輸出如下：

排序前的數組:
64 34 25 12 22 11 90 
排序后的數組:
11 12 22 25 34 64 90 

冒泡排序的時間復雜度

冒泡排序的時間復雜度為O(n^2)，其中n是數組的長度。在最壞的情況下，冒泡排序需要進行n*(n-1)/2次比較和交換操作。因此，冒泡排序適用于小規模的數據集，對于大規模數據集來說，效率較低。

總結

冒泡排序是一種簡單但效率較低的排序算法。通過嵌套的for循環和交換操作，我們可以輕松地在Java中實現冒泡排序。雖然冒泡排序在實際應用中較少使用，但它仍然是理解排序算法基礎的一個很好的起點。