複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/雞尾酒排序/7515196
複製
複製成功

雞尾酒排序

鎖定
雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時排序, 是冒泡排序的一種變形。該算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。
中文名
雞尾酒排序
外文名
Cocktail ordering
別    名
攪拌排序
簡    介
定向冒泡排序
説    明
冒泡排序的一種簡單優化

目錄

  1. 1 原理
  2. 2 代碼
  3. ▪ Java
  1. ▪ Pascal
  2. ▪ C 語言
  3. ▪ python
  4. 3 與冒泡的區別
  1. 4 複雜度

雞尾酒排序原理

使用雞尾酒排序為一列數字進行排序的過程可以通過形象的展示出來：
數組中的數字本是無規律的排放，先找到最小的數字，把他放到第一位，然後找到最大的數字放到最後一位。然後再找到第二小的數字放到第二位，再找到第二大的數字放到倒數第二位。以此類推，直到完成排序。

雞尾酒排序代碼

雞尾酒排序Java

public static int[] cocktailSort(int[] src)
{
        int len = src.length;
    //將最小值排到隊尾
    for(int i = 0 ; i < len/2 ; i++)
    {
        for(int j = i ; j < len-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 = len-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

type
arra=
array[1..10000]of integer;
procedure 
sort(b:arra);
var i,
bottom,top,t:integer;
f:
boolean;
begin
bottom:=1;
top:=n;
f:=true;

while(f=true) do
begin
f:=false;
for i:=bottom to top-1 do
if 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 do
if 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(int(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)。