数据结构-7-鸡尾酒排序法
程序猿小码 Architect

前言

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

鸡尾酒排序 🍸

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

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

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

冒泡排序特点

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

鸡尾酒排序特点

  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

代码示例

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
43
44
45
46
47
48
49
50
51
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);
}

结果如下:

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

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

有序优化

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

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

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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

  • 本文标题:数据结构-7-鸡尾酒排序法
  • 本文作者:程序猿小码
  • 创建时间:2021-07-21 17:10:57
  • 本文链接:https://keep.xpoet.cn/2021/07/21/数据结构-7-鸡尾酒排序法/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论