鸡尾酒(Cocktail)排序是冒泡排序的变体，它在两个方向上交替遍历列表。 它与冒泡排序的不同之处在于，冒泡排序仅在前向方向上遍历列表，而此算法在一次迭代中向前和向后遍历。
1. 算法
在鸡尾酒排序中，一次迭代包括两个阶段：
第一阶段循环遍历数组，如从左到右的冒泡排序。 比较相邻元素，如果左元素大于右元素，则交换这些元素。列表的最大元素放在前向传递中数组的末尾。
第二阶段从最右边未排序的元素到左边循环遍历数组。 比较相邻元素，如果右元素小于左元素，则交换这些元素。 列表的最小元素放在向后传递的数组的开头。
该过程将继续，直到列表变为未排序。
示例
假设有一个数组：A：{8,2,3,1,9}。 使用鸡尾酒(Cocktail)排序对数组的元素进行排序。
迭代1：
前进传递：
8 与 2比较 ; 8>2 → 交换(8,2)
A={2,8,3,1,9}
8 与 3比较 ; 8>3 → 交换(8,3)
A={2,3,8,1,9}
8 与 1 比较 ; 8 > 1 → 交换(8,1)
A = {2,3,1,8,9}
8 与 9 比较; 8<9 → 不交换
在第一次前进传递结束时：列表中最大的元素放在最后。
A={2, 3, 1, 8, 9 }
后退传递：
8 与 1 比较; 8> 1 → 不交换
A={2, 3, 1, 8, 9 }
1 与 3 比较 ; 3>1 → 交换(1,3)
A={2, 1, 3, 8, 9 }
1 与 2 比较 ; 2> 1 → 交换(1,2)
A={1, 2, 3, 8, 9}
在第一次向后通过结束时; 最小元素已放置在数组的第一个索引处。
如果看一下第一步产生的列表; 就发现列表已按升序排序，但算法将完全自行处理。
复杂性
| 复杂性 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 时间复杂性 | O(n^2) | O(n^2) | O(n^2) |
| 空间复杂性 | - | - | O(1) |
使用C语言实现鸡尾酒(Cocktail)排序，代码如下 -
#include <stdio.h>
int temp;
void Cocktail(int a[], int n)
{
int is_swapped = 1;
int begin = 0,i;
int end = n - 1;
while (is_swapped) {
is_swapped = 0;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
if (!is_swapped)
break;
is_swapped = 0;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
++begin;
}
}
int main()
{
int arr[] = {0, 10, 2, 8, 23, 1, 3, 45},i;
int n = sizeof(arr) / sizeof(arr[0]);
Cocktail(arr, n);
printf("printing sorted array :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
执行上面示例代码，得到以下结果：
printing sorted array :
0 1 2 3 8 10 23 45
使用C++语言实现鸡尾酒(Cocktail)排序，代码如下 -
#include <iostream>
using namespace std;
int temp;
void Cocktail(int a[], int n)
{
int is_swapped = 1;
int begin = 0,i;
int end = n - 1;
while (is_swapped) {
is_swapped = 0;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
if (!is_swapped)
break;
is_swapped = 0;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
++begin;
}
}
int main()
{
int arr[] = {0, 10, 2, 8, 23, 1, 3, 45},i;
int n = sizeof(arr) / sizeof(arr[0]);
Cocktail(arr, n);
cout <<"printing sorted array :\n";
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<"\n";
return 0;
}
执行上面示例代码，得到以下结果：
printing sorted array :
0 1 2 3 8 10 23 45
使用Java语言实现鸡尾酒(Cocktail)排序，代码如下 -
public class CocktailSort
{
static int temp;
static void Cocktail(int a[], int n)
{
boolean is_swapped = true;
int begin = 0,i;
int end = n - 1;
while (is_swapped) {
is_swapped = false;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
if (!is_swapped)
break;
is_swapped = false;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
++begin;
}
}
public static void main(String[] args) {
int arr[] = {0, 10, 2, 8, 23, 1, 3, 45},i;
int n = arr.length;
Cocktail(arr, n);
System.out.println("printing sorted array :\n");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
执行上面示例代码，得到以下结果：
printing sorted array :
0 1 2 3 8 10 23 45
使用C#语言实现鸡尾酒(Cocktail)排序，代码如下 -
using System;
public class CocktailSort
{
static int temp;
static void Cocktail(int[] a, int n)
{
Boolean is_swapped = true;
int begin = 0,i;
int end = n - 1;
while (is_swapped) {
is_swapped = false;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
if (!is_swapped)
break;
is_swapped = false;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
++begin;
}
}
public void Main() {
int[] arr = {0, 10, 2, 8, 23, 1, 3, 45};
int n = arr.Length,i;
Cocktail(arr, n);
Console.WriteLine("printing sorted array :\n");
for (i = 0; i < n; i++)
Console.Write(arr[i]+" ");
}
执行上面示例代码，得到以下结果：
printing sorted array :
0 1 2 3 8 10 23 45
