以下是冒泡排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
一、冒泡排序基础实现
原理
通过重复遍历数组，比较相邻元素并交换逆序对，逐步将最大值“冒泡”到数组末尾。
代码示例
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(n²)（逆序或随机数据）。 - 最好（已有序）：
O(n²)（未优化版本仍需遍历所有元素）。
- 最坏/平均：
- 空间复杂度：
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(n²)（所有情况） | O(1) | 不稳定 | 无优化，简单易实现 | 小规模数据或教学示例 |
| 优化版（带标志位） | O(n²)（平均/最坏），O(n)（最好） | O(1) | 不稳定 | 提前终止循环，减少无意义遍历 | 接近有序的数据（如已排序数组） |
| 鸡尾酒排序 | O(n²)（平均/最坏），O(n)（最好） | O(1) | 不稳定 | 双向扫描，同时归位最大和最小值 | 数据分布较分散或两端有序 |
| 递归实现 | O(n²)（所有情况） | O(n) | 不稳定 | 递归替代循环，代码结构清晰 | 代码风格偏好或教学场景 |
四、关键选择原则
- 基础场景：优先使用优化版（带标志位），在有序数据时效率显著提升。
- 双向优化：鸡尾酒排序适用于数据分布较分散的场景，减少比较次数。
- 递归实现：仅用于教学或代码风格需求，因递归增加栈空间开销。
- 稳定性需求：所有变体均不稳定，若需稳定排序需选择其他算法（如插入排序或归并排序）。
- 极端场景：小规模数据（如
n < 10）时，所有变体均可接受，优先选择简单实现。
通过选择合适的变体，可在特定场景下有效提升冒泡排序的效率或代码可读性。