论坛 › Java语言交流 › 鸡尾酒排序算法

影-死神 发表于 2018-10-13 19:53:01

鸡尾酒排序算法

本帖最后由 影-死神 于 2018-10-13 19:58 编辑

一. 鸡尾酒排序与冒泡排序
      鸡尾酒排序是冒泡排序的优化。
      鸡尾酒排序与冒泡排序不同之处在于，冒泡排序是单向的，鸡尾酒排序是双向的。
      鸡尾酒排序是第一轮从左到右，第二轮从右到左，第三轮从左到右......

       算法的时间复杂度：
                同冒泡排序一样，是O(n**2)，如果排序前，数列中大部分都已经是有序的了，那么时间复杂度接近O(n)
      Java代码实现：

public class CockTailSort {
      public static void sort1(int[] array) {
                int temp;
               
                for (int i=0;i<array.length/2;i++) {
                        //有序标记
                        boolean isSorted = true;
                     
                        //奇数轮，从左往右
                        for (int j=i;j<array.length - i - 1;j++) {
                              if (array > array) {
                                        temp = array;
                                        array = array;
                                        array = temp;
                                       
                                        //有交换，标记为无序
                                        isSorted = false;
                              }
                        }
                        if (isSorted) {
                              break;
                        }
                     
                        //偶数轮，从右往左
                        //排序前重新标记
                        isSorted = true;
                     
                        for (int j=array.length - i - 1;j>i;j--) {
                              if (array < array) {
                                        temp = array;
                                        array = array;
                                        array = temp;
                                       
                                        isSorted = false;
                              }
                        }
                        if (isSorted) {
                              break;
                        }
                }
      }
      
      public static void main(String[] args) {
                int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
               
                sort1(list);
               
                for (int i=0;i<list.length;i++) {
                        System.out.print(list + " ");
                }
      }
}


      
二. 鸡尾酒排序算法的优化
      优化思路：同冒泡排序一样，某轮排序后，实际有序区可能大于理论有序区
      优化方法：增加有序区边界标识，具体与冒牌排序及其优化基本相同
      Java代码实现：
public class CockTailSort {
      public static void sort2(int[] array) {
                int temp;
                //左右最后交换元素的位置
                int leftIndex = 0, rightIndex = 0;
                //左边界
                int leftSortBorder = 0;
                //有边界
                int rightSortBorder = array.length - 1;
               
                for (int i=0;i<array.length/2;i++) {
                        //有序标记
                        boolean isSorted = true;
                     
                        //奇数轮，从左往右
                        for (int j=leftSortBorder;j<rightSortBorder;j++) {
                              if (array > array) {
                                        temp = array;
                                        array = array;
                                        array = temp;
                                       
                                        //有交换，标记为无序
                                        isSorted = false;
                                        //记录交换元素的位置
                                        rightIndex = j;
                              }
                        }
                        if (isSorted) {
                              break;
                        }
                        rightSortBorder = rightIndex;
                     
                        //偶数轮，从右往左
                        //排序前重新标记
                        isSorted = true;
                     
                        for (int j=rightSortBorder;j>leftSortBorder;j--) {
                              if (array < array) {
                                        temp = array;
                                        array = array;
                                        array = temp;
                                       
                                        isSorted = false;
                                        leftIndex = j;
                              }
                        }
                        if (isSorted) {
                              break;
                        }
                        leftSortBorder = leftIndex;
                }
      }
      
      public static void main(String[] args) {
                int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
               
                sort2(list);
               
                for (int i=0;i<list.length;i++) {
                        System.out.print(list + " ");
                }
      }
}



三.应用场景
在大部分元素已经有序的情况下，能够发挥出优势

查看完整版本: 鸡尾酒排序算法