一、优化第一版

优化第一版是针对类似 int[] arr = {3,2,1,4,5,6,7,8,9; 这样的有很多已经排好序的数组，为了不让它做无用的循环，对于此场景进行的优化，优化代码如下：

// 优化第一版
public static void bubbleSort2(int[] arr, int len) {
    for (int i = 0; i < len; i++) {
        boolean isSorted = true;
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }
    }
}

程序定义了一个boolean类型的isSorted变量，用来判断往后的循环当中，数组是否已经是有序的，每一轮循环都会设置其值为true，当有元素对调位置时，就将isSorted的值设置为false，表示该数组还不是有序数组。每一轮都要判断isSorted的值，如果判断当前一轮操作没有元素有位置调换，那么可以提前结束所有的循环。读者可以自行举例数组检验。

二、优化第二版

我们针对优化第一版再进行优化。

这一版新增了两个int类型变量，一个是border，表示无序项的边界，同时也是每一轮循环的次数设定值，另一个是lastIndex，用来记录最后元素需要交换的下标值，进行一轮循环后，将这个值赋值给border，作为下一轮循环的次数。每一轮循环，当有元素需要调换位置时，记录j的位置，当前轮次循环结束，就将lastIndex赋值给border，最为新一轮循环操作的边界。

代码如下：

// 优化第二版
public static void bubbleSort3(int[] arr, int len) {
    int border = len - 1, lastIndex = 0;
    for (int i = 0; i < len; i++) {
        boolean isSorted = true;
        for (int j = 0; j < border; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                lastIndex = j;
                isSorted = false;
            }
        }
        border = lastIndex;
        if (isSorted) {
            break;
        }
    }
}

但是，优化第二版仍不是最优方案，上面的两种优化方案只是减少每轮的操作次数，还有一种可以直接减少循环的轮数，那就是鸡尾酒算法排序，请看下面的优化第三版。

三、优化第三版

鸡尾酒算法思想：冒泡排序是元素单向比较，而鸡尾酒排序却是双向。

列举一个最简单的栗子int[] arr = {2, 3, 4, 5, 6, 7, 8, 9, 1};

如果按照传统的冒泡排序进行操作，

第一轮结果：[2, 3, 4, 5, 6, 7, 8, 1, 9]，只有9和1交换；

第二轮结果：[2, 3, 4, 5, 6, 7, 1, 8, 9]，只有8和1交换；

第三轮结果：[2, 3, 4, 5, 6, 1, 7, 8, 9]，只有7和1交换；

。。。

第八轮结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]，只有2和1交换；

每一轮执行过程中，前面元素的比较，很明显做了无用功，对于本次栗子中的数组，如果元素比较的顺序是从右边开始，那就省了很多功夫，加入鸡尾酒算法，可以实现这个操作。

鸡尾酒算法实现冒泡排序：

// 优化第三版 (鸡尾酒算法)
public static void bubbleSort4(int[] arr, int len) {
    int temp = 0;
    boolean isSorted = true;
    for (int i = 0; i < len / 2 - 1; i++) {
        // 奇数轮比较
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }

        // 偶数轮比较
        for (int j = len - i - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }
    }
}

大循环中我们将循环轮次优化为len/2次，奇数轮比较顺序从左到右，每一轮 j 的开始项也从冒泡算法的0变成了 i ，因为下面还有偶数轮比较排序，偶数轮排序会将最左边的元素变成有序区。

鸡尾酒算法还可以再优化下，于是有了鸡尾酒算法的优化，如下第四版。

四、优化第四版

// 优化第四版 (鸡尾酒算法优化)
public static void bubbleSort5(int[] arr, int len) {
    int temp = 0;
    boolean isSorted = true;
    int lastLeftIndex = 0, lastRightIndex = 0;
    //左边界
    int leftBorder = 0;
    //右边界
    int rightBorder = arr.length - 1;

    for (int i = 0; i < len / 2 - 1; i++) {
        // 奇数轮比较
        for (int j = leftBorder; j < rightBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastRightIndex = j;
                isSorted = false;
            }
        }
        rightBorder = lastRightIndex;
        if (isSorted) {
            break;
        }

        // 偶数轮比较
        for (int j = rightBorder; j > leftBorder; j--) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                lastLeftIndex = j;
                isSorted = false;
            }
        }
        leftBorder = lastLeftIndex;
        if (isSorted) {
            break;
        }
    }
}

与传统冒泡法的第三版优化一样，设置了每一轮的循环边界，由于鸡尾酒算法是双向排序的，所以这里的边界也分别定义了左、右边界 leftBorder 和 rightBorder ，即每一轮循环都是以这两个边界为循环次数计算，相对于鸡尾酒第一版，第二版比较容易理解。

鸡尾酒算法实现冒泡排序的优化确实可以很大程度上减少了比较的无用功，同时也要注意它的代码量也是之前的两倍。

---

2020.5.7 更新。。。

对于冒泡排序优化，又想到了一种算法。

// 优化第五版 (引入标志位，只循环一次)
public static void bubbleSort6(int[] arr, int len) {
    boolean flag = true;
    while (flag) {
        flag = false;
        for (int i = 0; i < len - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                flag = true;
            }
        }
        len--;
    }
}

---

我自己测试了以下这几个版本的性能，10万随机数排序性能对比如下:

优化版本	性能耗时
第一版	18993 ms
第二版	19701 ms
第三版	15289 ms
第四版	11322 ms
第五版	19370 ms

这个数据各位小伙伴们看着选择，第二班比第一版还多，有点尴尬。第三版相对好点，第四版最好。第五版其实性能没有提升太多，如果注重代码简洁的可以选择第五版。

---

十大排序算法总结

【十大排序算法】（一）冒泡排序算法
【十大排序算法】（一）冒泡排序算法（优化）
【十大排序算法】（二）快速排序算法
【十大排序算法】（三）选择排序算法
【十大排序算法】（四）堆排序算法
【十大排序算法】（五）插入排序算法
【十大排序算法】（六）希尔排序算法
【十大排序算法】（七）归并排序算法
【十大排序算法】（八）计数排序算法
【十大排序算法】（九）桶排序算法
【十大排序算法】（十）基数排序算法