雞尾酒排序(Cocktail Sort)演算法又稱為搖晃排序(Shaker Sort)演算法、雙向氣泡排序(Bidirectional Bubble Sort)演算法,顧名思義,它是氣泡排序(Bubble Sort)演算法的變體,將原本單向走訪的氣泡排序改為雙向,用以解決使用氣泡排序法時,序列中未排序的一端其實已經大致排序好,卻又不能儘快把它完成的情形。



雞尾酒排序法(Cocktail Sort)

雞尾酒排序法的概念

雞尾酒排序法是基於氣泡排序法的演算法,如果您還不了解氣泡排序法的話,請先參考這篇文章:

https://magiclen.org/bubble-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
               ※

cocktail-sort

雞尾酒排序法的程式實作

雞尾酒排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目備註
最差時間複雜度#{{O(n^2)}}#排序已經反向排序過的序列。
最佳時間複雜度#{{O(n)}}#排序已經正向排序過的序列。
平均時間複雜度#{{O(n^2)}}#
額外最差空間複雜度#{{O(1)}}#
是否穩定