昨天小灰发布的五分钟学算法漫画中存在一些勘误,所以今天重新发布一篇修订版,修正了代码当中的一些细节问题。


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


五分钟学算法漫画:什么是冒泡排序?


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



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



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

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


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


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


让我们来举一个栗子:


五分钟学算法漫画:什么是鸡尾酒排序?(修订版)


有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; i++)

  5.    {

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

  7.        boolean isSorted = true;

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

  9.        for(int j=i; j<array.length-i-1; 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.        }

    1.     //偶数轮之前,重新标记为true

  23.        isSorted = true;

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

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

  26.        {

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

  28.            {

  29.                tmp = array[j];

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

  31.                array[j-1] = tmp;

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

  33.                isSorted = false;

  34.            }

  35.        }

  36.        if(isSorted){

  37.            break;

  38.        }

  39.    }

  40. }

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

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

  43.    sort(array);

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

  45. }

}


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



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



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


原始的冒泡排序,有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是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.        }

    1.     //偶数轮之前,重新标记为true

  33.        isSorted = true;

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

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

  36.        {

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

  38.            {

  39.                tmp = array[j];

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

  41.                array[j-1] = tmp;

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

  43.                isSorted = false;

  44.                lastLeftExchangeIndex = j;

  45.            }

  46.        }

  47.        leftSortBorder = lastLeftExchangeIndex;

  48.        if(isSorted){

  49.            break;

  50.        }

  51.    }

  52. }

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

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

  55.    sort(array);

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

  57. }

}


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


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



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)



五分钟学算法漫画:什么是鸡尾酒排序?(修订版)




—————END—————




喜欢本文的朋友们,欢迎长按下图关注订阅号程序员小灰,收看更多精彩内容

五分钟学算法漫画:什么是鸡尾酒排序?(修订版)

原文始发于微信公众号(程序员小灰):五分钟学算法漫画:什么是鸡尾酒排序?(修订版)