鸡尾酒排序(Cocktail Sort)算法又称为摇晃排序(Shaker Sort)算法、双向冒泡排序(Bidirectional Bubble Sort)算法,顾名思义,它是冒泡排序(Bubble Sort)算法的变体,将原本单向走访的冒泡排序改为双向,用以解决使用冒泡排序法时,串行中未排序的一端其实已经大致排序好,却又不能尽快把它完成的情形。

鸡尾酒排序法(Cocktail Sort)

鸡尾酒排序法的概念

鸡尾酒排序法是基于冒泡排序法的算法,如果您还不了解冒泡排序法的话,请先参考这篇文章:

鸡尾酒排序法会从串行的两端开始向个别的另一端进行走访,在每次迭代时,两端的走访循环都会拿当前索引位置的元素与其下一个索引位置的元素进行比较,从前端开始的走访比较策略是:如果下一个元素比较小,就进行交换;如果下一个元素没有比较小,就不进行交换;而从尾端开始的走访比较策略是:如果下一个元素比较大,就进行交换;如果下一个元素没有比较大,就不进行交换。当串行被各端走访完一次之后,串行的最尾端元素即为最大的元素,最前端的元素即为最小的元素。再来从两端重新走访一次串行,用同样的方法将第二大的元素值挤进串行的从尾端开始倒数的第二个位置,将第二小的元素值挤进串行的从前端开始数的第二个位置。从两端重新走访一次串行,用同样的方法将第三大的元素值挤进串行的从尾端开始倒数的第三个位置,将第三小的元素值挤进串行的从前端开始数的第三个位置。依此类推,直到所有元素都被挤到尾端或前端,或是在各端走访串行的过程中,如果发现都没有元素被交换的话,表示此时的串行已经完成排序了。

鸡尾酒排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

要如何将它递增排列呢?

一开始,从数组最前方开始,逐次两两比较元素的大小,将两个元素中较大的元素排在后面,即可逐渐将最大的元素从数组前方挤到数组后方。这部份和冒泡排序法是一模一样的,过程如下:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                       └┬┘
                      81 > 2

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                       └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                           └┬┘
                          81 > 47

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                               └┬┘
                              81 > 61

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                                   └┬┘
                                  81 > 32

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                       └┬┘
                                      81 > 79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81

再来就是鸡尾酒排序法的创新部份了。从数组尚未排序好的尾端开始,逐次两两比较元素的大小,将两个元素中较大的元素排在后面,即可逐渐将最小的元素从数组后方挤到数组前方。过程如下:

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                                   └┬┘
                                   32 < 79

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                               └┬┘
                               61 > 32

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  32  61  79  81
                               └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  32  61  79  81
                           └┬┘
                           47 > 32

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  32  47  61  79  81
                           └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  32  47  61  79  81
                       └┬┘
                       2 < 32

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  32  47  61  79  81
                   └┬┘
                    9 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   2   9  32  47  61  79  81
                   └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   2   9  32  47  61  79  81
               └┬┘
               38 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30   2  38   9  32  47  61  79  81
               └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30   2  38   9  32  47  61  79  81
           └┬┘
           30 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69   2  30  38   9  32  47  61  79  81
           └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69   2  30  38   9  32  47  61  79  81
       └┬┘
       69 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  69  30  38   9  32  47  61  79  81
       └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  69  30  38   9  32  47  61  79  81

接下来就是一直不断地在未排序范围内做「把最大值从前端挤到后端」和「把最小值从后端挤到前端」的动作。完整过程如下:

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
           └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
               └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                   └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                       └┬┘
                      81 > 2

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                       └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                           └┬┘
                          81 > 47

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                           └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                               └┬┘
                              81 > 61

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                               └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                                   └┬┘
                                  81 > 32

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                   └─┘

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                       └┬┘
                                      81 > 79

       ●                                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                                   └┬┘
                                   32 < 79

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                               └┬┘
                               61 > 32

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  32  61  79  81
                               └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  32  61  79  81
                           └┬┘
                           47 > 32

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  32  47  61  79  81
                           └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  32  47  61  79  81
                       └┬┘
                       2 < 32

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  32  47  61  79  81
                   └┬┘
                    9 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   2   9  32  47  61  79  81
                   └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   2   9  32  47  61  79  81
               └┬┘
               38 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30   2  38   9  32  47  61  79  81
               └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30   2  38   9  32  47  61  79  81
           └┬┘
           30 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69   2  30  38   9  32  47  61  79  81
           └─┘

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69   2  30  38   9  32  47  61  79  81
       └┬┘
       69 > 2

       ●                              ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  69  30  38   9  32  47  61  79  81
       └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  69  30  38   9  32  47  61  79  81

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  69  30  38   9  32  47  61  79  81
           └┬┘
           69 > 30

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  69  38   9  32  47  61  79  81
           └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  69  38   9  32  47  61  79  81
               └┬┘
               69 > 38

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38  69   9  32  47  61  79  81
               └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38  69   9  32  47  61  79  81
                   └┬┘
                   69 > 9

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  69  32  47  61  79  81
                   └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  69  32  47  61  79  81
                       └┬┘
                       69 > 32

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  69  47  61  79  81
                       └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  69  47  61  79  81
                           └┬┘
                           69 > 47

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  69  61  79  81
                           └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  69  61  79  81
                               └┬┘
                               69 > 61

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
                               └─┘

       ○  ●                          ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
                                   └┬┘
                                   69 < 79

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
                               └┬┘
                              61 < 69

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
                           └┬┘
                           47 < 61

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
                       └┬┘
                       32 < 47

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
                   └┬┘
                   9 < 32

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30  38   9  32  47  61  69  79  81
               └┬┘
               38 > 9

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30   9  38  32  47  61  69  79  81
               └─┘

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2  30   9  38  32  47  61  69  79  81
           └┬┘
           30 > 9

       ○  ●                      ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
           └─┘

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
               └┬┘
               30 < 38

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
                   └┬┘
                   38 > 32

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                   └─┘

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                       └┬┘
                      38 < 47

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                           └┬┘
                          47 < 61

       ○  ○  ●                  ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                               └┬┘
                              61 < 69

       ○  ○  ●              ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81

       ○  ○  ●              ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                           └┬┘
                           47 < 61

       ○  ○  ●              ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                       └┬┘
                       38 < 47

       ○  ○  ●              ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                   └┬┘
                   32 < 38

       ○  ○  ●              ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
               └┬┘
              30 < 32

       ○  ○  ●              ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
               ※

鸡尾酒排序法的排序过程动画

鸡尾酒排序法的程序实作

鸡尾酒排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(n^2)}}# 排序已经反向排序过的串行。
最佳时间复杂度 #{{O(n)}}# 排序已经正向排序过的串行。
平均时间复杂度 #{{O(n^2)}}#
最差空间复杂度 #{{O(1)}}#
是否稳定 是