2

数据结构-7-鸡尾酒排序法

 3 years ago
source link: https://blogs.chaobei.xyz/2021/07/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-7-%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F%E6%B3%95/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

鸡尾酒排序 🍸

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

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

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

冒泡排序特点

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

鸡尾酒排序特点

  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

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

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

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

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK