排序算法之鸡尾酒排序

JAVA herman 291浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
饿了么大量招人,我内推!Java 方向!薪资不设上限,工作年龄不限!工作地点限魔都,可电话面试!简历,发我微信:codedq
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

正如我上一篇文章所说,冒泡排序虽然简单,也很稳定,复杂度也不是最高的。但是它还存在在不少的优化空间,于是诞生了很多基于冒泡排序的改进算法,今天我们要讲的鸡尾酒排序算法就是其中之一。

鸡尾酒排序,也就是定向冒泡排序,鸡尾酒搅拌排序,搅拌排序(也可以视作选择排序的一种变形),涟漪排序,来回排序或快乐小时排序,是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

排序过程:

  • 先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端
  • 再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端
  • 以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问一次序列就可以完成排序,但如果使用冒泡排序则需要四次。但是在随机数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。

鸡尾酒排序的 Java 案例代码如下所示:

public static void cocktail_sort(int[] arr) {   
    int i, left = 0, right = arr.length - 1;
    int temp;
    while (left < right) {
        for (i = left; i < right; i++)
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        right--;
        for (i = right; i > left; i--)
            if (arr[i - 1] > arr[i]) {
                temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
            }
        left++;
    }
}

排序动态效果图如下所示:

鸡尾酒排序动画

鸡尾酒排序最糟或是平均所花费的次数都是平方阶平方阶 (O(n2)) ,但如果序列在一开始已经大部分排序过的话,会接近线性阶 (O(n))。

如果需要其他语言的鸡尾酒排序代码,可以微信我,我贴上来!

鸡尾酒排序的使用场景:在「大部分元素有序」的情况下,使用鸡尾酒排序可以减少排序的回合数。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 排序算法之鸡尾酒排序