冒泡排序是一種簡單的排序算法，通過相鄰元素的比較和交換，使較大的元素逐漸"浮"到數組末尾。
時間復雜度:最佳 O(n) | 平均 O(n2) | 最差 O(n2)
空間復雜度:O(1)
穩定性:穩定
應用場景/前提條件
- 適用于小規模數據
- 對幾乎已排序的數據效率較高
算法步驟
- 比較相鄰的元素。如果第一個比第二個大，就交換它們
- 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對
- 這步做完后，最后的元素會是最大的數
- 針對所有的元素重復以上的步驟，除了已經是最大數的最后一個
- 持續每次對越來越少(每次重復都會少一個最大數)的元素重復上面的步驟，直到沒有任何一對數字需要比較
public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {// 每次遍歷后，最大的i+1個元素已經排好序for (int j = 0; j < n - i - 1; j++) {// 如果當前元素大于下一個元素，則交換if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}- 外層循環：控制排序的輪數。對于長度為 n 的數組，需要進行 n-1 輪排序。每一輪排序都會將當前未排序部分的最大元素 "冒泡" 到右側。
- 內層循環：負責比較相鄰元素并在必要時交換它們。每一輪排序后，最大的元素已經就位，因此內層循環的次數可以逐輪減少（通過
n - i - 1實現）。1. 每輪排序后的有序元素 冒泡排序的特點是：每一輪結束后，最大的 i+1 個元素都會被排到數組的右側（升序排序）。例如：第 1 輪后，最大的元素被排到了最后一個位置。 第 2 輪后，第二大的元素被排到了倒數第二個位置。 依此類推，第 i 輪后，最大的 i+1 個元素都已經在正確的位置上。2. 內層循環的邊界 由于右側的 i+1 個元素已經有序，下一輪比較時就不需要再考慮它們。因此， 每一輪需要比較的元素數量是逐漸減少的：第 1 輪需要比較 n-1 次（所有元素都參與比較）。 第 2 輪需要比較 n-2 次（最后一個元素已經有序，不需要再比較）。 第 i 輪需要比較 n - i - 1 次。3. 為什么是 n - i - 1？n 是數組的總長度。 i 是當前外層循環的輪數（從 0 開始計數）。 n - i 表示剩余未排序元素的數量。 由于每次比較的是相鄰的兩個元素，因此需要進行 n - i - 1 次比較。 - 元素交換：當發現相鄰元素順序錯誤時（前一個元素大于后一個元素），通過臨時變量
temp交換它們的位置。
if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}優缺點
優點
- 代碼簡單，容易實現
- 適合小規模數據排序
- 對于幾乎已經排好序的數據，效率較高
- 穩定的排序算法
缺點
- 時間復雜度高，為O(n2)
- 隨著元素數量增加，效率急劇下降
- 每次只能將一個元素移動到其最終位置，效率不高
雞尾酒排序（雙向冒泡排序）
雞尾酒排序是冒泡排序的一種變體，它從低到高然后從高到低來回排序，比冒泡排序的效率稍微高一點：
public static void cocktailSort(int[] arr) {boolean swapped = true;int start = 0; // 左側已排序邊界int end = arr.length - 1; // 右側已排序邊界while (swapped) {// 從左到右掃描，將最大元素移到右側swapped = false;for (int i = start; i < end; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);swapped = true;}}// 掃描結束后，最大元素已在end位置，因此下次掃描到end-1即可end--;// 如果沒有交換，說明數組已排序if (!swapped) break;// 從右到左掃描，將最小元素移到左側swapped = false;for (int i = end - 1; i >= start; i--) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);swapped = true;}}// 掃描結束后，最小元素已在start位置，因此下次從start+1開始start++;}
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}測驗
- 冒泡排序的平均時間復雜度是多少？
- 冒泡排序是穩定的排序算法嗎？
- 對于已經排好序的數組，優化版冒泡排序的時間復雜度是多少？
- 冒泡排序每一輪遍歷后，數組尾部會有什么特點？
- 如何優化冒泡排序以提高效率？
測驗答案
- 冒泡排序的平均時間復雜度是O(n2)。
- 是的，冒泡排序是穩定的排序算法。因為只有當前一個元素大于后一個元素時才交換，相等元素不會改變相對位置。
- 對于已經排好序的數組，優化版冒泡排序的時間復雜度是O(n)。因為第一輪遍歷不會發生交換，優化版會檢測到這點并提前終止。
- 冒泡排序每一輪遍歷后，數組尾部會有一個元素到達其最終位置，且是當前未排序部分中的最大元素。第i輪結束后，末尾i個元素已排好序。
- 優化冒泡排序的方法:
- 添加標志位跟蹤是否發生交換，無交換則提前終止
- 記錄最后一次交換位置，下一輪只遍歷到該位置
- 使用雙向冒泡(雞尾酒排序)，同時將最大值上浮和最小值下沉
