推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 蓝桥杯 > 什么是冒泡排序和鸡尾酒排序?

什么是冒泡排序和鸡尾酒排序?

蓝桥杯 2019-02-11


冒泡排序


冒泡排序的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。


冒泡排序算法的原理


  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

  • 针对所有的元素重复以上的步骤,除了最后一个。

  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

一般情况下,可以通过下面的动画理解冒泡排序。


现在我们来看一组特殊数据如果使用冒泡排序会怎么样。


将无序数列:2,3,4,5,6,7,8,1,使用冒泡排序使其从小到大排序。



什么是冒泡排序和鸡尾酒排序?


进行逐步分析:

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

    什么是冒泡排序和鸡尾酒排序?

  2. 第二轮操作( 7 和 1 交换 )

    什么是冒泡排序和鸡尾酒排序?

  3. 第三轮操作( 6 和 1 交换 )

    什么是冒泡排序和鸡尾酒排序?

  4. 第四轮操作( 5 和 1 交换 )

    什么是冒泡排序和鸡尾酒排序?

  5. 第五轮操作( 4 和 1 交换 )

    什么是冒泡排序和鸡尾酒排序?

  6. 第六轮操作( 3 和 1 交换 )

    什么是冒泡排序和鸡尾酒排序?

  7. 第七轮操作( 2 和 1 交换 )

    什么是冒泡排序和鸡尾酒排序?

仔细观察上面的这组无序数列,实际上只有 1 的位置不在该在的位置,而 2 ,3 ,4 ,5 ,6 ,7 ,8 都已经有序了,结果使用冒泡排序,需要 折腾 7 次 才能将 1 归位。


鸡尾酒排序


什么是冒泡排序和鸡尾酒排序?


鸡尾酒排序,也就是定向冒泡排序,鸡尾酒搅拌排序,搅拌排序(也可以视作选择排序的一种变形),涟漪排序,来回排序或快乐小时排序,是冒泡排序的一种变形。


此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。


排序过程:

  • 先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端

  • 再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端

  • 以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束


Show Me The Animation

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

    什么是冒泡排序和鸡尾酒排序?

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

    什么是冒泡排序和鸡尾酒排序?

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

    什么是冒泡排序和鸡尾酒排序?

在这一轮操作中,没有元素位置交换,证明已经有序,排序结束。对比 冒泡排序 ,鸡尾酒排序只需要 3 轮操作就可以完成排序。





什么是冒泡排序和鸡尾酒排序?

好文章那么多,千万别走散了

点击下方阅读原文↓

进入蓝桥微官网,阅读更多技术干货

来源:五分钟学算法  原文链接:

https://juejin.im/post/5c37e5096fb9a049d05df191

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《什么是冒泡排序和鸡尾酒排序?》的版权归原作者「蓝桥杯」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注蓝桥杯微信公众号

蓝桥杯微信公众号:bluebridgecup

蓝桥杯

手机扫描上方二维码即可关注蓝桥杯微信公众号

蓝桥杯最新文章

精品公众号随机推荐