雞尾酒排序


雞尾酒(Cocktail)排序是氣泡排序的變體,它在兩個方向上交替遍歷列表。 它與氣泡排序的不同之處在於,氣泡排序僅在前向方向上遍歷列表,而此演算法在一次疊代中向前和向後遍歷。

1. 演算法

在雞尾酒排序中,一次疊代包括兩個階段:

  1. 第一階段迴圈遍歷陣列,如從左到右的氣泡排序。 比較相鄰元素,如果左元素大於右元素,則交換這些元素。列表的最大元素放在前向傳遞中陣列的末尾。

  2. 第二階段從最右邊未排序的元素到左邊迴圈遍歷陣列。 比較相鄰元素,如果右元素小於左元素,則交換這些元素。 列表的最小元素放在向後傳遞的陣列的開頭。

該過程將繼續,直到列表變為未排序。

範例

假設有一個陣列: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