鸡尾酒排序

伪代码

将一个序列由小到大进行排序：
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)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在随机数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲。

C语言

1 void cocktail_sort(int arr[], int len) { 2 int i, left = 0, right = len - 1; 3 int temp; 4 while (left < right) { 5 for (i = left; i < right; i++) 6 if (arr[i] > arr[i + 1]) { 7 temp = arr[i]; 8 arr[i] = arr[i + 1]; 9 arr[i + 1] = temp;10 }11 right--;12 for (i = right; i > left; i--)13 if (arr[i - 1] > arr[i]) {14 temp = arr[i];15 arr[i] = arr[i - 1];16 arr[i - 1] = temp;17 }18 left++;19 }20 }

C++

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能void cocktail_sort(T arr[], int len) {
int j, left = 0, right = len - 1;
while (left < right) {
for (j = left; j < right; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
right--;
for (j = right; j > left; j--)
if (arr[j - 1] > arr[j])
swap(arr[j - 1], arr[j]);
left++;
}}

JAVA

1 public static void cocktail_sort(int[] arr) {
 2 int i, left = 0, right = arr.length - 1; 3 int temp; 4 while (left < right) { 5 for (i = left; i < right; i++) 6 if (arr[i] > arr[i + 1]) { 7 temp = arr[i]; 8 arr[i] = arr[i + 1]; 9 arr[i + 1] = temp;10 }11 right--;12 for (i = right; i > left; i--)13 if (arr[i - 1] > arr[i]) {14 temp = arr[i];15 arr[i] = arr[i - 1];16 arr[i - 1] = temp;17 }18 left++;19 }20 }

JavaScript

1 Array.prototype.cocktail_sort = function() { 2 var i, left = 0, right = this.length - 1; 3 var temp; 4 while (left < right) { 5 for (i = left; i < right; i++) 6 if (this[i] > this[i + 1]) { 7 temp = this[i]; 8 this[i] = this[i + 1]; 9 this[i + 1] = temp;10 }11 right--;12 for (i = right; i > left; i--)13 if (this[i - 1] > this[i]) {14 temp = this[i];15 this[i] = this[i - 1];16 this[i - 1] = temp;17 }18 left++;19 }20 };

PHP

1 function swap(&$x, &$y) { 2 $t = $x; 3 $x = $y; 4 $y = $t; 5 } 6 function cocktail_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參才能修改原陣列 7 $left = 0; 8 $right = count($arr) - 1; 9 while ($left < $right) {10 for ($j = $left; $j < $right; $j++)11 if ($arr[$j] > $arr[$j + 1])12 swap($arr[$j], $arr[$j + 1]);13 $right--;14 for ($j = $right; $j > $left; $j--)15 if ($arr[$j - 1] > $arr[$j])16 swap($arr[$j - 1], $arr[$j]);17 $left++;18 }19 }

Python 2.7

1 def cocktail_sort(l): 2     l_len = len(l) 3     for i in range(l_len, 0, -1): 4         rem_i_l_len = abs(i - l_len) 5         isNeedContinue = False 6         obverse_count = len(l[rem_i_l_len : i-1]) 7         reverse_count = len(l[rem_i_l_len + 1 : i-1]) 8         
 9         for j in range(obverse_count):10             if l[j] > l[j + 1]:11                 l[j], l[j + 1] = l[j + 1], l[j]12                 isNeedContinue = True13         # you can print this to observe the whole process14         # print l15         
16         for j in range(reverse_count, 0, -1):17             if l[j] < l[j - 1]:18                 l[j], l[j - 1] = l[j - 1], l[j]19                 isNeedContinue = True20         # you can print this to observe the whole process21         # print l22         
23         if isNeedContinue:24             continue25         else:26             return27   
28         
29 if __name__ == '__main__':30     sample_list = [6,5,4,3,2,100]31     cocktail_sort(sample_list)32     print(sample_list)

Golang

1 func cocktailSort(arr []int) { 2 i, left := 0, 0 3 right := len(arr) - 1 4 var temp int 5 for left < right { 6 for i = left; i < right; i++ { 7 if arr[i] > arr[i+1] { 8 temp = arr[i] 9 arr[i] = arr[i+1]10 arr[i+1] = temp11 }12 }13 right--14 15 for i = right; i > left; i-- {16 if arr[i-1] > arr[i] {17 temp = arr[i]18 arr[i] = arr[i-1]19 arr[i-1] = temp20 }21 }22 left++23 }24 }

复杂度

鸡尾酒排序最糟或是平均所花费的次数都是，但如果序列在一开始已经大部分排序过的话，会接近。