鸡尾酒排序

鸡尾酒排序，也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

C代码如下：

 1 #include<stdio.h>    
 2 #include<string.h>   
 3 #include<math.h>   
 4 #include<ctype.h>   
 5 #include<stdbool.h>  
 6 
 7 void swap(int *a, int *b)   //交换两元素的值
 8 {
 9     int t;
10     t=*a;
11     *a=*b;
12     *b=t;
13 }
14 
15 void printArray(int a[], int count)   //打印数组元素
16 {
17     int i;
18     for(i=0; i<count; i++)
19         printf("%d ",a[i]);
20     printf("\n");
21 }
22 
23 void cocktail_sort(int a[], int size){    //数组中的第一个数为0索引
24     int i,bottom = 0;
25     int top = size - 1;
26     bool swapped = true; 
27     while(swapped)    //假如没有元素交换，则数组有序
28     {
29         swapped = false; 
30         for(i = bottom; i < top; i++)
31         {
32             if(a[i] > a[i + 1])      //判断两个元素是否正确的顺序
33             {
34                 swap(&a[i], &a[i + 1]);     //让两个元素交换顺序
35                 swapped = true;
36             }
37         }
38         // 将未排序部分的最大元素交换到顶端
39         top = top - 1; 
40         for(i = top; i > bottom; i--)
41         {
42             if(a[i] < a[i - 1]) 
43             {
44                 swap(&a[i], &a[i - 1]);
45                 swapped = true;
46             }
47         }
48         //将未排序部分的最小元素交换到底端
49         bottom = bottom + 1;  
50     }
51 }
52 
53 int main(void)   
54 {
55     int a[]={3, 5, 4, 6, 9, 7, 8, 0, 1};
56     int n=sizeof(a)/sizeof(*a);
57     printArray(a,n);
58     cocktail_sort(a,n);
59     printArray(a,n);
60     return 0;
61 }

与冒泡排序不同的地方

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。

以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲，优点只有观念简单这一点

复杂度

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