[TOC]
## 算法原理
為什么叫雞尾酒排序？其實我也不知道，知道的小伙伴請告訴我。
其實它還有很多**奇怪**的名稱，比如雙向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、搖曳排序 (Shuffle Sort)、飛梭排序 (Shuttle Sort) 和歡樂時光排序 (Happy Hour Sort)。本文中就以雞尾酒排序來稱呼它。
> 雞尾酒排序是[冒泡排序](http://bubkoo.com/2014/01/12/sort-algorithm/bubble-sort/)的輕微變形。不同的地方在于，雞尾酒排序是從低到高然后從高到低來回排序，而冒泡排序則僅從低到高去比較序列里的每個元素。他可比冒泡排序的效率稍微好一點，原因是冒泡排序只從一個方向進行比對(由低到高)，每次循環只移動一個項目。
以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問一次序列就可以完成排序，但如果使用冒泡排序則需要四次。但是在亂數序列狀態下，雞尾酒排序與冒泡排序的效率都很差勁，優點只有原理簡單這一點。
排序過程：
1. 先對數組從左到右進行冒泡排序（升序），則最大的元素去到最右端
2. 再對數組從右到左進行冒泡排序（降序），則最小的元素去到最左端
3. 以此類推，依次改變冒泡的方向，并不斷縮小未排序元素的范圍，直到最后一個元素結束
[](https://box.kancloud.cn/2015-07-26_55b458cfe0128.gif "圖片來自維基百科")
圖片來自維基百科
## 實例分析
以數組 array = [45, 19, 77, 81, 13, 28, 18, 19, 77] 為例，排序過程如下：
從左到右，找到最大的數 81，放到數組末尾：
~~~
┌─────────────────────────────────────────┐
│ 19 45 77 13 28 18 19 77 │ 81
└─────────────────────────────────────────┘
~~~
從右到左，找到剩余數組（先框中的部分）中最小的數 ，放到數組開頭：
~~~
┌────────────────────────────────────┐
13 │ 19 45 77 18 28 19 77 │ 81
└────────────────────────────────────┘
~~~
從左到右，在剩余數組中找到最大數，放在剩余數組的末尾：
~~~
┌───────────────────────────────┐
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 語言實現
慣例，看代碼：
~~~
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;
}
}
~~~
## 參考文章
* [維基百科，自由的百科全書](http://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F)
* [Cocktail Sort Algorithm or Shaker Sort Algorithm](http://www.codingunit.com/cocktail-sort-algorithm-or-shaker-sort-algorithm)
* [Sorting Algorithms: The Cocktail Sort](http://buffered.io/posts/sorting-algorithms-the-cocktail-sort/)
* [[演算法]搖晃排序法(Shaker Sort)](http://notepad.yehyeh.net/Content/Algorithm/Sort/Shaker/Shaker.php)
* [冒泡排序與雞尾酒排序](http://www.cnblogs.com/wuweiblog/archive/2011/07/11/2103325.html)
