算法概述
冒泡排序（Bubble Sort）是最经典的交换排序算法，通过 repeatedly 比较相邻元素并交换逆序对，使较大的元素逐步”冒泡”到数组末端。虽然其平均时间复杂度为O(n²)，但冒泡排序的思想简单直观，且经过鸡尾酒排序（双向冒泡）优化后，在部分有序场景下效率显著提升。本文用Java实现基础冒泡排序、提前终止优化以及鸡尾酒双向排序。
核心原理
每一趟遍历将当前未排序区间的最大元素”冒泡”到正确位置。基础优化：若某趟遍历没有发生交换，说明数组已有序，可立即终止。鸡尾酒排序进一步优化：交替进行正向和反向遍历，同时把最大元素沉底、最小元素浮顶，减少乌龟型小元素（位于数组末端的小值）的缓慢移动问题。
完整Java实现
public class BubbleSort {
/**
* 基础冒泡排序：每趟将最大元素冒泡到末尾
* 时间复杂度：最坏O(n²)，最好O(n²)，平均O(n²)
* 空间复杂度：O(1)
* 稳定性：稳定
*/
public static void basicBubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/**
* 优化冒泡排序：引入标志位，无交换时提前终止
* 最好时间复杂度降至O(n)
*/
public static void optimizedBubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; 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; // 已有序，提前退出
}
}
/**
* 鸡尾酒排序（双向冒泡）：交替正向和反向扫描
* 解决"乌龟"问题——小元素位于数组末端需要很多趟才能移到前端
*/
public static void cocktailSort(int[] arr) {
int n = arr.length;
int left = 0, right = n - 1;
while (left < right) {
boolean swapped = false;
// 正向扫描：将最大元素移到right位置
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
right--;
if (!swapped) break;
// 反向扫描：将最小元素移到left位置
swapped = false;
for (int i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
int temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
swapped = true;
}
}
left++;
if (!swapped) break;
}
}
/**
* 进阶优化：记录每趟最后交换的位置，缩小下次扫描边界
*/
public static void boundaryOptimizedBubbleSort(int[] arr) {
int n = arr.length;
int sortBorder = n - 1; // 无序区边界
while (sortBorder > 0) {
int newBorder = 0;
for (int i = 0; i < sortBorder; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
newBorder = i; // 记录最后交换位置
}
}
sortBorder = newBorder;
}
}
public static void main(String[] args) {
int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
int[] arr2 = {64, 34, 25, 12, 22, 11, 90};
int[] arr3 = {64, 34, 25, 12, 22, 11, 90};
optimizedBubbleSort(arr1);
System.out.println("优化冒泡排序: " + java.util.Arrays.toString(arr1));
cocktailSort(arr2);
System.out.println("鸡尾酒排序: " + java.util.Arrays.toString(arr2));
boundaryOptimizedBubbleSort(arr3);
System.out.println("边界优化冒泡: " + java.util.Arrays.toString(arr3));
}
}
复杂度分析
| 版本 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 特点 |
|---|---|---|---|---|---|
| 基础冒泡 | O(n²) | O(n²) | O(n²) | O(1) | 无优化 |
| 提前终止 | O(n) | O(n²) | O(n²) | O(1) | 已有序时最快 |
| 鸡尾酒 | O(n) | O(n²) | O(n²) | O(1) | 双向扫描减少乌龟问题 |
| 边界优化 | O(n) | O(n²) | O(n²) | O(1) | 动态缩小无序区间 |
鸡尾酒排序在最坏情况下仍需O(n²)，但对于部分有序且小元素分布在末端的数据，其实际比较和交换次数约为基础冒泡的一半。
应用场景
- 教学演示：最直观的排序算法，便于理解交换排序思想
- 几乎有序的小数据集：提前终止机制使其效率接近O(n)
- 需要稳定排序且空间受限的场景
- 作为更复杂排序算法的基准对比
