冒泡排序与鸡尾酒排序

#算法 #java

冒泡排序通过相邻元素比较交换，把最大值逐步"冒"到末尾。鸡尾酒排序是它的双向版本，每轮同时把最大值推到右边、最小值推到左边，轮次减半。

实际项目里这两个都不用，但面试会考优化思路。

1. 冒泡排序

两个优化点：

• 某轮没有发生交换，说明已有序，提前退出
• 记录最后一次交换的位置，该位置之后不用再比

public static void bubbleSort(int[] arr) {
    int len = arr.length;

    for (int i = 0; i < len - 1; i++) {
        boolean sorted = true;
        int sortedBoundary = len - 1 - i;

        for (int j = 0; j < sortedBoundary; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                sorted = false;
                sortedBoundary = j; // 缩小下一轮的范围
            }
        }

        if (sorted) break; // 提前退出
    }
}

复杂度：最好 O(n)（已有序），平均/最坏 O(n²)，空间 O(1)，稳定。

2. 鸡尾酒排序

public static void cocktailSort(int[] arr) {
    int len = arr.length;

    for (int i = 0; i < len / 2; i++) {
        boolean sorted = true;
        int right = len - 1 - i;

        // 从左往右，把最大值推到右边
        for (int j = i; j < right; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
                sorted = false;
                right = j;
            }
        }
        if (sorted) break;

        sorted = true;

        // 从右往左，把最小值推到左边
        for (int j = right; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                int tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp;
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

对 [2,3,4,5,1,6,7,8,9] 这种两端有序、中间乱的数据效果更好。

3. 对比

实际大数据量用快速排序或归并排序，小数据量（< 50）用插入排序，Java 内置的 Arrays.sort 是 TimSort（归并 + 插入），直接用就行。