冒泡算法

冒泡排序(bubble sort)是很经典的 交换排序 算法，为什么叫做冒泡，就是因为这个算法的每一个元素都像小气泡一样，根据自身大小，往数组的一侧移动。

思想

把相邻的元素两两比较，当一个元素大于右侧元素时，两个元素交换，如果没有，位置不变

• 每一遍历完一轮，总有一个最大的元素移到最右侧
• 冒泡算法是一个稳定的算法
• 每一轮都要遍历所有没排序的元素，总共遍历 n-1 轮，因此时间复杂度为O(n^2)

实现

public void bubbleSort(int array[]){
    for(int i = 0; i < array.length-1; i++){
        //有序标志，每一轮初值为true
        //如果是执行一轮过后还是true，就是没有进行交换，则数组以有序，循环结束
        boolean isSorted = true;
        for(int j = 0; j < array.length-i-1; j++){
            int tmp = 0;
            if(array[j] > array[j+1]){
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                isSorted = false;//发生了交换
            }
        }

        if(isSorted) break;
    }
}

双向冒泡：鸡尾酒排序

冒泡排序的每一个元素都是向右移动的，是单向的，鸡尾酒排序是 双向 的，奇数找最大的，偶数找最小的，但是代码量增加了一倍，在大部分元素有序的情况下，鸡尾酒排序更有优势

public void doubleBubbleSort(int array[]){
    int tmp = 0;
    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]){
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                isSorted = false;//发生了交换
            }
        }
        if(isSorted) break;

        //偶数轮，重新标记
        isSorted = true;
        for(int j = array.length-i-1; j > i; j--){
            if(array[j] <> array[j-1]){
                tmp = array[j];
                array[j] = array[j-1];
                array[j-1] = tmp;
                isSorted = false;//发生了交换
            }
        }
        if(isSorted) break;
    }
}