交换类排序

1.冒泡排序

原理：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

                  
代码实现：

public class Bubble {
    public static void main(String[] args) {
        int[] arr = {10,14,73,25,23,13,27,33,39,59,94,65,82,45};

        BubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void BubbleSort(int[] arr){
        int tmp;
        //外层for每次不同的遍历需要的次数
        for (int i = arr.length-1;i>0; i--) {
            //内层for每次遍历检索并交换
            for (int j = 0; j < i; j++) {
                if (arr[j+1]<arr[j]) {
                    tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
}

算法分析：
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要次交换，而插入排序只要最多交换。冒泡排序的实现通常会对已经排序好的数列拙劣地执行（），而插入排序在这个例子只需要个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。

2.鸡尾酒排序：也就是定向冒泡排序，与冒泡排序不同是在排序是以双向序列进行

                                 
代码实现：

public class cocktail {
    public static void main(String[] args) {
        int[] arr={3,2,5,1,4,8,9,0,6,7};
        cocktail_sort(arr);
        for(int i:arr){
            System.out.println(i);
        }

    }
    public static void cocktail_sort(int[] arr){
        int bottom = 0;
        int top = arr.length-1;
        boolean swaped = true;
        while(swaped==true){//如果已经处于排序则不需要在排
            swaped =false;
            for (int i = bottom; i < top; i++) {
                if(arr[i]>arr[i+1]){
                    int tmp = arr[i+1];
                    arr[i+1] = arr[i];
                    arr[i] = tmp;
                    swaped = true;
                }
            }
            top = top -1;;
            for (int i = top; i >bottom; i--) {
                if(arr[i]<arr[i-1]){
                    int tmp = arr[i-1];
                    arr[i-1] = arr[i];
                    arr[i] = tmp;
                    swaped = true;
                }
            }
            bottom = bottom+1;
        }
    }
}

与冒泡排序的不同：

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

以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。 但是在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲，优点只有观念简单这一点

复杂度：
鸡尾酒排序最糟或是平均所花费的次数都是，但如果序列在一开始已经大部分排序过的话，会接近。