Java實現簡單冒泡排序

一、冒泡排序基本原理

首先，讓我們看看什麼是冒泡排序。冒泡排序是一種簡單的排序算法，它比較相鄰元素，如果第一個比第二個大（或者小，根據具體實現而定），就交換它們的位置。這樣一趟下來，最大（或最小）的元素就會被移動到數組的末尾。然後再針對剩下的元素進行類似的操作，直到整個數組有序。

具體實現方式可以參考下面的代碼：

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j  arr[j + 1]) {
                // swap arr[j+1] and arr[i]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

這段代碼中，我們通過兩層循環來實現冒泡排序。外層循環控制排序輪數，內層循環用於比較相鄰元素的大小。

二、時間複雜度分析

冒泡排序的時間複雜度是O(n^2)。在最壞的情況下，也就是待排序的序列是逆序的情況下，比較次數和交換次數都是最大值，達到了n(n-1)/2次，即O(n^2)。在最好的情況下，也就是待排序的序列已經排好序了，比較次數只有n-1次，交換次數為0，時間複雜度為O(n)。但是，由於在實際場景中，待排序的序列很少是完全有序或者完全逆序的，因此冒泡排序的時間複雜度平均為O(n^2)。

三、優化冒泡排序

雖然冒泡排序算法是簡單易懂，但是在大規模數據的排序中，它的效率非常低。如果待排序數組已經基本有序，那麼仍然需要進行O(n^2)的比較和交換操作。因此，我們需要針對冒泡排序進行一些優化。

1. 設置標誌位

如果一趟冒泡下來，沒有進行任何交換，那麼說明序列已經有序，無需進行下一輪排序。設置一個標誌位來記錄是否進行了交換操作，如果沒有進行交換，則說明已經有序，可以直接退出循環。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean flag = false; // 設置標誌位
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j  arr[j + 1]) {
                // swap arr[j+1] and arr[i]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true; // 標誌位設為true
            }
        }
        if (!flag) { // 如果沒有進行交換，說明已經有序
            break;
        }
    }
}

2. 優化內層循環

因為每一輪都會將未排序的最大元素移動到數組的末尾，在下一輪排序時，就可以不用考慮已經排好序的元素。因此，我們可以記錄最後一次交換的位置，作為下一輪交換的結束位置。這樣可以減少比較和交換的次數。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    int last = n - 1; // 最後一次交換的位置
    for (int i = 0; i < n - 1; i++) {
        boolean flag = true; // 設置標誌位
        int k = last;
        for (int j = 0; j  arr[j + 1]) {
                // swap arr[j+1] and arr[i]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = false;
                last = j; // 記錄最後一次交換的位置
            }
        }
        if (flag) {
            break;
        }
    }
}

四、小結

本文介紹了冒泡排序的基本原理，並對冒泡排序的時間複雜度進行了分析。針對冒泡排序效率低的缺點，我們進行了優化，包括設置標誌位和優化內層循環。冒泡排序看起來簡單，但是在實際應用中，它的效率非常低，一般只用於小規模數據的排序。