转载：算法：鸡尾酒排序CocktailSort
转载：算法：鸡尾酒排序CocktailSort
原文链接：https://zhuanlan.zhihu.com/p/104105622
动画 | 什么是鸡尾酒排序？
公众号『算法无遗策』
已关注
鸡尾酒排序其实就是冒泡排序的变形，它的时间复杂度和冒泡排序一样，都是O(n^2)，比快速排序要慢不少。
鸡尾酒排序的思想有点像摆钟一样，从左到右，又从右到左。而冒泡排序只是单向执行。
鸡尾酒排序也是交换排序，假设做一个升序排序，先从左到右，交换一趟把最大的数放置右边，然后从右到左，把最小的数放置左边。
视频动画
算法动画视频 地址 https://www.bilibili.com/video/av78236322/
[高清 720P] 鸡尾酒排序和它的优化_P1_鸡尾酒排序 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class CocktailSort {
public static void cocktailSort(int[] array){
for(int i = 0; i < array.length / 2; i++){//for(1)
for(int j = i; j < array.length - i - 1; j++){//for(2)
if(array[j] > array[j + 1]){
swap(array, j, j + 1);
System.out.println("从左到右发生交换：" + Arrays.toString(array));
}
}//end of for(2)
for(int j = array.length - i - 2; j > i; j--){//for(3)
if(array[j - 1] > array[j]){
swap(array, j - 1, j);
System.out.println("从右到左发生交换：" + Arrays.toString(array));
}
}//end of for()3
}//end of for(1)
}//end of method cocktailSort
public static void swap(int[] array, int i, int j){
if(i == j){return;}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static void main(String[] args) {
int[] array = {5,1,9,3,7,4,8,6,2};
System.out.println("初始状态：" + Arrays.toString(array));
cocktailSort(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态 [5, 1, 9, 3, 7, 4, 8, 6, 2]从左到右发生交换 [1, 5, 9, 3, 7, 4, 8, 6, 2]从左到右发生交换 [1, 5, 3, 9, 7, 4, 8, 6, 2]从左到右发生交换 [1, 5, 3, 7, 9, 4, 8, 6, 2]从左到右发生交换 [1, 5, 3, 7, 4, 9, 8, 6, 2]从左到右发生交换 [1, 5, 3, 7, 4, 8, 9, 6, 2]从左到右发生交换 [1, 5, 3, 7, 4, 8, 6, 9, 2]从左到右发生交换 [1, 5, 3, 7, 4, 8, 6, 2, 9]从右到左发生交换 [1, 5, 3, 7, 4, 8, 2, 6, 9]从右到左发生交换 [1, 5, 3, 7, 4, 2, 8, 6, 9]从右到左发生交换 [1, 5, 3, 7, 2, 4, 8, 6, 9]从右到左发生交换 [1, 5, 3, 2, 7, 4, 8, 6, 9]从右到左发生交换 [1, 5, 2, 3, 7, 4, 8, 6, 9]从右到左发生交换 [1, 2, 5, 3, 7, 4, 8, 6, 9]从左到右发生交换 [1, 2, 3, 5, 7, 4, 8, 6, 9]从左到右发生交换 [1, 2, 3, 5, 4, 7, 8, 6, 9]从左到右发生交换 [1, 2, 3, 5, 4, 7, 6, 8, 9]从右到左发生交换 [1, 2, 3, 5, 4, 6, 7, 8, 9]从右到左发生交换 [1, 2, 3, 4, 5, 6, 7, 8, 9]
优化 减少不必要的交换
看了前面冒泡排序和快速排序，我相信优化是一项学习的重点，以后面试中可以把这项说说来，展示出你的实力。
这次我们就优化不必要的交换次数，come on！
我们通过移除swap函数的调用，从而让程序运行的更快一点。每次进行符合条件判断时，不做交换，让最大或者最小的数据做一个标记，待全部比较完之后，才进行做交换。
视频动画
算法动画视频 地址 https://www.bilibili.com/video/av78236322?p=2
[高清 720P] 鸡尾酒排序和它的优化_P2_鸡尾酒排序不必要的交换 [最优化的质量和大小].flv
Code
package cn.study.sort;
import java.util.Arrays;
public class CocktailSort {
public static void cocktailSort(int[] array){
for(int i = 0; i < array.length / 2; i++){//for(1)
for(int j = i; j < array.length - i - 1; j++){//for(2)
if(array[j] > array[j + 1]){
swap(array, j, j + 1);
System.out.println("从左到右发生交换：" + Arrays.toString(array));
}
}//end of for(2)
for(int j = array.length - i - 2; j > i; j--){//for(3)
if(array[j - 1] > array[j]){
swap(array, j - 1, j);
System.out.println("从右到左发生交换：" + Arrays.toString(array));
}
}//end of for()3
}//end of for(1)
}//end of method cocktailSort
//每次进行符合条件判断时，不做交换，让最大或者最小的数据做一个标记，待全部比较完之后，才进行做交换。
public static void cocktailSortTwo(int[] array){
int low, high;
for(int i = 0; i < array.length / 2; i++){
low = i;
high = array.length - i - 1;
for(int j = i; j < array.length - i - 1; j++){
if(array[low] < array[j + 1]){
low = j + 1;
}
}
swap(array, low, high);
System.out.println("从左到右发生交换：" + Arrays.toString(array));
for(int j = array.length - i - 1; j > i; j--){
if(array[j - 1] < array[high]){
high = j - 1;
}
}
swap(array, i, high);
System.out.println("从右到左发生交换：" + Arrays.toString(array));
}
}//end of method cocktailSortTwo
public static void swap(int[] array, int i, int j){
if(i == j){return;}
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
public static void main(String[] args) {
int[] array = {5,1,9,3,7,4,8,6,2};
System.out.println("初始状态：" + Arrays.toString(array));
// cocktailSort(array);
cocktailSortTwo(array);
System.out.println(Arrays.toString(array));
}
}
Result
初始状态 [5, 1, 9, 3, 7, 4, 8, 6, 2]从左到右发生交换 [5, 1, 2, 3, 7, 4, 8, 6, 9]从右到左发生交换 [1, 5, 2, 3, 7, 4, 8, 6, 9]从左到右发生交换 [1, 5, 2, 3, 7, 4, 6, 8, 9]从右到左发生交换 [1, 2, 5, 3, 7, 4, 6, 8, 9]从左到右发生交换 [1, 2, 5, 3, 6, 4, 7, 8, 9]从右到左发生交换 [1, 2, 3, 5, 6, 4, 7, 8, 9]从左到右发生交换 [1, 2, 3, 5, 4, 6, 7, 8, 9]从右到左发生交换 [1, 2, 3, 4, 5, 6, 7, 8, 9]
喜欢本文的朋友，微信搜索「算法无遗策」公众号，收看更多精彩的算法动画文章