一.鸡尾酒排序概念
鸡尾酒排序，是冒泡排序算法的一种升级。冒泡排序的每个元素都可以像气泡一样，根据自身大小，一点点的向着数组的某侧移动。算法每一轮都是从左到右来比较元素，进行单向的位置交换的。而鸡尾酒排序是在此基础上元素比较和交换过程变成了双向的。固鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。
鸡尾酒排序最糟或是平均所花费的次数都是O(n²)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。
二. 逻辑推演
问题分析：
现有一个数组，里面的数据为： [2,3,4,5,6,7,8,1]，我们以此数据来分析：
冒泡排序过程如下：
结果分析：
元素 2、3、4、5、6、7、8已经是有序的了，只需要将元素1的放到正确的位置就可以了，却还是进行了7轮排序，这也太不方便了。要是能直接将1的位置进行调整，数列就有序了。鸡尾酒排序正是要解决这个问题的。
优化思路：
鸡尾酒详细过程：
第一轮（和冒泡排序一样，8和1交换）
第二轮：此时开始不一样了，我们反过来从右往左比较进行交换。
第三轮:虽然实际上已经有序，但是流程并没有结束。
在鸡尾酒排序的第三轮，需要重新从左向右比较进行交换。
1和2比较，位置不变；2和3比较，位置不变；3和4比较，位置不变...7和8比较位置不变。没有元素进行交换，证明当前有序，排序结束。
小结：
本来需要7轮的排序场景，用3轮就解决了，鸡尾酒排序就是这样巧妙的算法。
而鸡尾酒排序的思路，排序过程就像钟摆一样，第一轮从左往右比较，第二轮从右往左比较，第三轮再从左往右比较...
三.鸡尾酒排序算法
代码：
public static void sort(int[] array) {
//循环计数
int count = 0;
//数据交换临时变量
int tmp = 0;
for (int i = 0; i < array.length / 2; i++) {
System.out.println("第" + (++count) + "次循环");
//每轮的初始值都是true，有序标记：true代表有序
boolean isSorted = true;
//奇数轮，从左向右比较和交换
for (int j = i; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
//发生交换，不是有序，标记改成false
isSorted = false;
}
}
//是否有序
if (isSorted) {
break;
}
//在偶数轮之前，将isSorted重新标记为true
isSorted = true;
System.out.println("第" + (++count) + "次循环");
//偶数轮，方向从右向左比较和交换
for (int j = array.length - i - 1; j > i; j--) {
if (array[j] < array[j - 1]) {
tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
isSorted = false;
}
}
//是否有序
if (isSorted) {
break;
}
}
}
结果输出:
第1次循环
第2次循环
第3次循环
[1, 2, 3, 4, 5, 6, 7, 8]
总结：
这段代码是鸡尾酒排序的原始实现。代码外部的大循环控制所有排序回合，大循环内部包含两个小循环，第1个小循环从左往右比较并交换元素，第2个小循环从右往左比较并交换元素。
鸡尾酒的优势是，在大部分元素已经有序的情况下，减少排序的回合数；而缺点也很明显，就是代码量几乎翻了一倍。
