雞尾酒排序(Cocktail Sort)演算法，雙向的氣泡排序法

雞尾酒排序(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
               ※

雞尾酒排序法的程式實作

/// 雞尾酒排序法(遞增)。
pub fn cocktail_sort(array: &mut [i32]) {
    let length = array.len();
    let length_dec = length - 1;

    for i in (1..length).rev() {
        let mut sorted = true;

        let s = length_dec - i;

        for j in s..i {
            let jj = j + 1;

            if array[j] > array[jj] {
                array.swap(j, jj);

                sorted = false;
            }
        }

        if sorted {
            break;
        }

        sorted = true;

        for j in (s..(i - 1)).rev() {
            let jj = j + 1;

            if array[j] > array[jj] {
                array.swap(j, jj);

                sorted = false;
            }
        }

        if sorted {
            break;
        }
    }
}

/// 雞尾酒排序法(遞減)。
pub fn cocktail_sort_desc(array: &mut [i32]) {
    let length = array.len();
    let length_dec = length - 1;

    for i in (1..length).rev() {
        let mut sorted = true;

        let s = length_dec - i;

        for j in s..i {
            let jj = j + 1;

            if array[j] < array[jj] {
                array.swap(j, jj);

                sorted = false;
            }
        }

        if sorted {
            break;
        }

        sorted = true;

        for j in (s..(i - 1)).rev() {
            let jj = j + 1;

            if array[j] < array[jj] {
                array.swap(j, jj);

                sorted = false;
            }
        }

        if sorted {
            break;
        }
    }
}

/**
 * 雞尾酒排序法(遞增)。
 */
public static void cocktailSort(final int[] array) {
    final int length = array.length;
    final int lengthDec = length - 1;

    for (int i = lengthDec; i > 0; --i) {
        boolean sorted = true;

        final int s = lengthDec - i;

        for (int j = s; j < i; ++j) {
            final int jj = j + 1;

            if (array[j] > array[jj]) {
                final int temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }

        sorted = true;

        for (int j = i - 2; j >= s; --j) {
            final int jj = j + 1;

            if (array[j] > array[jj]) {
                final int temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

/**
 * 雞尾酒排序法(遞減)。
 */
public static void cocktailSortDesc(final int[] array) {
    final int length = array.length;
    final int lengthDec = length - 1;

    for (int i = lengthDec; i > 0; --i) {
        boolean sorted = true;

        final int s = lengthDec - i;

        for (int j = s; j < i; ++j) {
            final int jj = j + 1;

            if (array[j] < array[jj]) {
                final int temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }

        sorted = true;

        for (int j = i - 2; j >= s; --j) {
            final int jj = j + 1;

            if (array[j] < array[jj]) {
                final int temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

/**
 * 雞尾酒排序法(遞增)。
 */
function cocktailSort(array: number[]) {
    const length = array.length;
    const lengthDec = length - 1;

    for (let i = lengthDec;i > 0;i--) {
        let sorted = true;

        const s = lengthDec - i;

        for (let j = s;j < i;j++) {
            const jj = j + 1;

            if (array[j] > array[jj]) {
                const temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }

        sorted = true;

        for (let j = i - 2;j >= s;j--) {
            const jj = j + 1;

            if (array[j] > array[jj]) {
                const temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

/**
 * 雞尾酒排序法(遞減)。
 */
function cocktailSortDesc(array: number[]) {
    const length = array.length;
    const lengthDec = length - 1;

    for (let i = lengthDec;i > 0;i--) {
        let sorted = true;

        const s = lengthDec - i;

        for (let j = s;j < i;j++) {
            const jj = j + 1;

            if (array[j] < array[jj]) {
                const temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }

        sorted = true;

        for (let j = i - 2;j >= s;j--) {
            const jj = j + 1;

            if (array[j] < array[jj]) {
                const temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

// 雞尾酒排序法(遞增)。
func CocktailSort(array []int) {
	length := len(array)
	lengthDec := length - 1

	for i := lengthDec; i > 0; i -= 1 {
		sorted := true

		s := lengthDec - i

		for j := s; j < i; j += 1 {
			jj := j + 1

			if array[j] > array[jj] {
				array[j], array[jj] = array[jj], array[j]

				sorted = false
			}
		}

		if sorted {
			break
		}

		sorted = true

		for j := i - 2; j >= s; j -= 1 {
			jj := j + 1

			if array[j] > array[jj] {
				array[j], array[jj] = array[jj], array[j]

				sorted = false
			}
		}

		if sorted {
			break
		}
	}
}

// 雞尾酒排序法(遞減)。
func CocktailSortDesc(array []int) {
	length := len(array)
	lengthDec := length - 1

	for i := lengthDec; i > 0; i -= 1 {
		sorted := true

		s := lengthDec - i

		for j := s; j < i; j += 1 {
			jj := j + 1

			if array[j] < array[jj] {
				array[j], array[jj] = array[jj], array[j]

				sorted = false
			}
		}

		if sorted {
			break
		}

		sorted = true

		for j := i - 2; j >= s; j -= 1 {
			jj := j + 1

			if array[j] < array[jj] {
				array[j], array[jj] = array[jj], array[j]

				sorted = false
			}
		}

		if sorted {
			break
		}
	}
}

雞尾酒排序法的複雜度