「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

云惠网小编 2021年12月25日21:18:32
评论
3263字阅读10分52秒
摘要

冒泡排序的实现仍然不是最优,有一种排序算法叫做 「鸡尾酒排序」;鸡尾酒排序是基于冒泡排序的一种升级;今天这篇文章就是关于 「鸡尾酒排序」 的详细介绍;

广告也精彩

img

Let‘s get it!

第一轮结果(8和1交换)

第一轮操作( 8 和 1 交换 )

鸡尾酒排序是基于冒泡排序的一种升级;

2. 图解示例

时间复杂度:同冒泡排序,为
O
(
n
²
)
O(n²)
O(n²)

 

空间复杂度:同冒泡排序,为
O
(
1
)
O(1)
O(1)

 

优点:能够在特定的条件下,减少排序的回合数;

 

缺点:代码量几乎扩大了一倍;

 

适用场景:大部分元素已经是有序的情况下,使用「鸡尾酒排序」会更好;


对于单向的冒泡排序,我们需要设置一个边界值;

3. 动图演示

第四轮结果(5和1交换)

但是冒泡排序的实现仍然不是最优,有一种排序算法叫做 「鸡尾酒排序」

image-20211224090620073

📃 代码示例

我们先来看个「鸡尾酒排序」的动图吧

那么冒泡排序有什么问题呢???

让我们来举一个栗子:

第三轮

img

第二轮结果(7和1交换)

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;
}
}

这段代码是鸡尾酒排序的原始实现。

img

image-20211224091105234

image-20211224090741105

🌟 前言

1. 基本思想

image-20211224090817520

第二轮

鸡尾酒排序又叫「快乐小时排序」;它基于冒泡排序做了一点小小优化;

🤗作者水平有限,如有总结不对的地方,欢迎留言或者私信!
 
💕如果你觉得这篇文章还不错的话,那么点赞👍、评论💬、收藏🤞就是对我最大的支持!
 
🌟你知道的越多,你不知道越多,我们下期见!

image-20211224090717023

大家好,我是Edison😎

第五轮结果(4和1交换)

🍑 鸡尾酒过程

🍑 冒泡过程

有8个数组成一个无序数列:2,3,4,5,6,7,8,1,希望从小到大排序。

 

如果按照冒泡排序的思想,排序的过程是什么样呢?

image-20211224090510007

对于双向的鸡尾酒排序,我们需要设置两个边界值。请看代码:

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;
}

代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder 代表左边界。

 

比较交换元素时,奇数轮leftSortBorder 遍历到 rightSortBorder 位置;

 

偶数轮rightSortBorder 遍历到 leftSortBorder 位置。

第一轮(和冒泡排序一样,8和1交换)

4. 代码实现

让我们首先来回顾一下冒泡排序的思想:

第六轮结果(3和1交换)

之前有写过一篇关于「冒泡排序」的文章;

在这里插入图片描述

6. 特性总结


原始的冒泡排序,有序区的长度和排序的轮数是相等的。

 

比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2 …

 

要想优化,我们可以在每一轮排序的最后,记录下最后一次元素交换的位置,那个位置也就是无序数列的边界,再往后就是有序区了。

虽然已经有序,但是流程并没有结束;

 

1和2比较,位置不变;2和3比较,位置不变;3和4比较,位置不变…6和7比较,位置不变;

 

没有元素位置交换,证明已经有序,排序结束。

image-20211224090558030

第二轮操作 ( 从序列右边开始遍历 )

此时开始不一样了,我们反过来从右往左比较和交换:

 

8已经处于有序区,我们忽略掉8让1和7比较元素1小于7,所以1和7交换位置:

image-20211224091143979

image-20211224091151045

接下来1和6比较元素1小于6,所以1和6交换位置:

image-20211224091216241

image-20211224091223856

接下来1和5比较元素1小于5,所以1和5交换位置:

image-20211224091246323

image-20211224091258796

接下来1和4交换1和3交换1和2交换,最终成为了下面的结果:

image-20211224091320102

鸡尾酒排序是什么样子呢?让我们来看一看详细过程:

今天这篇文章就是关于 「鸡尾酒排序」 的详细介绍;

文章目录

    • 🌟 前言
    • 1. 基本思想
    • 2. 图解示例
      • 🍑 冒泡过程
      • 🍑 鸡尾酒过程
    • 3. 动图演示
    • 4. 代码实现
    • 5. 代码优化
    • 6. 特性总结
    • 总结

冒泡排序的每⼀个元素都可以像⼩⽓泡⼀样,根据⾃⾝⼤⼩,⼀点⼀点地向着数组的⼀侧移动。

 

算法的每⼀轮都是从左到右来⽐较元素, 进⾏单向的位置交换的 。

 

那么鸡尾酒排序做了怎样的优化呢?

 

鸡尾酒排序的元素比较和交换过程是双向

第三轮结果(6和1交换)

image-20211224090801714

代码解释👇

第三轮操作 ( 从左向右比较和交换 )

image-20211224090645701


上次介绍冒泡排序的时候,有一种针对有序区间的优化,那么我们的鸡尾酒排序也可以根据这个思路来进行优化;

代码外层的大循环控制着所有排序回合,大循环内包含两个小循环;

 

第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。

由上面可以看出,从2到8已经是有序了。只有元素1的位置不对,却还要进行7轮排序,太麻烦了吧?

 

那我们的鸡尾酒排序正是要解决这种问题,让我们来看一看鸡尾酒排序的过程吧。

这就是鸡尾酒排序的思路。

总结

第七轮结果(2和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】
刚刚的「鸡尾酒排序」过程,我们也可以用动图演示👇

5. 代码优化

排序过程就像大摆锤一样,第一轮从左到右第二轮从右到左第三轮再从左到右

🛫送所有正在努力的大家一句话:你不一定逆风翻盘,但一定要向阳而生🌅
 
🔥热榜必看文章:室友打一把王者就学会了冒泡排序算法

让我们来回顾一下冒泡排序针对有序区的优化思路:

本文转自 https://blog.csdn.net/m0_63325890/article/details/122122400

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论