转载:算法:鸡尾酒排序CocktailSort

tech2024-11-24  14

转载:算法:鸡尾酒排序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]

 

喜欢本文的朋友,微信搜索「算法无遗策」公众号,收看更多精彩的算法动画文章

最新回复(0)