JAVA:实现 Cocktail Sort鸡尾酒排序算法（附带源码）

m0_61840987

395人浏览 · 2025-08-05 00:15:00

m0_61840987 · 2025-08-05 00:15:00 发布

【一、项目背景详细介绍】

鸡尾酒排序（Cocktail Sort），又称双向冒泡排序（Bidirectional Bubble Sort）或振荡排序（Shaker Sort），是冒泡排序的改进版。它通过在数组上从左向右、再从右向左交替进行冒泡过程，使小元素快速向左移动，大元素快速向右移动，解决了普通冒泡排序“小元素移动慢”的问题。尽管最坏时间复杂度仍为O(n²)，但在某些近乎有序或特殊分布的场景下表现更优。

鸡尾酒排序同样为稳定排序，原地进行，无额外空间开销，常用于教学和中小规模数据排序场景中，并可作为其他排序算法的小规模子排序步骤。

【二、项目需求详细介绍】

功能需求
- 在Java环境中实现Cocktail Sort算法，对整型数组及泛型可比较对象数组进行正序和逆序排序；
- 支持可选日志输出，展示冒泡过程和边界收缩；
性能需求
- 时间复杂度：最坏O(n²)，最好O(n)；
- 空间复杂度：O(1)，原地排序；
代码质量需求
- 模块化方法：入口、双向冒泡、日志模式；
- 详细注释：说明前向和后向冒泡及边界更新；
- 提供JUnit测试示例：覆盖空数组、单元素、近似有序和随机场景。

【三、相关技术详细介绍】

双向冒泡思想
- 每轮分两步：先从左向右将最大元素移至右端，再从右向左将最小元素移至左端；
- 每完成一次双向冒泡，左边界右移一位，右边界左移一位，缩小未排序区间；
泛型支持
- 使用<T extends Comparable<T>>泛型方法和compareTo实现通用排序；
稳定性与原地
- 仅交换相邻逆序元素，保持相等元素相对顺序；
日志与调试
- 可选verbose模式输出每次比较和交换，便于理解算法步骤。

【四、实现思路详细介绍】

初始化边界
- left = 0, right = arr.length - 1, swapped = true；
双向循环
- 当swapped为true且left < right时：
  a) swapped = false；
  b) 前向冒泡：遍历i从left到right-1，比较并交换arr[i]和arr[i+1]，若交换则swapped=true；
  c) right--；
  d) 若!swapped退出；
  e) 后向冒泡：遍历i从right到left+1，比较并交换arr[i]和arr[i-1]，若交换则swapped=true；
  f) left++；
逆序支持
- 根据ascending参数切换比较方向；
日志输出
- 若verbose，在每次交换后打印当前数组状态和边界位置；

【五、完整实现代码】

// 文件：CocktailSort.java
// 描述：双向冒泡（鸡尾酒）排序实现，支持原生类型和泛型

import java.util.Arrays;

public class CocktailSort {
    /**
     * 原生整型数组鸡尾酒排序
     */
    public static void sort(int[] arr, boolean ascending, boolean verbose) {
        if (arr == null || arr.length < 2) return;
        int left = 0, right = arr.length - 1;
        boolean swapped = true;
        while (swapped && left < right) {
            swapped = false;
            // 前向冒泡
            for (int i = left; i < right; i++) {
                if (ascending ? arr[i] > arr[i + 1] : arr[i] < arr[i + 1]) {
                    int tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp;
                    swapped = true;
                    if (verbose) System.out.printf("Forward swap at %d: %s%n", i, Arrays.toString(arr));
                }
            }
            right--;
            if (!swapped) break;
            swapped = false;
            // 后向冒泡
            for (int i = right; i > left; i--) {
                if (ascending ? arr[i - 1] > arr[i] : arr[i - 1] < arr[i]) {
                    int tmp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = tmp;
                    swapped = true;
                    if (verbose) System.out.printf("Backward swap at %d: %s%n", i, Arrays.toString(arr));
                }
            }
            left++;
        }
    }

    /**
     * 泛型数组鸡尾酒排序
     */
    public static <T extends Comparable<T>> void sort(T[] arr, boolean ascending, boolean verbose) {
        if (arr == null || arr.length < 2) return;
        int left = 0, right = arr.length - 1;
        boolean swapped = true;
        while (swapped && left < right) {
            swapped = false;
            for (int i = left; i < right; i++) {
                if (ascending ? arr[i].compareTo(arr[i + 1]) > 0 : arr[i].compareTo(arr[i + 1]) < 0) {
                    T tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp;
                    swapped = true;
                    if (verbose) System.out.printf("Forward swap at %d: %s%n", i, Arrays.toString(arr));
                }
            }
            right--;
            if (!swapped) break;
            swapped = false;
            for (int i = right; i > left; i--) {
                if (ascending ? arr[i - 1].compareTo(arr[i]) > 0 : arr[i - 1].compareTo(arr[i]) < 0) {
                    T tmp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = tmp;
                    swapped = true;
                    if (verbose) System.out.printf("Backward swap at %d: %s%n", i, Arrays.toString(arr));
                }
            }
            left++;
        }
    }

    // 测试示例
    public static void main(String[] args) {
        int[] data = {5,3,8,4,2,7,1};
        System.out.println("原始：" + Arrays.toString(data));
        sort(data, true, true);
        System.out.println("排序后：" + Arrays.toString(data));

        String[] strs = {"d","b","a","c"};
        System.out.println("原始字符串：" + Arrays.toString(strs));
        sort(strs, true, true);
        System.out.println("泛型排序后：" + Arrays.toString(strs));
    }
}

【六、代码详细解读】