鸡尾酒的定义和分类有哪些详细说明？
摘要：在上一篇漫画中，小灰介绍了冒泡排序的思路和几种变化： 漫画：什么是冒泡排序？ 那么，鸡尾酒排序又是何方神圣呢？我们这一期将会详细讲述。 让我们首先来回顾一下冒泡排序的思想： 冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着
在上一篇漫画中，小灰介绍了冒泡排序的思路和几种变化：
漫画：什么是冒泡排序？
那么，鸡尾酒排序又是何方神圣呢？我们这一期将会详细讲述。
让我们首先来回顾一下冒泡排序的思想：
冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。算法的每一轮从都是从左到右比较元素，进行单向的位置交换。
那么鸡尾酒排序做了怎样的优化呢？
鸡尾酒排序的元素比较和交换过程是双向的。
让我们来举一个栗子：
有8个数组成一个无序数列：2，3，4，5，6，7，8，1，希望从小到大排序。
如果按照冒泡排序的思想，排序的过程是什么样呢？
第一轮结果（8和1交换）
第二轮结果（7和1交换）
第三轮结果（6和1交换）
第四轮结果（5和1交换）
第五轮结果（4和1交换）
第六轮结果（3和1交换）
第七轮结果（2和1交换）
鸡尾酒排序是什么样子呢？让我们来看一看详细过程：
第一轮（和冒泡排序一样，8和1交换）
第二轮
此时开始不一样了，我们反过来从右往左比较和交换：
8已经处于有序区，我们忽略掉8，让1和7比较。元素1小于7，所以1和7交换位置：
接下来1和6比较，元素1小于6，所以1和6交换位置：
接下来1和5比较，元素1小于5，所以1和5交换位置：
接下来1和4交换，1和3交换，1和2交换，最终成为了下面的结果：
第三轮（虽然已经有序，但是流程并没有结束）
鸡尾酒排序的第三轮，需要重新从左向右比较和交换：
1和2比较，位置不变；2和3比较，位置不变；3和4比较，位置不变......6和7比较，位置不变。
没有元素位置交换，证明已经有序，排序结束。
这就是鸡尾酒排序的思路。排序过程就像钟摆一样，第一轮从左到右，第二轮从右到左，第三轮再从左到右......
1 /// <summary>
2 /// 鸡尾酒排序1
3 /// </summary>
4 /// <param name="list"></param>
5 /// <returns></returns>
6 private static List<int> CockTailSort1(List<int> array)
7 {
8 int tmp = 0;
9 for (int i = 0; i <= array.Count / 2-1; i++)
10 {
11 //有序标记，每一轮的初始是true
12 bool isSorted = true;
13 //从前到后的排序 (升序)
14 for (int j = i; j < array.Count - i; j++)
15 {
16 if (j + 1 < array.Count && array[j] > array[j + 1])
17 {
18 tmp = array[j];
19 array[j] = array[j + 1];
20 array[j + 1] = tmp;
21 //有元素交换，所以不是有序，标记变为false
22 isSorted = false;
23 }
24 }
25 if (isSorted)
26 {
27 break;
28 }
29 //从后到前的排序（降序）
30 for (int j = array.Count - i - 1; j >= i; j--)
31 {
32 if (j > 0 && array[j] < array[j - 1])
33 {
34 tmp = array[j];
35 array[j] = array[j - 1];
36 array[j - 1] = tmp;
37 //有元素交换，所以不是有序，标记变为false
38 isSorted = false;
39 }
40 }
41 if (isSorted)
42 {
43 break;
44 }
45 }
46 return array;
47 }
这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含两个小循环，第一个循环从左向右比较并交换元素，第二个循环从右向左比较并交换元素。
让我们来回顾一下冒牌排序针对有序区的优化思路：
原始的冒泡排序，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ......
要想优化，我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。
对于单向的冒泡排序，我们需要设置一个边界值，对于双向的鸡尾酒排序，我们需要设置两个边界值。请看代码：
1 /// <summary>
2 /// 鸡尾酒排序2
3 /// </summary>
4 /// <param name="list"></param>
5 /// <returns></returns>
6 private static List<int> CockTailSort2(List<int> array)
7 {
8 int tmp = 0;
9 //记录右侧最后一次交换的位置
10 int lastRightExchangeIndex = 0;
11 //记录左侧最后一次交换的位置
12 int lastLeftExchangeIndex = 0;
13 //无序数列的右边界，每次比较只需要比到这里为止
14 int rightSortBorder = array.Count - 1;
15 //无序数列的左边界，每次比较只需要比到这里为止
16 int leftSortBorder = 0;
17 for (int i = 0; i <= array.Count / 2 - 1; i++)
18 {
19 //有序标记，每一轮的初始是true
20 bool isSorted = true;
21 //奇数轮，从左向右比较和交换
22 for (int j = leftSortBorder; j < rightSortBorder; j++)
23 {
24 if (array[j] > array[j + 1])
25 {
26 tmp = array[j];
27 array[j] = array[j + 1];
28 array[j + 1] = tmp;
29 //有元素交换，所以不是有序，标记变为false
30 isSorted = false;
31 lastRightExchangeIndex = j;
32 }
33 }
34 rightSortBorder = lastRightExchangeIndex;
35 if (isSorted)
36 {
37 break;
38 }
39 //偶数轮，从右向左比较和交换
40 for (int j = rightSortBorder; j > leftSortBorder; j--)
41 {
42 if (array[j] < array[j - 1])
43 {
44 tmp = array[j];
45 array[j] = array[j - 1];
46 array[j - 1] = tmp;
47 //有元素交换，所以不是有序，标记变为false
48 isSorted = false;
49 lastLeftExchangeIndex = j;
50 }
51 }
52 leftSortBorder = lastLeftExchangeIndex;
53 if (isSorted)
54 {
55 break;
56 }
57 }
58 return array;
59 }
代码中使用了左右两个边界值，rightSortBorder 代表右边界，leftSortBorder代表左边界。
在比较和交换元素时，奇数轮从 leftSortBorder遍历到 rightSortBorder 位置，偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。
—————END—————