鸡尾酒排序

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(n^2)
最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 稳定

原理

       鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能。

步骤

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始到结尾。这步做完后，最后的元素会是最大的数。并将结尾指针移动到最大数的前一位。
3. 从结尾开始向前比较，如果后一个比前一个小，就把它们两个调换位置。
4. 对每一对相邻元素作同样的工作，从结尾到开头。这步做完后，开头的元素会是最小的数。并加开头指针移动到最小数的后一位。
5. 重复以上的步骤，直到没有任何一对数字需要比较。

代码实现

public class CocktailSort {
    void sort(Integer[] array) {

        int left = 0;
        int right = array.length - 1;

        while (left < right){
            // 前半轮,将最大元素放到后面
            for (int i = left; i < right; i++){
                if (array[i] > array[i+1]){
                    Tool.exchange(array,i ,i + 1);
                }
            }
            //已经把最大的值放到right的位置了，所以right要-1
            right--;
            // 后半轮,将最小元素放到前面
            for (int j = right; j > left;j--){
                if (array[j] < array[j - 1]){
                    Tool.exchange(array,j, j- 1);
                }
            }
            //已经把最小的值放到left的位置了，所以left要+1
            left++;
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        CocktailSort sort = new CocktailSort();
        sort.sort(a);
        System.out.println("array by CocktailSort is " + Tool.arrayToString(a));
    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

实现结果：

array by CocktailSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]