雞尾酒排序

雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時排序, 是冒泡排序的一種變形。該算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。

基本介紹

• 中文名：雞尾酒排序
• 簡介：定向冒泡排序
• 別名：攪拌排序
• 說明：選擇排序的一種變形

概述

雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時排序, 是冒泡排序的一種變形。該算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。

原理

使用雞尾酒排序為一列數字進行排序的過程可以通過右圖形象的展示出來：

數組中的數字本是無規律的排放，先找到最小的數字，把他放到第一位，然後找到最大的數字放到最後一位。然後再找到第二小的數字放到第二位，再找到第二大的數字放到倒數第二位。以此類推，直到完成排序。

代碼

Java

public static int[] cocktailSort(int[] src){    //將最小值排到隊尾    for(int i = 0 ; i < src.length/2 ; i++)    {        for(int j = i ; j < src.length-i-1 ; j++)        {            if(src[j] < src[j+1])            {                int temp = src[j];                src[j] = src[j+1];                src[j+1] = temp;            }            System.out.println("交換小"+Arrays.toString(src));        }        //將最大值排到隊頭        for(int j = src.length-1-(i+1); j > i ; j--)        {            if(src[j] > src[j-1])            {                int temp = src[j];                src[j] = src[j-1];                src[j-1] = temp;            }            System.out.println("交換大"+Arrays.toString(src));        }        System.out.println("第"+i+"次排序結果："+Arrays.toString(src));    }    return src;}

Pascal

typearra=array[1..10000]of integer;procedure sort(b:arra);var i,bottom,top,t:integer;f:boolean;beginbottom:=1;top:=n;f:=true;while(f=true) dobeginf:=false;for i:=bottom to top-1 doif a[i]>a[i+1] then begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;f:=true;end;top:=top-1;for i:=top downto bottom+1 doif a[i]<a[i-1] then begin t:=a[i];a[i]:=a[i-1];a[i-1]:=t;f:=true end;bottom:=bottom+1;end;end;

C 語言

function cocktail_sort(list, list_length) // the first element of list has index 0{    bottom = 0;    top = list_length - 1;    swapped = true;    bound = 0; //最佳化循環次數，記錄已經排序的邊界，減少循環次數    while(swapped) // 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;                bound = i;            }        }        // 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;        top = bound;        for(i = top; i > bottom; i = i - 1)        {            if(list[i] < list[i-1])            {                swap(list[i], list[i-1]);                swapped = true;                bound = i;            }        }        // 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;        bottom = bound;    }}pytho

python

 def cocktail_sort(l):    size = len(l)    sign = 1      for i in range(size / 2):        if sign:            sign = 0            for j in range(i, size - 1 - i):                if l[j] > l[j + 1]:                    l[j], l[j + 1] = l[j + 1], l[j]            for k in range(size - 2 - i, i, -1):                if l[k] < l[k - 1]:                    l[k], l[k - 1] = l[k - 1], l[k]                    sign = 1          else:            break    print l

與冒泡的區別

雞尾酒排序等於是冒泡排序的輕微變形。不同的地方在於從低到高然後從高到低，而冒泡排序則僅從低到高去比較序列里的每個元素。他可以得到比冒泡排序稍微好一點的效能，原因是冒泡排序只從一個方向進行比對(由低到高)，每次循環只移動一個項目。

以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問兩次（升序降序各一次 ）次序列就可以完成排序，但如果使用冒泡排序則需要四次。

複雜度

雞尾酒排序最糟或是平均所花費的次數都是O(n²)，但如果序列在一開始已經大部分排序過的話，會接近O(n)。