冒泡排序升级之【鸡尾酒排序】

发表于

这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战

欢迎关注公众号OpenCoder，来和我做朋友吧~❤😘😁🐱‍🐉👀

一.鸡尾酒排序概念

鸡尾酒排序，是冒泡排序算法的一种升级。冒泡排序的每个元素都可以像气泡一样，根据自身大小，一点点的向着数组的某侧移动。算法每一轮都是从左到右来比较元素，进行单向的位置交换的。而鸡尾酒排序是在此基础上元素比较和交换过程变成了双向的。固鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。

鸡尾酒排序最糟或是平均所花费的次数都是O(n²)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。

二. 逻辑推演

问题分析：

现有一个数组，里面的数据为： [2,3,4,5,6,7,8,1]，我们以此数据来分析：

image-20211013110818725

冒泡排序过程如下：

image-20211013111356725

image-20211013162036391

结果分析：

元素 2、3、4、5、6、7、8已经是有序的了，只需要将元素1的放到正确的位置就可以了，却还是进行了7轮排序，这也太不方便了。要是能直接将1的位置进行调整，数列就有序了。鸡尾酒排序正是要解决这个问题的。

优化思路：

鸡尾酒详细过程：

第一轮（和冒泡排序一样，8和1交换）

image-20211013162754692

第二轮：此时开始不一样了，我们反过来从右往左比较进行交换。

image-20211013163352045

image-20211013163912858

第三轮:虽然实际上已经有序，但是流程并没有结束。

在鸡尾酒排序的第三轮，需要重新从左向右比较进行交换。

1和2比较，位置不变；2和3比较，位置不变；3和4比较，位置不变…7和8比较位置不变。没有元素进行交换，证明当前有序，排序结束。

小结：

本来需要7轮的排序场景，用3轮就解决了，鸡尾酒排序就是这样巧妙的算法。

而鸡尾酒排序的思路，排序过程就像钟摆一样，第一轮从左往右比较，第二轮从右往左比较，第三轮再从左往右比较…

三.鸡尾酒排序算法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
java复制代码    public static void sort(int[] array) {
        //循环计数
        int count = 0;
        //数据交换临时变量
        int tmp = 0;
        for (int i = 0; i < array.length / 2; i++) {
            System.out.println("第" + (++count) + "次循环");
            //每轮的初始值都是true，有序标记：true代表有序
            boolean isSorted = true;
            //奇数轮，从左向右比较和交换
            for (int j = i; j < array.length - i - 1; j++) {
​
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    //发生交换，不是有序，标记改成false
                    isSorted = false;
                }
            }
            //是否有序
            if (isSorted) {
                break;
            }
            //在偶数轮之前，将isSorted重新标记为true
            isSorted = true;
            System.out.println("第" + (++count) + "次循环");
            //偶数轮，方向从右向左比较和交换
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    isSorted = false;
                }
            }
            //是否有序
            if (isSorted) {
                break;
            }
        }
    }

结果输出:

1
2
3
4
java复制代码第1次循环
第2次循环
第3次循环
[1, 2, 3, 4, 5, 6, 7, 8]

总结：

这段代码是鸡尾酒排序的原始实现。代码外部的大循环控制所有排序回合，大循环内部包含两个小循环，第1个小循环从左往右比较并交换元素，第2个小循环从右往左比较并交换元素。

鸡尾酒的优势是，在大部分元素已经有序的情况下，减少排序的回合数；而缺点也很明显，就是代码量几乎翻了一倍。

欢迎关注公众号OpenCoder，来和我做朋友吧~❤😘😁🐱‍🐉👀

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%