鸡尾酒排序（Cocktail Shaker Sort），又称双向冒泡排序或摇摆排序，是冒泡排序的改进版本。传统冒泡排序单向扫描，而鸡尾酒排序交替进行正向和反向扫描，一次遍历可将最大元素”冒泡”到末尾、最小元素”沉底”到开头。本文用Java实现鸡尾酒排序，讲解有序边界检测优化与复杂度分析。
算法核心思想
冒泡排序每一轮只能确定一个最大元素的位置。鸡尾酒排序的改进在于：
- 正向扫描：从左到右，将当前未排序区间的最大值交换到右边界
- 反向扫描：从右到左，将当前未排序区间的最小值交换到左边界
- 边界收缩：记录最后一次交换的位置，缩小下一轮扫描区间
这种双向扫描使得算法对”乌龟型”数据（小元素在末尾）更加友好。
与冒泡排序的对比
| 特性 | 冒泡排序 | 鸡尾酒排序 |
|---|---|---|
| 扫描方向 | 单向 | 双向交替 |
| 每轮确定元素 | 1个最大 | 1个最大 + 1个最小 |
| 对逆序小元素 | 需多轮移动 | 反向一轮即可 |
| 最优时间复杂度 | O(n) | O(n) |
| 平均时间复杂度 | O(n²) | O(n²) |
Java完整实现
import java.util.Arrays;
/**
* 鸡尾酒排序（Cocktail Shaker Sort）
* 双向冒泡排序，交替进行正向和反向扫描
*/
public class CocktailShakerSort {
/**
* 基础版鸡尾酒排序
* 双向扫描，每轮确定最大和最小元素位置
*/
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
boolean swapped;
for (int i = 0; i < n / 2; i++) {
swapped = false;
// 正向扫描：将最大值移到未排序区间末尾
for (int j = i; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true;
}
}
// 如果正向扫描没有交换，说明已有序
if (!swapped) break;
// 反向扫描：将最小值移到未排序区间开头
for (int j = n - 2 - i; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
swapped = true;
}
}
// 如果反向扫描也没有交换，说明已有序
if (!swapped) break;
}
}
/**
* 优化版鸡尾酒排序：记录最后一次交换位置，缩小扫描边界
* 这是实际应用中推荐的版本
*/
public static void sortOptimized(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
int left = 0; // 左边界
int right = n - 1; // 右边界
int lastSwapLeft = 0; // 最后一次交换的左位置
int lastSwapRight = 0; // 最后一次交换的右位置
while (left < right) {
lastSwapRight = left;
// 正向扫描：将最大值移到right位置
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
lastSwapRight = i; // 记录最后一次交换位置
}
}
// 如果没有发生交换，提前结束
if (lastSwapRight == left) break;
right = lastSwapRight; // 缩小右边界
lastSwapLeft = right;
// 反向扫描：将最小值移到left位置
for (int i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
swap(arr, i, i - 1);
lastSwapLeft = i;
}
}
// 如果没有发生交换，提前结束
if (lastSwapLeft == right) break;
left = lastSwapLeft; // 缩小左边界
}
}
/**
* 通用版：支持任意Comparable类型
*/
public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
if (arr == null || arr.length <= 1) return;
int left = 0;
int right = arr.length - 1;
int lastSwapLeft, lastSwapRight;
while (left < right) {
lastSwapRight = left;
for (int i = left; i < right; i++) {
if (arr[i].compareTo(arr[i + 1]) > 0) {
T temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
lastSwapRight = i;
}
}
if (lastSwapRight == left) break;
right = lastSwapRight;
lastSwapLeft = right;
for (int i = right; i > left; i--) {
if (arr[i].compareTo(arr[i - 1]) < 0) {
T temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
lastSwapLeft = i;
}
}
if (lastSwapLeft == right) break;
left = lastSwapLeft;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 打印数组
*/
public static void printArray(int[] arr) {
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
// 测试用例1：包含"乌龟型"数据的数组（小元素在末尾）
int[] arr1 = {5, 1, 4, 2, 8, 0, 2};
System.out.println("原始数组: " + Arrays.toString(arr1));
sortOptimized(arr1.clone());
System.out.println("排序结果: " + Arrays.toString(arr1));
// 测试用例2：完全逆序（鸡尾酒排序的优势场景）
int[] arr2 = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
System.out.println("\n逆序数组: " + Arrays.toString(arr2));
sortOptimized(arr2);
System.out.println("排序结果: " + Arrays.toString(arr2));
// 测试用例3：近乎有序的数组
int[] arr3 = {1, 2, 3, 5, 4, 6, 7, 8, 9, 10};
System.out.println("\n近乎有序: " + Arrays.toString(arr3));
sortOptimized(arr3);
System.out.println("排序结果: " + Arrays.toString(arr3));
// 性能对比：鸡尾酒排序 vs 冒泡排序
System.out.println("\n=== 性能对比 ===");
int size = 5000;
int[] testArr = new int[size];
for (int i = 0; i < size; i++) {
testArr[i] = (int)(Math.random() * size);
}
// 冒泡排序
int[] bubbleArr = testArr.clone();
long start1 = System.currentTimeMillis();
bubbleSort(bubbleArr);
long time1 = System.currentTimeMillis() - start1;
// 鸡尾酒排序
int[] cocktailArr = testArr.clone();
long start2 = System.currentTimeMillis();
sortOptimized(cocktailArr);
long time2 = System.currentTimeMillis() - start2;
System.out.printf("数组大小: %d%n", size);
System.out.printf("冒泡排序耗时: %d ms%n", time1);
System.out.printf("鸡尾酒排序耗时: %d ms%n", time2);
// 验证排序正确性
boolean isSorted = true;
for (int i = 1; i < cocktailArr.length; i++) {
if (cocktailArr[i] < cocktailArr[i - 1]) {
isSorted = false;
break;
}
}
System.out.println("排序正确性: " + (isSorted ? "通过" : "失败"));
}
/**
* 标准冒泡排序（用于对比）
*/
private static void bubbleSort(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]) {
swap(arr, j, j + 1);
swapped = true;
}
}
if (!swapped) break;
}
}
}
边界检测优化详解
优化版的核心在于记录最后一次交换位置。原理是：如果某位置之后没有发生交换，说明该位置之后的子数组已经有序。
初始: [3, 5, 2, 8, 1, 9, 4]
正向扫描后: [3, 2, 5, 1, 8, 4, 9]
最后一次交换在索引5 (4和9交换)
→ right边界从6缩小到5
反向扫描后: [1, 3, 2, 5, 4, 8, 9]
最后一次交换在索引1 (3和1交换)
→ left边界从0扩大到1
下一轮只需扫描 arr[1..5]
复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最优 | O(n) | 数组已有序，一轮扫描即可结束 |
| 平均 | O(n²) | 双向扫描减少约一半的比较次数 |
| 最坏 | O(n²) | 完全逆序，但反向扫描能快速处理小元素 |
| 空间 | O(1) | 原地排序，仅需常数额外空间 |
虽然最坏复杂度与冒泡排序相同，但鸡尾酒排序在以下场景表现更好：
- “乌龟型”数据：小元素位于数组末尾时，反向扫描一次即可将其移动到正确位置
- 数据波动大：同时存在极大值在头部和极小值在尾部的情况
- 近乎有序：边界检测能大幅缩小扫描范围
稳定性说明
鸡尾酒排序是稳定排序。当相邻元素相等时，我们只在 arr[i] > arr[i+1] 时才交换，相等元素保持原有相对顺序。
适用场景
鸡尾酒排序适合：
- 教学演示：直观展示排序的双向优化思想
- 小规模数据：n < 1000时性能可接受
- 数据近乎有序：边界检测能提前终止
- 学习冒泡排序改进：理解如何从单向到双向优化算法
对于大规模数据，推荐使用快速排序、归并排序或TimSort（Java Arrays.sort() 的实现）。
