数据结构 7 基础排序算法详解 鸡尾酒排序法、了解钟摆排序实现

数据结构 7 基础排序算法详解 鸡尾酒排序法、了解钟摆排序实现

前言

上节,我们已经通过对冒泡算法的优化、能够达到我们预想的结果。比较次数的减少、本节将继续在冒泡排序的基础上进行优化、能够达到刚好的效果。

鸡尾酒排序 🍸

为什么叫鸡尾酒排序呢?可能这个名字起得比较特殊。它是基于冒泡排序做了一些小小的改动。也叫做快乐钟摆排序 现在,大家的脑子里肯定会想到一个古老的钟摆。。。。。

左摇一下、右摇一下、重复不止

现在请记住这个场景。我们来学习一下这个鸡尾酒排序为何方神圣!

冒泡排序特点

从左往右、依次循环比较、一遍将一个大元素推到最右侧。

鸡尾酒排序特点

  1. 将原有的单向改为 双向比较
  2. 每次循环则将最小元素和最大元素分别推至左右两侧

画图理解

准备一个数组 [49, 38, 65, 97, 76, 13, 27, 49]

image.png

钟摆循环1开始 从右至左

1、本次比较27<49则无需改变循序。
image.png

2、本次比较13<27则无需改变循序。
image.png

3、本次比较76<13则需要交换位置。
image.png

image.png

4、直到比较到最左侧。。。(这里省略几个步骤)
image.png

我们发现,这个最小的元素13 已经被确认出来了。

钟摆循环2开始 从左至右

  1. 13<49 则不改变位置。继续向下移步
    image.png

  2. 49>38 则需要交换位置。交换位置后,继续下一步
    image.png

  3. 49<65 则位置不改变,继续向下一步。
    image.png

  4. 省略一些步骤。直到比较完最后一个元素。最大的一个元素97 已经被确认出来了。
    image.png

代码示例

public static void sort4(int[] array) {

    int temp = 0;
    int allChange = 0;
    /**
     * 外层循环用于控制程序总体循环次数
     */
    for (int i = 0; i < array.length / 2; i++) {

        /**
         * 有无交换元素标记
         */
        boolean isChange = true;

        //从左向右摆动
        for (int j = i; j < array.length - i - 1; j++) {

            if (array[j] > array[j + 1]) {

                //交换元素
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                isChange = false;
            }
            allChange++;
        }

        if (isChange) break;

        isChange = true;
        //从右向左摆动
        for (int g = array.length - i - 1; g > i; g--) {

            if (array[g] < array[g - 1]) {

                temp = array[g];

                array[g] = array[g-1];
                array[g-1] = temp;

                isChange = false;
            }
            allChange++;
        }
        if (isChange) break;
    }
    System.out.println(Arrays.toString(array));
    System.out.println("总体比较次数:"+allChange);
}

结果如下:

[13, 27, 38, 49, 49, 65, 76, 97]
总体比较次数:30

通过观察我们发现,当前算法的比较次数还是相对来说较多的。外层大循环运行减少一半、但是内层两个小循环还是需要注意的。有什么办法可以优化一下呢?我们可以采用之前的思路。通过设置有序长度 的方式来减少内层循环次数、已达到我们优化的目的。

有序优化

其实说白了,就是在发生变化的时候记录当前位置,下次循环到本次记录的位置停止则可以了。
通过两个边界变量 leftBorderrightBorder 控制程序比较位置的终止。

左循环从左边界比较到右边界停止
右循环从右边界比较到左边界停止

public static void sort5(int[] array) {


    int temp = 0;
    int allChange = 0;

    //记录左边界
    int leftBorder = 0;
    //右边界
    int rightBorder = array.length - 1;
    //左边发生变化的位置
    int leftChangeIndex = 0;
    //右边发生变化的位置
    int rightChangeIndex = 0;

    /**
     * 外层循环用于控制程序总体循环次数
     */
    for (int i = 0; i < array.length / 2; i++) {

        /**
         * 有无交换元素标记
         */
        boolean isChange = true;

        //从左向右摆动
        for (int j = leftBorder; j < rightBorder; j++) {

            if (array[j] > array[j + 1]) {

                //交换元素
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                isChange = false;

                //记录右边边界
                rightChangeIndex = j;
            }
            allChange++;
        }
        //用于下次循环终止
        rightBorder = rightChangeIndex;

        if (isChange) break;

        isChange = true;
        //从右向左摆动
        for (int g = rightBorder; g > leftBorder; g--) {

            if (array[g] < array[g - 1]) {

                temp = array[g];

                array[g] = array[g-1];
                array[g-1] = temp;

                isChange = false;
                //记录左边界
                leftChangeIndex = g;

            }
            allChange++;
        }
        leftBorder = leftChangeIndex;

        if (isChange) break;
    }
    System.out.println(Arrays.toString(array));
    System.out.println("总体比较次数:"+allChange);
}
--------------
[13, 27, 38, 49, 49, 65, 76, 97]
总体比较次数:27

小结

至此我们已经学习了有关的三个排序方式、包括最基础的冒泡排序、优化冒泡排序。最终的冒泡排序。通过钟摆思想实现的鸡尾酒排序法。越来觉得一个小小的排序,通过学习后发现,竟然有很多有意思的地方。

参考

https://mp.weixin.qq.com/s/CoVZrvis6BnxBQgQrdc5kA

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×