🌟 前言
大家好，我是Edison😎
之前有写过一篇关于「冒泡排序」的文章；但是冒泡排序的实现仍然不是最优，有一种排序算法叫做 「鸡尾酒排序」；
鸡尾酒排序是基于冒泡排序的一种升级；
今天这篇文章就是关于 「鸡尾酒排序」 的详细介绍；Let‘s get it！
🛫送所有正在努力的大家一句话：你不一定逆风翻盘，但一定要向阳而生🌅
🔥热榜必看文章：室友打一把王者就学会了冒泡排序算法
文章目录
1. 基本思想
鸡尾酒排序又叫「快乐小时排序」；它基于冒泡排序做了一点小小优化；
让我们首先来回顾一下冒泡排序的思想：
冒泡排序的每⼀个元素都可以像⼩⽓泡⼀样，根据⾃⾝⼤⼩，⼀点⼀点地向着数组的⼀侧移动。
算法的每⼀轮都是从左到右来⽐较元素， 进⾏单向的位置交换的 。
那么鸡尾酒排序做了怎样的优化呢？
鸡尾酒排序的元素比较和交换过程是双向的
2. 图解示例
让我们来举一个栗子：
有8个数组成一个无序数列：2，3，4，5，6，7，8，1，希望从小到大排序。
如果按照冒泡排序的思想，排序的过程是什么样呢？
🍑 冒泡过程
第一轮结果（8和1交换）
第二轮结果（7和1交换）
第三轮结果（6和1交换）
第四轮结果（5和1交换）
第五轮结果（4和1交换）
第六轮结果（3和1交换）
第七轮结果（2和1交换）
那么冒泡排序有什么问题呢？？？
由上面可以看出，从2到8已经是有序了。只有元素1的位置不对，却还要进行7轮排序，太麻烦了吧？
那我们的鸡尾酒排序正是要解决这种问题，让我们来看一看鸡尾酒排序的过程吧。
🍑 鸡尾酒过程
鸡尾酒排序是什么样子呢？让我们来看一看详细过程：
第一轮（和冒泡排序一样，8和1交换）
第二轮
此时开始不一样了，我们反过来从右往左比较和交换：
8已经处于有序区，我们忽略掉8，让1和7比较。元素1小于7，所以1和7交换位置：
接下来1和6比较，元素1小于6，所以1和6交换位置：
接下来1和5比较，元素1小于5，所以1和5交换位置：
接下来1和4交换，1和3交换，1和2交换，最终成为了下面的结果：
第三轮
虽然已经有序，但是流程并没有结束；
1和2比较，位置不变；2和3比较，位置不变；3和4比较，位置不变…6和7比较，位置不变；
没有元素位置交换，证明已经有序，排序结束。
这就是鸡尾酒排序的思路。
排序过程就像大摆锤一样，第一轮从左到右，第二轮从右到左，第三轮再从左到右…
3. 动图演示
我们先来看个「鸡尾酒排序」的动图吧
刚刚的「鸡尾酒排序」过程，我们也可以用动图演示👇
第一轮操作（ 8 和 1 交换 ）
第二轮操作 ( 从序列右边开始遍历 ）
第三轮操作 ( 从左向右比较和交换 )
4. 代码实现
📃 代码示例
void Cocktail_Sort(int arr[], int sz) { int tmp = 0; int left = 0; int right = sz - 1; for (int i = 0; i < sz / 2; i++) { //有序标记，每一轮的初始是true int flag = 1; //奇数轮，从左向右比较和交换 for (int j = 0; j < sz - i - 1; j++) { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; //有元素交换，所以不是有序，标记变为0 flag = 0; } } if (flag) break; //偶数轮之前，重新标记为1 flag = 1; //偶数轮，从右向左比较和交换 for (int j = sz - i - 1; j > i; j--) { if (arr[j] < arr[j - 1]) { tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; //有元素交换，所以不是有序，标记变为0 flag = 0; } } if (flag) break; } } void Cocktail_Show(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = { 2,3,4,5,6,7,8,1 }; int sz = sizeof(arr) / sizeof(int); printf("排序前:"); Cocktail_Show(arr, sz);//打印排序函数 Cocktail_Sort(arr, sz);//排序函数 printf("排序后:"); Cocktail_Show(arr, sz); return 0; }
这段代码是鸡尾酒排序的原始实现。
代码外层的大循环控制着所有排序回合，大循环内包含两个小循环；
第一个循环从左向右比较并交换元素，第二个循环从右向左比较并交换元素。
5. 代码优化
上次介绍冒泡排序的时候，有一种针对有序区间的优化，那么我们的鸡尾酒排序也可以根据这个思路来进行优化；
让我们来回顾一下冒泡排序针对有序区的优化思路：
原始的冒泡排序，有序区的长度和排序的轮数是相等的。
比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 …
要想优化，我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。
对于单向的冒泡排序，我们需要设置一个边界值；
对于双向的鸡尾酒排序，我们需要设置两个边界值。请看代码：
void Cocktail_Sort(int arr[], int sz) { int tmp = 0; //无序数列的左边界，每次比较只需要比到这里为止 int leftBorder = 0; //无序数列的右边界，每次比较只需要比到这里为止 int rightBorder = sz - 1; //记录右侧最后一次交换的位置 int lastRightExchange = 0; //记录左侧最后一次交换的位置 int lastLeftExchange = 0; for (int i = 0; i < sz / 2; i++) { //有序标记，每一轮的初始是true int flag = 1; //奇数轮，从左向右比较和交换 for (int j = leftBorder; j < rightBorder; j++) { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; //有元素交换，所以不是有序，标记变为0 flag = 0; lastRightExchange = j; } } rightBorder = lastRightExchange; if (flag) break; //偶数轮之前，重新标记为1 flag = 1; //偶数轮，从右向左比较和交换 for (int j = rightBorder; j > leftBorder; j--) { if (arr[j] < arr[j - 1]) { tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; //有元素交换，所以不是有序，标记变为0 flag = 0; lastLeftExchange = j; } } leftBorder = lastLeftExchange; if (flag) break; } }
代码解释👇
代码中使用了左右两个边界值，
rightSortBorder代表右边界，leftSortBorder代表左边界。在比较和交换元素时，奇数轮从
leftSortBorder遍历到rightSortBorder位置；偶数轮从
rightSortBorder遍历到leftSortBorder位置。
6. 特性总结
时间复杂度：同冒泡排序，为 O ( n ² ) O(n²) O(n²)
空间复杂度：同冒泡排序，为 O ( 1 ) O(1) O(1)
优点：能够在特定的条件下，减少排序的回合数；
缺点：代码量几乎扩大了一倍；
适用场景：大部分元素已经是有序的情况下，使用「鸡尾酒排序」会更好；
总结
🤗作者水平有限，如有总结不对的地方，欢迎留言或者私信！
💕如果你觉得这篇文章还不错的话，那么点赞👍、评论💬、收藏🤞就是对我最大的支持！
🌟你知道的越多，你不知道越多，我们下期见！
