排序算法之鸡尾酒排序

公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序

腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

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

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

排序过程：

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

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

以序列(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）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

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