鸡尾酒排序

虚拟码

与冒泡排序不同的地方

鸡尾酒排序

也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

虚拟码

虚拟码是以 C 语言撰写，目的在将一个序列由小到大进行排序：

function cocktail_sort(list, list_length) // the first element of list has index 0

bottom = 0;

top = list_length - 1;

swapped = true;

while(swapped == true) // 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;

}

}

// 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;

for(i = top; i > bottom; i = i - 1)

{

if(list[i] < list[i-1])

{

swap(list[i], list[i-1]);

swapped = true;

}

}

// 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;

}

}

与冒泡排序不同的地方

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。

以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问两次（升序降序各一次 ）次序列就可以完成排序，但如果使用冒泡排序则需要四次。

复杂度

鸡尾酒排序最糟或是平均所花费的次数都是O(n2)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。