冒泡排序的优化

优化的点

如果在一次循环中，都没有「冒泡」行为发生，整个排序任务就可以 提前终止。

• 可以设置布尔变量 sorted，假设每一轮循环开始假设数组是有序的；
• 一旦在比较的过程中执行了交换，说明数组不是有序的，将 sorted 设置为 false；
• 如果在一次循环中，都没有「冒泡」行为发生，才可以认为剩下的部分是有序的。

参考代码：

说明：该代码在「力扣」运行超时。

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i >= 0; i--) {
            // 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较
            boolean sorted = true;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    sorted = false;
                }
            }

            // 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组
            if (sorted) {
                break;
            }
        }
        return nums;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

补充说明：下面这份代码是讲课的时候写的代码，区别仅在于内层循环中对 j 的定义不同。

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            boolean sorted = true;
            for (int j = 1; j < len - i; j++) {
                if (nums[j - 1] > nums[j]) {
                    swap(nums, j - 1, j);
                    sorted = false;
                }
            }
            if (sorted) {
                return nums;
            }
        }
        return nums;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

复杂度分析：

• 时间复杂度：，这里 是输入数组的长度；
• 空间复杂度：。

调试代码

使用一个极端的例子来理解冒泡排序：

控制台输出：

---

作者：liweiwei1419 链接：https://suanfa8.com/basic-sorting-algorithm/bubble-sort/optimization 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。