鸡尾酒排序算法

影-死神

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

       算法的时间复杂度：
                同冒泡排序一样，是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[j] > array[j+1]) {
                                        temp = array[j];
                                        array[j] = array[j+1];
                                        array[j+1] = temp;
                                       
                                        //有交换，标记为无序
                                        isSorted = false;
                                }
                        }
                        if (isSorted) {
                                break;
                        }
                       
                        //偶数轮，从右往左
                        //排序前重新标记
                        isSorted = true;
                       
                        for (int j=array.length - i - 1;j>i;j--) {
                                if (array[j] < array[j-1]) {
                                        temp = array[j];
                                        array[j] = array[j-1];
                                        array[j-1] = 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[j] > array[j+1]) {
                                        temp = array[j];
                                        array[j] = array[j+1];
                                        array[j+1] = temp;
                                       
                                        //有交换，标记为无序
                                        isSorted = false;
                                        //记录交换元素的位置
                                        rightIndex = j;
                                }
                        }
                        if (isSorted) {
                                break;
                        }
                        rightSortBorder = rightIndex;
                       
                        //偶数轮，从右往左
                        //排序前重新标记
                        isSorted = true;
                       
                        for (int j=rightSortBorder;j>leftSortBorder;j--) {
                                if (array[j] < array[j-1]) {
                                        temp = array[j];
                                        array[j] = array[j-1];
                                        array[j-1] = 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 + " ");
                }
        }
}

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