冒泡排序升级版-鸡尾酒排序

谁践踏了优雅 2022-05-15 12:06 204阅读 0赞

## 简介 ##

鸡尾酒排序等于冒泡排序的轻微变形，不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。

## 分析 ##

鸡尾酒排序算法的运作如下：

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

## 视觉图效果 ##

![这里写图片描述][70]

## 代码实现 ##

public int[] cocktail(int[] nums){ 
            if (null == nums || nums.length == 0 || nums.length == 1) { 
                System.out.println("0 0");
                return nums;
            } 
            int left = 0, right = nums.length - 1;
            int count=0, swapCount=0;
            while(left < right){ 
                //先从右到左，把最大的找出来
                for (int i = left; i < right; i++) { 
                    count ++;
                    if(nums[i] > nums[i+1]){ 
                        swapCount ++;
                        swap(nums, i, i+1);
                    }
                }
                right --;
                // 从左到右，将最小的放到左边
                for (int i = right; i > left; i--) { 
                    count ++;
                    if(nums[i-1] > nums[i]){ 
                        swapCount ++;
                        swap(nums, i-1, i);
                    }
                }
                left ++;
            }
            System.out.println(count + " " + swapCount);
            return nums;
        }
    
        private void swap(int[] nums, int i, int j) { 
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }

## 测试 ##

### 测试用例 ###

*  数组长度1
 *  数组长度10
 *  数组长度100
 *  数组长度1000
 *  数组长度10000
 *  数组长度100000
 *  数组长度1000000

期望：数组长度越大，耗时越长，且呈现几何倍数递增

### 测试条件 ###

### 硬件环境 ###

<table> 
 <thead> 
  <tr> 
   <th>配置项</th> 
   <th>配置值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>computer</td> 
   <td>MacBook Pro (Retina, 13-inch, Early 2015)</td> 
  </tr> 
  <tr> 
   <td>graphics</td> 
   <td>Intel Iris Graphics 6100 1536 MB</td> 
  </tr> 
  <tr> 
   <td>member</td> 
   <td>16 GB 1867 MHz DDR3</td> 
  </tr> 
  <tr> 
   <td>processor</td> 
   <td>3.1 GHz Dual-Core Intel Core i7</td> 
  </tr> 
 </tbody> 
</table>

### 测试代码 ###

public class AppTest2{ 
       App app = new App();
       int[] one = new int[1];
       int[] two = new int[10];
       int[] three = new int[100];
       int[] four = new int[1000];
       int[] five = new int[10000];
       int[] six = new int[100000];
    
       @Before
       public void before(){ 
          one = generateRandomNumber(1);
          two = generateRandomNumber(10);
          three = generateRandomNumber(100);
          four = generateRandomNumber(1000);
          five = generateRandomNumber(10000);
          six = generateRandomNumber(100000);
       }
       @Test
       public void testDoItOne(){ 
          System.out.print(1 + " ");
          app.cocktail(one);
          System.out.println("----------------");
       }    
    
       @Test
       public void testDoItTwo(){ 
          System.out.print(3 + " ");
          app.cocktail(two);
          System.out.println("----------------");
       }
       @Test
       public void testDoItThree(){ 
          System.out.print(3 + " ");
          app.cocktail(three);
          System.out.println("----------------");
       }
       @Test
       public void testDoItFour(){ 
          System.out.print(4 + " ");
          app.cocktail(four);
          System.out.println("----------------");
       }
       @Test
       public void testDoItFive(){ 
          System.out.print(5 + " ");
          app.cocktail(five);
          System.out.println("----------------");
       }
       @Test
       public void testDoItSix(){ 
          System.out.print(6 + " ");
          app.cocktail(six);
          System.out.println("----------------");
       } 
    
       // @Test
       public void testDoItSeven(){ 
          System.out.print(7 + " ");
          int[] seven = generateRandomNumber(1000000);
          long start = System.currentTimeMillis();
          app.cocktail(seven);
          long end = System.currentTimeMillis();
          System.out.println("----------------");
          System.out.println("耗时："+ (end - start));
       }
    
       public static int[] generateRandomNumber(int length){ 
          int[] randomArray = new int[length];
          Random random = new Random();
          for(int i=0;i<length;i++){ 
              randomArray[i] = random.nextInt(length);
          }
          return randomArray;
      }
    }

## 测试结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4MDY3ODc_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4MDY3ODc_size_16_color_FFFFFF_t_70_pic_center 1]

## 总结 ##

T(1) = 长度1的数组排序耗时  
毫秒级：T(1), T(10), T(100), T(1000) 10毫秒  
秒级：T(10000) 140毫秒  
十秒级:T(100000) 10秒  
千秒级:T(1000000) 1000秒

从上到下递增倍数是：10倍， 7倍， 70倍

分水岭是数组长度10000.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4MDY3ODc_size_16_color_FFFFFF_t_70_pic_center 2]  
整个排序期间，并未创建多余的数组占用内存（除了几个用户辅助判断查找次数，交换次数的变量）  
时间复杂度：介于O(n)~O(n\*n)之间  
空间复杂度：O(1)

我测试了十多次，总体上看，鸡尾酒冒泡排序性能略优于单向冒泡排序

[70]: /images/20220515/1fb0e38824424a379ab45145ee7ad69d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4MDY3ODc_size_16_color_FFFFFF_t_70_pic_center]: /images/20220515/b91c40ea36c5432e818253b5f68cde70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4MDY3ODc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220515/6702edbdd7f943cd859fedb02eb1138a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4MDY3ODc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220515/6511d5d15d264a1c9a24bc32c32c7b82.png