雞尾酒(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