（8）雞尾酒排序 (Cocktail Sort/Shaker Sort)

算法原理

為什么叫雞尾酒排序？其實我也不知道，知道的小伙伴請告訴我。

其實它還有很多奇怪的名稱，比如雙向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、搖曳排序 (Shuffle Sort)、飛梭排序 (Shuttle Sort) 和歡樂時光排序 (Happy Hour Sort)。本文中就以雞尾酒排序來稱呼它。

雞尾酒排序是冒泡排序的輕微變形。不同的地方在于，雞尾酒排序是從低到高然后從高到低來回排序，而冒泡排序則僅從低到高去比較序列里的每個元素。他可比冒泡排序的效率稍微好一點，原因是冒泡排序只從一個方向進(jìn)行比對(由低到高)，每次循環(huán)只移動一個項目。

以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問一次序列就可以完成排序，但如果使用冒泡排序則需要四次。但是在亂數(shù)序列狀態(tài)下，雞尾酒排序與冒泡排序的效率都很差勁，優(yōu)點只有原理簡單這一點。

排序過程：

1. 先對數(shù)組從左到右進(jìn)行冒泡排序（升序），則最大的元素去到最右端
2. 再對數(shù)組從右到左進(jìn)行冒泡排序（降序），則最小的元素去到最左端
3. 以此類推，依次改變冒泡的方向，并不斷縮小未排序元素的范圍，直到最后一個元素結(jié)束

圖片來自維基百科

實例分析

以數(shù)組 array = [45, 19, 77, 81, 13, 28, 18, 19, 77] 為例，排序過程如下：

從左到右，找到最大的數(shù) 81，放到數(shù)組末尾：

┌─────────────────────────────────────────┐
│  19   45   77   13   28   18   19   77  │  81
└─────────────────────────────────────────┘

從右到左，找到剩余數(shù)組（先框中的部分）中最小的數(shù) ，放到數(shù)組開頭：

    ┌────────────────────────────────────┐
13  │  19   45   77   18   28   19   77  │   81
    └────────────────────────────────────┘

從左到右，在剩余數(shù)組中找到最大數(shù)，放在剩余數(shù)組的末尾：

    ┌───────────────────────────────┐
13  │  19   45   18   28   18   77  │   77   81
    └───────────────────────────────┘

從右到左

         ┌──────────────────────────┐
13   18  │  19   45   18   28   77  │   77   81
         └──────────────────────────┘

從左到右

         ┌─────────────────────┐
13   18  │  19   18   28   45  │  77   77   81
         └─────────────────────┘

從右到左

              ┌────────────────┐
13   18   18  │  19   28   45  │  77   77   81
              └────────────────┘

從左到右

              ┌───────────┐
13   18   18  │  19   28  │  45   77   77   81
              └───────────┘

從右到左

                   ┌──────┐
13   18   18   19  │  28  │  45   77   77   81
                   └──────┘

JavaScript 語言實現(xiàn)

慣例，看代碼：

function shakerSort(array) {

    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    var length = array.length,
        left = 0,
        right = length - 1,
        lastSwappedLeft = left,
        lastSwappedRight = right,
        i,
        j;

    while (left < right) {
        // 從左到右
        lastSwappedRight = 0;
        for (i = left; i < right; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                lastSwappedRight = i;
            }
        }
        right = lastSwappedRight;
        // 從右到左
        lastSwappedLeft = length - 1;
        for (j = right; left < j; j--) {
            if (array[j - 1] > array[j]) {
                swap(array, j - 1, j)
                lastSwappedLeft = j
            }
        }
        left = lastSwappedLeft;
    }
}

參考文章

• 維基百科，自由的百科全書
• Cocktail Sort Algorithm or Shaker Sort Algorithm
• Sorting Algorithms: The Cocktail Sort
• [演算法]搖晃排序法(Shaker Sort)
• 冒泡排序與雞尾酒排序