排序算法之鸡尾酒排序

不念不忘少年蓝@ 2023-02-20 02:56 1阅读 0赞

双向冒泡排序也被称为鸡尾酒排序、鸡尾酒调酒器排序、摇床排序、涟漪排序、洗牌排序、班车排序等。（再多再华丽丽的名字也难以弥补它的低效）

>  *  鸡尾酒排序，是冒泡排序的改良
>  *  大部分元素都有序的时候，可以用鸡尾酒排序、地精排序

# 冒泡排序 #

冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。

## 原理 ##

*  比较相邻的元素。如果第一个比第二个大，就交换他们两个
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

一般情况下，可以通过下面的动画理解冒泡排序。

现在我们来看一组特殊数据如果使用冒泡排序会怎么样。

将无序数列：2，3，4，5，6，7，8，1，使用冒泡排序使其从小到大排序。

进行逐步分析：

第一轮操作（ 8 和 1 交换 ）  
![在这里插入图片描述][20200622174918129.gif]  
第二轮操作（ 7 和 1 交换 ）  
![在这里插入图片描述][20200622175022772.gif]  
第三轮操作（ 6 和 1 交换 ）  
![在这里插入图片描述][20200622175107665.gif]  
第四轮操作（ 5 和 1 交换 ）  
![在这里插入图片描述][20200622175320603.gif]  
第五轮操作（ 4 和 1 交换 ）  
![在这里插入图片描述][20200622175355846.gif]  
第六轮操作（ 3 和 1 交换 ）  
![在这里插入图片描述][20200622175426547.gif]  
第七轮操作（ 2 和 1 交换 ）  
![在这里插入图片描述][20200622175550225.gif]  
仔细观察上面的这组无序数列，实际上只有 1 的位置不在该在的位置，而 2 ，3 ，4 ，5 ，6 ，7 ，8 都已经有序了，结果使用冒泡排序，需要 折腾 7 次才能将 1 归位。

兔子示例图等待补充：

\{6, 1, 2, 3, 4, 5\}

从上面可以看出，冒泡排序有意i给很大的问题：它的运行时间依赖于数组的初始排序。大的数(兔子)上升得很快，而小的数(乌龟)下降的很慢。

冒泡排序中，尾部小数值称为乌龟，头部大数值叫做兔子。

# 鸡尾酒排序 #

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。

![在这里插入图片描述][20200622175755133.gif]  
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

排序过程：

*  先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端
 *  再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端
 *  以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束

第一轮操作（ 8 和 1 交换 ）  
![在这里插入图片描述][2020062217592434.gif]  
第二轮操作 ( 从序列右边开始遍历 ）  
![在这里插入图片描述][20200622180040689.gif]  
第三轮操作 ( 从左向右比较和交换 )  
![在这里插入图片描述][20200622180121718.gif]  
在这一轮操作中，没有元素位置交换，证明已经有序，排序结束。对比 冒泡排序 ，鸡尾酒排序只需要 3 轮操作就可以完成排序。

# 代码实现 #

## java ##

private static void BubbleSort(int[] arr){
        
            int left = 0, right = arr.length - 1;  // 无序区间索引
            while (left < right){
        
                for (int i = left; i < right; i++){
         //第一次比较时： i = 数组的最后一个元素的索引时跳出循环。 因为最后一个元素就不需要比较
                    if (arr[i] > arr[i+1]){
        
                        swap(arr, i, i+1);
                    }
                }
                right--;
            }
        }
    
    
    
        private static void CocktailSort(int[] arr){
        
            int left = 0, right = arr.length - 1;  // 无序区间索引
            while (left < right){
        
                // 从左到右边：最大的放在右边
                for (int i = left; i < right; i++){
        
                    if (arr[i] > arr[i+1]){
        
                        swap(arr, i, i+1);
                    }
                }
                right--;
            //    System.out.println(Arrays.toString(arr));
                // 从右到左：最小的放到右边
                for (int i = right; i > left; i--){
        
                    if (arr[i] < arr[i-1]){
        
                        swap(arr, i, i-1);
                    }
                }
             //   System.out.println(Arrays.toString(arr));
                left++;
            }
        }
    
    
        private static void swap(int[] arr, int i , int j){
        
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
    
    
    
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        77, 66, 33, 3,2,3,2,5,333,45566,2345678,78,990,12,432,56};
            CocktailSort(arr);
            System.out.println(Arrays.toString(arr));
        }

优化：一旦没有任何元素发生交换，就表示数据已经有序了

private static void BubbleSort(int[] arr){
        
            int left = 0, right = arr.length - 1;  // 无序区间索引
            boolean swap = false;
            while (left < right){
        
                swap = false;
                for (int i = left; i < right; i++){
         //第一次比较时： i = 数组的最后一个元素的索引时跳出循环。 因为最后一个元素就不需要比较
                    if (arr[i] > arr[i+1]){
        
                        swap(arr, i, i+1);
                        swap = true;
                    }
                }
    
                //当前这一轮比较中没有发生交换：表示有序
                if (swap == false){
        
                    break;
                }
    
                right--;
            }
        }
    
    
    
        private static void CocktailSort(int[] arr){
        
            int left = 0, right = arr.length - 1;  // 无序区间索引
            boolean swap = false;
            while (left < right){
        
                swap = false;
                // 从左到右边：最大的放在右边
                for (int i = left; i < right; i++){
        
                    if (arr[i] > arr[i+1]){
        
                        swap(arr, i, i+1);
                        swap = true;
                    }
                }
                right--;
            //    System.out.println(Arrays.toString(arr));
                // 从右到左：最小的放到右边
                for (int i = right; i > left; i--){
        
                    if (arr[i] < arr[i-1]){
        
                        swap(arr, i, i-1);
                        swap = true;
                    }
                }
             //   System.out.println(Arrays.toString(arr));
    
                if (swap == false){
        
                    break;
                }
                left++;
            }
        }
    
    
        private static void swap(int[] arr, int i , int j){
        
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
    
        public static int[] generateRandomArray(int length, int rangeL, int rangeR){
        
            if (length <0  || rangeR <= rangeL) {
        
                return null;
            };
    
            return  new Random().ints(rangeL, rangeR).limit(length).toArray();
        }
    
        public static void main(String[] args) {
        
          //  int[] arr = new int[]{77, 66, 33, 3,2,3,2,5,333,45566,2345678,78,990,12,432,56};
            int [] arr =  generateRandomArray(1000000, -10000, 10000);
            long start = System.currentTimeMillis(); // 记录起始时间
            CocktailSort(arr);
            long end = System.currentTimeMillis();       // 记录结束时间
            System.out.println(end-start);
            System.out.println(Arrays.toString(arr));
        }

## golang ##

package main
    
    import (
    	"fmt"
    )
    
    func bobbleSort(arr [] int)[]int{
        
    	length := len(arr)
    	if length <= 1 {
        
    		return arr
    	}else{
        
    		for i := 0; i < length ; i++ {
        
    			exchange := false
    			left,  right :=  0,  length - 1 - i;// 无序区间索引
    			for j := left; j < right ; j++{
        
    				if arr[j] > arr[j + 1] {
        
    					arr[j], arr[j + 1] = arr[j + 1], arr[j];
    					exchange = true
    				}
    			}
    			if !exchange {
        
    				break
    			}
    		}
    
    		return arr;
    	}
    }
    
    
    func cocktailSort(arr [] int)[]int{
        
    	length := len(arr)
    	 if length <= 1 {
        
    		return arr
    	}else{
        
    		 left,  right :=  0,  length - 1;// 无序区间索引
    		 for left < right {
        
    			 exchange := false
    			 for j := left; j < right ; j++{
        
    				 if arr[j] > arr[j + 1] {
        
    					 arr[j], arr[j + 1] = arr[j + 1], arr[j]
    					 exchange = true
    				 }
    			 }
    			 right--
    
    			 for j := right; j > left ; j--{
        
    				 if arr[j] < arr[j - 1] {
        
    					 arr[j], arr[j - 1] = arr[j - 1], arr[j]
    					 exchange = true
    				 }
    			 }
    			 left++
    
    			 if !exchange {
        
    				 break
    			 }
    
    		 }
    
    		 return arr;
    	}
    }
    
    
    
    func main() {
        
    	arr:=[]int {
        1,9,2,8,3,7,4,6,5,10, -1}
    	fmt.Println(cocktailSort(arr))
    	fmt.Println(arr)
    }

[20200622174918129.gif]: https://img-blog.csdnimg.cn/20200622174918129.gif
[20200622175022772.gif]: https://img-blog.csdnimg.cn/20200622175022772.gif
[20200622175107665.gif]: https://img-blog.csdnimg.cn/20200622175107665.gif
[20200622175320603.gif]: https://img-blog.csdnimg.cn/20200622175320603.gif
[20200622175355846.gif]: https://img-blog.csdnimg.cn/20200622175355846.gif
[20200622175426547.gif]: https://img-blog.csdnimg.cn/20200622175426547.gif
[20200622175550225.gif]: https://img-blog.csdnimg.cn/20200622175550225.gif
[20200622175755133.gif]: https://img-blog.csdnimg.cn/20200622175755133.gif
[2020062217592434.gif]: https://img-blog.csdnimg.cn/2020062217592434.gif
[20200622180040689.gif]: https://img-blog.csdnimg.cn/20200622180040689.gif
[20200622180121718.gif]: https://img-blog.csdnimg.cn/20200622180121718.gif