原理

冒泡排序原理：

冒泡排序是较简单的排序算法，它是比较相邻两个元素的大小，并进行交换。

1、两个相邻元素进行比较，如果第一个比第二个大就交换(升序)，

2、重复1动作，从开始第一对到最后一对，次数会越来越少

3、直到没有可以比较的元素，最后一位数字是最大的。

时间复杂度：O(n²)
空间复杂度：1
稳定性：稳定：比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变。简而言之，相同元素的前后顺序不会改变
鸡尾酒冒泡排序原理：

鸡尾酒排序又叫双向冒泡排序，是冒泡排序的一种优化，排序时以双向在序列中进行排序，从低到高然后从高到低

1、先找到最小的数字，放在第一位，然后找到最大数字放在最后，

2、接着找第二小的数字放在第二位，找到第二大数字放在倒数第二位，

3、一次类推

时间复杂度：O(n²)
空间复杂度：1

冒泡排序动态示意图

当数据量小的时候看不出2者的快慢，可以把下面的示例里的长度改成10000，会发现鸡尾酒排序会快些

示例

import java.util.Random;

/**
 * 冒泡排序
 * 鸡尾酒冒泡排序
 * 
 **/
public class BulkSort {
    public static void main(String[] args) {
        int len = 10;
        int[] datas = new int[len];
        int[] copyDatas = new int[len];

        Random r = new Random(0);
        for(int i = 0; i < len;i++) {
            int d = r.nextInt(100);
            datas[i] = d;
            copyDatas[i] = d;
        }
        long start = System.currentTimeMillis();
        bulkSort(datas);
        long spend = System.currentTimeMillis() - start;
        System.out.println("******  spend " + spend);
        for (int data:
             datas) {
            System.out.print(data + ",");
        }
        System.out.println("");
        start = System.currentTimeMillis();
        shakerBulkSort(copyDatas);
        spend = System.currentTimeMillis() - start;
        System.out.println("******  shaker spend " + spend);
        for (int data:
                copyDatas) {
            System.out.print(data + ",");
        }
    }

    /**
     * 冒泡排序：
     *    假设升序排序
     *   当前元素向后按顺序和相邻元素比较，
     *   若当前元素比比较的元素大则交换，否则继续向后面进行比较
     * @param datas
     */
    public static void bulkSort(int[] datas) {
        int len = datas.length;
        if(len == 0) {
            return;
        }
        //排序趟数
        for (int i = 1; i < len; i++) {
            //每趟比较次数
            for (int currIdx = 0; currIdx < len - i; currIdx ++) {
                int cmpIdx = currIdx + 1;
                //相邻量元素之间进行比较，逆序就交换
                if(datas[currIdx] > datas[cmpIdx]) {
                    int temp = datas[currIdx];
                    datas[currIdx] = datas[cmpIdx];
                    datas[currIdx + 1] = temp;
                }
            }
        }
    }

    /**
     * 双向冒泡排序，也叫鸡尾酒算法
     *  
     * @param datas
     */
    public static void shakerBulkSort(int[] datas) {
        int len = datas.length;
        if(len == 0) {
            return;
        }
        int midLen = len / 2;
        //排序趟数
        for (int i = 0; i < midLen; i++) {
            //每趟比较次数
            for (int currIdx = i; currIdx < len-i-1 ; currIdx ++) {
                int cmpIdx = currIdx + 1;
                //相邻量元素之间进行比较，逆序就交换
                if(datas[currIdx] > datas[cmpIdx]) {
                    int temp = datas[currIdx];
                    datas[currIdx] = datas[cmpIdx];
                    datas[cmpIdx] = temp;
                }
            }
            for (int currIdx = len - 1 - (i+1); currIdx > i; currIdx --) {
                int cmpIdx = currIdx - 1;
                //相邻量元素之间进行比较，逆序就交换
                if(datas[currIdx] < datas[cmpIdx]) {
                    int temp = datas[currIdx];
                    datas[currIdx] = datas[cmpIdx];
                    datas[cmpIdx] = temp;
                }
            }
        }
    }}