以下是冒泡排序的詳細解析，包含基礎實現、常見變體的完整代碼示例，以及各變體的對比表格：

---

一、冒泡排序基礎實現

原理

通過重復遍歷數組，比較相鄰元素并交換逆序對，逐步將最大值“冒泡”到數組末尾。

代碼示例

public class BubbleSort {void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {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;}}}}
}

復雜度分析

• 時間復雜度：
  • 最壞/平均：O(n2)（逆序或隨機數據）。
  • 最好（已有序）：O(n2)（未優化版本仍需遍歷所有元素）。
• 空間復雜度：O(1)。
• 穩定性：不穩定（相同值的元素可能因交換順序改變相對位置）。

---

二、常見變體及代碼示例

1. 優化版（帶標志位）

改進點：通過標志位檢測是否提前終止循環，減少無意義遍歷。
適用場景：接近有序的數據（如已排序數組）。

public class OptimizedBubbleSort {void sort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;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;swapped = true;}}// 若某輪未交換，說明已有序，提前終止if (!swapped) break;}}
}

2. 雞尾酒排序（雙向冒泡）

改進點：從兩端交替掃描，同時將最大值和最小值歸位。
適用場景：數據分布較分散或兩端有序。

public class CocktailSort {void sort(int[] arr) {int n = arr.length;boolean swapped = true;int start = 0, end = n - 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;}}if (!swapped) break;swapped = false;end--;// 向左掃描，將最小值移到開頭for (int i = end - 1; i >= start; i--) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);swapped = true;}}start++;}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

3. 遞歸實現

改進點：用遞歸替代循環，代碼結構更清晰。
適用場景：教學或代碼風格偏好遞歸。

public class RecursiveBubbleSort {void sort(int[] arr, int n) {if (n == 1) return;for (int i = 0; i < n - 1; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);}}sort(arr, n - 1);}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

---

三、變體對比表格

變體名稱	時間復雜度	空間復雜度	穩定性	主要特點	適用場景
基礎冒泡排序	O(n2)（所有情況）	O(1)	不穩定	無優化，簡單易實現	小規模數據或教學示例
優化版（帶標志位）	O(n2)（平均/最壞）， O(n)（最好）	O(1)	不穩定	提前終止循環，減少無意義遍歷	接近有序的數據（如已排序數組）
雞尾酒排序	O(n2)（平均/最壞）， O(n)（最好）	O(1)	不穩定	雙向掃描，同時歸位最大和最小值	數據分布較分散或兩端有序
遞歸實現	O(n2)（所有情況）	O(n)	不穩定	遞歸替代循環，代碼結構清晰	代碼風格偏好或教學場景

---

四、關鍵選擇原則

1. 基礎場景：優先使用優化版（帶標志位），在有序數據時效率顯著提升。
2. 雙向優化：雞尾酒排序適用于數據分布較分散的場景，減少比較次數。
3. 遞歸實現：僅用于教學或代碼風格需求，因遞歸增加棧空間開銷。
4. 穩定性需求：所有變體均不穩定，若需穩定排序需選擇其他算法（如插入排序或歸并排序）。
5. 極端場景：小規模數據（如 n < 10）時，所有變體均可接受，優先選擇簡單實現。

通過選擇合適的變體，可在特定場景下有效提升冒泡排序的效率或代碼可讀性。