如何优化冒泡排序？

一、冒泡排序（BubbleSort）

• 基本思想：从左到右使用相邻两个元素进行比较，如果第一个比第二个大，则交换两个元素。这样会使较大数下沉到数组的尾端，即较小数像泡泡一样冒到数组首端。
• 排序过程：

1. 比较相邻两个元素，如果第一个比第二个大，则交换两个元素；
2. 从左到右依次比较，直到最大数位于数组尾端；
3. 重复N-1次1、2步骤，(除去已经排序的最大数)依次将第二，第三。。。第N-1大的数排好位置。

如表格所示，每一趟都将当前乱序序列中最大的数移到尾端。【小伙伴们从表格中看出基本冒泡排序可以优化的地方了吗？】下面先来基本实现代码。

• java实现冒泡排序：

  private static <T extends Comparable<? super T>> void bubbleSort(T[] nums) {
        if (null == nums || nums.length == 0) {
            throw new RuntimeException("数组为null或长度为0");
        }
        T temp = null;
        int length = nums.length;
        //外循环是趟数，每一趟都会将未排序中最大的数放到尾端
        for (int i = 0; i < length - 1; i++) {
            //内循环是从第一个元素开始，依次比较相邻元素，
            // 比较次数随着趟数减少，因为每一趟都排好了一个元素
            for (int j = 0; j < length - 1 - i; j++) {
                if (nums[j].compareTo(nums[j + 1]) > 0) {
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
  

从表格中，相信小伙伴已经看出，在第5趟其实已经排好序了，但基本的冒泡排序算法还会进行第7趟比较，这其实只是进行没必要的比较，而不会进行元素的交换。（第6趟还是必须要走的，下面会说明）

• 时间、空间复杂度及稳定性分析：

1. 时间复杂度：由于内外循环都发生N次迭代，所以时间复杂度为O(n^2)。并且这个界是精确的。思考最坏的情况，输入一个逆序的数组，则比较次数为：

   (N-1)+(N-2)+(N-3)+..+2+1 = n*(n-1)/2 = O(n^2)

2. 空间复杂度：只使用了一个临时变量，所以为O(1)；

3. 是否稳定：稳定排序

二、优化冒泡排序

? 我们换个角度看待这个问题。基本冒泡算法之所以进行了无用的多余扫描，是因为不知道已经排好了序；所以只要我们在第 i 趟（i小于N-1）就知道序列已经排好序，我们就不用进行之后的扫描了。

综上所述，我们可以增加一个boolean变量，来标识是否已经排好序。优化代码如下：

冒泡排序优化普通版：

    private static <T extends Comparable<? super T>> void bubbleSort(T[] nums) {
        if (null == nums || nums.length == 0) {
            throw new RuntimeException("数组为null或长度为0");
        }

        T temp = null;
        int length = nums.length;
        //用于标识是否已经将序列排好序
        boolean isOrdered = false;
        for (int i = 0; i < length - 1; i++) {
            //每一趟开始前都假设已经有序
            isOrdered = true;
            for (int j = 0; j < length - 1 - i; j++) {
                if (nums[j].compareTo(nums[j + 1]) > 0) {
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    //如果出现有元素交换，则表明此躺可能没有完成排序
                    isOrdered = false;
                }
            }
            //如果当前趟都没有进行元素的交换，证明前面一趟比较已经排好序
            //直接跳出循环
            if (isOrdered) {
                break;
            }
        }
    }

注意：虽然第5趟已经排好序，但对于程序来说，它并不知道此趟已经排好序，需要进行下一趟扫描来确定上一趟是否已经将原序列排好序。所以第6趟是必须要去扫描的。

你以为结束了吗？哈哈哈，还没有，这只是第一版优化。

让我们想一想这样的情况。对于下列序列，前半部分乱序，后半部分有序。

简述排序过程：

第一趟：发生交换的是5和3，接着是5和2；随后5与6比较，不需要换位置，相同地，6与7、7与8、8与9都不需要更换位置。所以第一趟结果为：[4,3,2,5,6,7,8,9]。

第二趟：发生交换的是4与3，接着4与2；随后4与5、5与6，6与7、7与8都不需要更换位置。【8不需要与9比较，因为第一趟已经将最大的数下沉到尾端】。所以第二趟结果为：[3,2,4,5,6,7,8,9]。

第三趟：发生交换的是3与2；随后3与4，4与5，5与6，6与7都不需要更换位置。所以第三趟结果为：[2,3,4,5,6,7,8,9]。

大家看出什么了吗？其实进行了很多无意义的比较，因为这些都不需要更换位置，而很多趟都会重复比较。根据冒泡排序思想，我们知道，有序序列长度，其实跟排序趟数相等，每一趟就是将当前乱序中的最大值下沉到数组尾端。但其实序列真正有序的序列长度是大于当前排序趟数的。也就是说，只要我们找到了原序列中无序与有序的边界，就可以避免再去比较有序序列。

其实最后一次交换的位置，就是无序序列与有序序列的边界。

从例子中看：

第一趟最后一次交换的位置是元素5与2交换的位置，即数组下标2的位置；

第二趟最后一次交换的位置是元素4与2交换的位置，即数组下标1的位置；

第三趟最后一次交换的位置是元素3与2交换的位置，即数组下标0的位置；

所以，只要我们记录下当前趟最后一次交换的位置，在下一趟只比较到这个位置即可。

冒泡排序优化加强版：

    private static <T extends Comparable<? super T>> void bubbleSort(T[] nums) {
        if (null == nums || nums.length == 0) {
            throw new RuntimeException("数组为null或长度为0");
        }

        T temp = null;
        int length = nums.length;
        boolean isOrdered = false;
        int lastExchangeIndex = 0;
        //当前趟无序的边界
        int unorderedBorder = length - 1;
        for (int i = 0; i < length - 1; i++) {
            //每一趟开始前都假设已经有序
            isOrdered = true;
            for (int j = 0; j < unorderedBorder; j++) {
                if (nums[j].compareTo(nums[j + 1]) > 0) {
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    //如果出现有元素交换，则表明此躺没有完成排序
                    isOrdered = false;
                    //记录下最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            unorderedBorder = lastExchangeIndex;
            if (isOrdered) {
                break;
            }
        }
    }

其实，还可以进一步优化， 有兴趣的可以去看看鸡尾酒排序，我们已经很接近了。

三、总结

? 冒泡排序可以通过增加boolean标识是否已经排好序来进行优化；还可以记录下最后一次交换元素的位置来进行优化，防止无意义的比较。冒泡排序是稳定排序，时间复杂度为O(n^2)，空间复杂度为O(1)。