微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

漫画:什么是鸡尾酒排序?

2018-07-31 09:51 小灰

来自:程序员小灰(微信号:chengxuyuanxiaohui)



在上一篇漫画中,小灰介绍了冒泡排序的思路和几种变化:


漫画:什么是冒泡排序?


那么,鸡尾酒排序又是何方神圣呢?我们这一期将会详细讲述。







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

冒泡排序的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。算法的每一轮从都是从左到右比较元素,进行单向的位置交换


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


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


让我们来举一个栗子:



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


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


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




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




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




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




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




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




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








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


第一轮(和冒泡排序一样,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比较,位置不变。


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



这就是鸡尾酒排序的思路。排序过程就像钟摆一样,第一轮从左到右,第二轮从右到左,第三轮再从左到右......







public class CockTailSort {

 
           
  1. private static void sort(int array[])

  2. {

  3.     int tmp  = 0;

  4.    for(int i=0; i<array.length/2-1; i++)

  5.    {

  6.        //有序标记,每一轮的初始是true

  7.        boolean isSorted = true;

  8.        //奇数轮,从左向右比较和交换

  9.        for(int j=i; j<array.length-i  ; j++)

  10.        {

  11.            if(array[j] > array[j+1])

  12.            {

  13.                tmp = array[j];

  14.                array[j] = array[j+1];

  15.                array[j+1] = tmp;

  16.                //有元素交换,所以不是有序,标记变为false

  17.                isSorted = false;

  18.            }

  19.        }

  20.        if(isSorted){

  21.            break;

  22.        }

  23.        //偶数轮,从右向左比较和交换

  24.        for(int j=array.length-i-1; j>i; j--)

  25.        {

  26.            if(array[j] < array[j-1])

  27.            {

  28.                tmp = array[j];

  29.                array[j] = array[j-1];

  30.                array[j-1] = tmp;

  31.                //有元素交换,所以不是有序,标记变为false

  32.                isSorted = false;

  33.            }

  34.        }

  35.        if(isSorted){

  36.            break;

  37.        }

  38.    }

  39. }

  40. public static void main(String[] args){

  41.    int[] array = new int[]{2,3,4,5,6,7,8,1};

  42.    sort(array);

  43.    System.out.println(Arrays.toString(array));

  44. }

}


这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。







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


原始的冒泡排序,有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2 ......


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



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



public class CockTailSort {

 
           
  1. private static void sort(int array[])

  2. {

  3.    int tmp  = 0;

  4.    //记录右侧最后一次交换的位置

  5.    int lastRightExchangeIndex = 0;

  6.    //记录左侧最后一次交换的位置

  7.    int lastLeftExchangeIndex = 0;

  8.    //无序数列的右边界,每次比较只需要比到这里为止

  9.    int rightSortBorder = array.length - 1;

  10.    //无序数列的左边界,每次比较只需要比到这里为止

  11.    int leftSortBorder = 0;

  12.    for(int i=0; i<array.length/2  ; i++)

  13.    {

  14.        //有序标记,每一轮的初始是true

  15.        boolean isSorted = true;

  16.        //奇数轮,从左向右比较和交换

  17.        for(int j=leftSortBorder; j<rightSortBorder; j++)

  18.        {

  19.            if(array[j] > array[j+1])

  20.            {

  21.                tmp = array[j];

  22.                array[j] = array[j+1];

  23.                array[j+1] = tmp;

  24.                //有元素交换,所以不是有序,标记变为false

  25.                isSorted = false;

  26.                lastRightExchangeIndex = j;

  27.            }

  28.        }

  29.        rightSortBorder = lastRightExchangeIndex;

  30.        if(isSorted){

  31.            break;

  32.        }

  33.        //偶数轮,从右向左比较和交换

  34.        for(int j=rightSortBorder; j>leftSortBorder; j--)

  35.        {

  36.            if(array[j] < array[j-1])

  37.            {

  38.                tmp = array[j];

  39.                array[j] = array[j-1];

  40.                array[j-1] = tmp;

  41.                //有元素交换,所以不是有序,标记变为false

  42.                isSorted = false;

  43.                lastLeftExchangeIndex = j;

  44.            }

  45.        }

  46.        leftSortBorder = lastLeftExchangeIndex;

  47.        if(isSorted){

  48.            break;

  49.        }

  50.    }

  51. }

  52. public static void main(String[] args){

  53.    int[] array = new int[]{2,3,4,5,6,7,8,1};

  54.    sort(array);

  55.    System.out.println(Arrays.toString(array));

  56. }

}


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


在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。












●编号709,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

大数据与人工智能

更多推荐18个技术类公众微信

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

 
算法与数据结构 更多文章 从零开始,搭建一个完善的AI应用 微积分也能用来玩游戏,腾讯公布《微积历险记》 为什么程序员一定要学数据结构?数据结构书单推荐~ 数学是普通程序员入门人工智能的最大障碍 5分钟理解一致性哈希算法
猜您喜欢 【抢月饼】Coding 一个新创优秀的国内社交代码托管服务 几句话解释一些中国互联网行业 学会理财,创造财富--读《富爸爸穷爸爸》 FIT2CLOUD发布Jenkins代码部署插件,帮助用户实现持续集成和部署