鸡尾酒排序(Cocktail Sort)算法又称为摇晃排序(Shaker Sort)算法、双向冒泡排序(Bidirectional Bubble Sort)算法,顾名思义,它是冒泡排序(Bubble Sort)算法的变体,将原本单向走访的冒泡排序改为双向,用以解决使用冒泡排序法时,串行中未排序的一端其实已经大致排序好,却又不能尽快把它完成的情形。
鸡尾酒排序法(Cocktail Sort)
鸡尾酒排序法的概念
鸡尾酒排序法是基于冒泡排序法的算法,如果您还不了解冒泡排序法的话,请先参考这篇文章:
鸡尾酒排序法会从串行的两端开始向个别的另一端进行走访,在每次迭代时,两端的走访循环都会拿当前索引位置的元素与其下一个索引位置的元素进行比较,从前端开始的走访比较策略是:如果下一个元素比较小,就进行交换;如果下一个元素没有比较小,就不进行交换;而从尾端开始的走访比较策略是:如果下一个元素比较大,就进行交换;如果下一个元素没有比较大,就不进行交换。当串行被各端走访完一次之后,串行的最尾端元素即为最大的元素,最前端的元素即为最小的元素。再来从两端重新走访一次串行,用同样的方法将第二大的元素值挤进串行的从尾端开始倒数的第二个位置,将第二小的元素值挤进串行的从前端开始数的第二个位置。从两端重新走访一次串行,用同样的方法将第三大的元素值挤进串行的从尾端开始倒数的第三个位置,将第三小的元素值挤进串行的从前端开始数的第三个位置。依此类推,直到所有元素都被挤到尾端或前端,或是在各端走访串行的过程中,如果发现都没有元素被交换的话,表示此时的串行已经完成排序了。
鸡尾酒排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
一开始,从数组最前方开始,逐次两两比较元素的大小,将两个元素中较大的元素排在后面,即可逐渐将最大的元素从数组前方挤到数组后方。这部份和冒泡排序法是一模一样的,过程如下:
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
81 > 30
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└┬┘
81 > 38
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└┬┘
81 > 9
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└┬┘
81 > 2
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└┬┘
81 > 47
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└┬┘
81 > 61
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└┬┘
81 > 32
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└─┘
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└┬┘
81 > 79
●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└─┘
● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
再来就是鸡尾酒排序法的创新部份了。从数组尚未排序好的尾端开始,逐次两两比较元素的大小,将两个元素中较大的元素排在后面,即可逐渐将最小的元素从数组后方挤到数组前方。过程如下:
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└┬┘
32 < 79
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└┬┘
61 > 32
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 32 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 32 61 79 81
└┬┘
47 > 32
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 32 47 61 79 81
└┬┘
2 < 32
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 32 47 61 79 81
└┬┘
9 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 2 9 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 2 9 32 47 61 79 81
└┬┘
38 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 2 38 9 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 2 38 9 32 47 61 79 81
└┬┘
30 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 2 30 38 9 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 2 30 38 9 32 47 61 79 81
└┬┘
69 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 30 38 9 32 47 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 30 38 9 32 47 61 79 81
接下来就是一直不断地在未排序范围内做「把最大值从前端挤到后端」和「把最小值从后端挤到前端」的动作。完整过程如下:
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
81 > 30
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 81 38 9 2 47 61 32 79
└┬┘
81 > 38
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 81 9 2 47 61 32 79
└┬┘
81 > 9
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 81 2 47 61 32 79
└┬┘
81 > 2
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 81 47 61 32 79
└┬┘
81 > 47
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 81 61 32 79
└┬┘
81 > 61
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 81 32 79
└┬┘
81 > 32
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└─┘
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 81 79
└┬┘
81 > 79
● ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└┬┘
32 < 79
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 61 32 79 81
└┬┘
61 > 32
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 32 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 47 32 61 79 81
└┬┘
47 > 32
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 32 47 61 79 81
└┬┘
2 < 32
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 9 2 32 47 61 79 81
└┬┘
9 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 2 9 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 38 2 9 32 47 61 79 81
└┬┘
38 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 2 38 9 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 30 2 38 9 32 47 61 79 81
└┬┘
30 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 2 30 38 9 32 47 61 79 81
└─┘
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 2 30 38 9 32 47 61 79 81
└┬┘
69 > 2
● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 30 38 9 32 47 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 30 38 9 32 47 61 79 81
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 69 30 38 9 32 47 61 79 81
└┬┘
69 > 30
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 69 38 9 32 47 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 69 38 9 32 47 61 79 81
└┬┘
69 > 38
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 69 9 32 47 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 69 9 32 47 61 79 81
└┬┘
69 > 9
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 69 32 47 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 69 32 47 61 79 81
└┬┘
69 > 32
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 69 47 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 69 47 61 79 81
└┬┘
69 > 47
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 69 61 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 69 61 79 81
└┬┘
69 > 61
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└─┘
○ ● ● ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└┬┘
69 < 79
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└┬┘
61 < 69
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└┬┘
47 < 61
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└┬┘
32 < 47
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└┬┘
9 < 32
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 38 9 32 47 61 69 79 81
└┬┘
38 > 9
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 9 38 32 47 61 69 79 81
└─┘
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 30 9 38 32 47 61 69 79 81
└┬┘
30 > 9
○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└─┘
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└┬┘
30 < 38
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 32 47 61 69 79 81
└┬┘
38 > 32
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└─┘
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
38 < 47
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
47 < 61
○ ○ ● ● ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
61 < 69
○ ○ ● ● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
○ ○ ● ● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
47 < 61
○ ○ ● ● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
38 < 47
○ ○ ● ● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
32 < 38
○ ○ ● ● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
└┬┘
30 < 32
○ ○ ● ● ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
※
鸡尾酒排序法的程序实作
鸡尾酒排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n^2)}}# | 排序已经反向排序过的串行。 |
| 最佳时间复杂度 | #{{O(n)}}# | 排序已经正向排序过的串行。 |
| 平均时间复杂度 | #{{O(n^2)}}# | |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 是 |

