鸡尾酒排序

鸡尾酒排序

使用鸡尾酒排序為一列数字进行排序的过程
分類	排序算法
數據結構	数组
最差時間複雜度	$O(n^2)$
最優時間複雜度	$O(n)$
平均時間複雜度	$O(n^2)$
最佳算法	No

鸡尾酒排序，也就是定向冒泡排序, 雞尾酒攪拌排序, 攪拌排序 (也可以視作選擇排序的一種變形), 漣漪排序, 來回排序 or 快乐小時排序, 是冒泡排序的一種变形。此演算法与冒泡排序的不同處在於排序時是以双向在序列中進行排序。

伪代码

伪代码是以 C语言撰写，目的在将一个序列由小到大进行排序：

function cocktail_sort(list, list_length){ // the first element of list has index 0
    bottom = 0;
    top = list_length - 1;
    swapped = true; 
    while(swapped == true) // if no elements have been swapped, then the list is sorted
    {
        swapped = false; 
        for(i = bottom; i < top; i = i + 1)
        {
            if(list[i] > list[i + 1])  // test whether the two elements are in the correct order
            {
                swap(list[i], list[i + 1]); // let the two elements change places
                swapped = true;
            }
        }
        // decreases top the because the element with the largest value in the unsorted
        // part of the list is now on the position top 
        top = top - 1; 
        for(i = top; i > bottom; i = i - 1)
        {
            if(list[i] < list[i - 1]) 
            {
                swap(list[i], list[i - 1]);
                swapped = true;
            }
        }
        // increases bottom because the element with the smallest value in the unsorted 
        // part of the list is now on the position bottom 
        bottom = bottom + 1;  
    }
}

与冒泡排序不同的地方

鸡尾酒排序等於是冒泡排序的輕微變形。不同的地方在於從低到高然後從高到低，而冒泡排序則僅從低到高去比較序列裡的每個元素。他可以得到比冒泡排序稍微好一點的效能，原因是冒泡排序只從一個方向進行比對(由低到高)，每次循環只移動一個項目。

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

複雜度

鸡尾酒排序最糟或是平均所花費的次數都是$O(n^2)$，但如果序列在一開始已經大部分排序過的話，會接近$O(n)$。

額外連結

• Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
• Implementations of cocktail sort in several different programming languages