???? 前言
大家好，我是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)
优点：能够在特定的条件下，减少排序的回合数；
缺点：代码量几乎扩大了一倍；
适用场景：大部分元素已经是有序的情况下，使用「鸡尾酒排序」会更好；
总结
????作者水平有限，如有总结不对的地方，欢迎留言或者私信！
????如果你觉得这篇文章还不错的话，那么点赞????、评论????、收藏????就是对我最大的支持！
????你知道的越多，你不知道越多，我们下期见！