:-: 14.2 鸡尾酒排序 * * * * * **基本概念：** 它也就是定向冒泡排序，也叫鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。 它可以得到比冒泡排序稍微好一点的性能，原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目。以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在随机数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲，但是对于初学者理解特别容易，所以教材一般会将冒泡排序当作介绍算法的概念. **算法的运作：** 1、排除头部已经经过检查排好序的元素后的头部开始比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对（未经过检测排好序的数列）。这步做完后，最后的元素会是最大（小）的数。 3、排除尾部已经经过检查排好序的元素后的尾部开始比较相邻的元素。如果第一个比第二个小（大），就交换他们两个。 4、对每一对相邻元素作同样的工作，从结尾的最后一对到开始第一对（未经过检测排好序的数列）。这步做完后，最后的元素会是最小（大）的数。 3、针对除了开头和最后已经排好序的元素的元素重复以上的步骤，。 4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。 **图片示例：** :-:  **代码实现：** 第一种方式：从小到大排序，正序寻找其中最大的元素排在尾部，倒序寻找其中最小的元素排在头部。 ~~~ public void cocktailSort(int nums[]) { int sign = 0; int j, left = 0, right = nums.length - 1; while (left < right) { for (j = left; j < right; j++) { if (nums[j] > nums[j + 1]) { sign = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = sign; } } right--; for (j = right; j > left; j--) { if (nums[j - 1] > nums[j]) { sign = nums[j]; nums[j] = nums[j - 1]; nums[j - 1] = sign; } } left++; } } ~~~ 第二种方式：从小到大排序，我们分析一下上面排序算法，我们会发现，如果我们输入[5,6,7,8],它还是会经过多次循环来排序，但是我们的原数组这已经顺序已经排好了呀。我们怎么避免这种情况呢？我们可以做个标记，来判断当前的数组有无需要交换的元素，这样最优的情况下时间复杂度会降到O(n)。 ~~~ public void cocktailSort(int nums[]) { int sign = 0; int j, left = 0, right = nums.length - 1; boolean cocktail = false; do { cocktail = false; for (j = left; j < right; j++) { if (nums[j] > nums[j + 1]) { sign = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = sign; cocktail = true; } } right--; for (j = right; j > left; j--) { if (nums[j - 1] > nums[j]) { sign = nums[j]; nums[j] = nums[j - 1]; nums[j - 1] = sign; } } left++; } while (left < right && cocktail); } ~~~ **复杂度分析：** 时间复杂度：平均：O(n^2)、最坏：O(n^2)、最优：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [维基百科——鸡尾酒排序](https://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F) [经典算法排序（示例图片来源）](https://zhuanlan.zhihu.com/p/29334450)