冒泡排序优化、鸡尾酒排序

参考书籍：《漫画算法小灰的算法之旅》
（1）冒泡排序中，当数组后半部分的元素逐渐变得有序后，仍然会进行多次比较，从这一点进行优化。
设置变量记录有序区域，每次比较时仅仅比较无序区域的元素即可。

public class PubblesortTo {
    public static void main(String []args){
        int array[] = {1,2,6,3,16,4,3,11,5};
        pubbleSort03(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+",");
        }
    }
    public static void pubbleSort03(int array[]){
            //最后一次交换的下标
        int LastExchangeIndex = 0;
        //有序边界
        int SortBorder = array.length -1;
        for(int i = 0;iarray[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //发生交换则将flag设置为false,即假设错误，数组并不是有序的
                    flag = false;
                    LastExchangeIndex = j;
                }
            }
            SortBorder = LastExchangeIndex;
            if(flag){
                break;
            }
        }
    }
}

（2）鸡尾酒排序（双向冒泡排序，搅拌排序，来回排序）
常规冒泡排序存在着如下问题。
如图，只有1顺序不对，但仍需进行7轮排序。

鸡尾酒排序流程：


第三轮虽然已经有序，还是会从左到右进行一轮比较，没有元素进行位置交换，证明已经有序，排序结束。
思路：像钟摆一样，第一轮从左到右，第二轮从右到左，第三轮从左到右…

public class CocktailSort {
    public static void main(String []args){
        int array[] = {1,2,6,3,16,4,3,11,1,5};
        cocktailSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+",");
        }
    }
    public static void cocktailSort(int []array){
        int tmp = 0;
        //这里一个外层循环对应两个内层循环，因此使用数组长度/2
        for (int i = 0; i < array.length /2 ; i++) {
            //flag设为true,假设此时数组有序
            boolean flag = true;
            for(int j = i ;j< array.length - i -1;j++){
                if(array[j]>array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //发生交换则假设错误，将flag设为flase
                    flag = false;
                }
            }
            //flag为true表示假设正确，直接退出循环
            if(flag){
                break;
            }
            //开始偶数轮前重新置flag为true
            flag = true;
            //这里偶数轮采用反方向，因此从后往前遍历,for循环的条件改变
            for(int j = array.length -1 -1;j>i ; j--){
                //这里比较也是反方向
                if (array[j] < array[j-1]) {
                    tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    flag = false;//同前
                }
            }
            if(flag){
                break;
            }
        }
    }
}

鸡尾酒排序和上面的优化方法可以结合。
缺点：鸡尾酒排序代码量更大。优点：某些情况下可以大大节省资源。