Java 冒泡排序与优化

冒泡排序是最经典的排序算法之一，其主要思路是两两比较相邻位置的元素，并交换其位置，直到结束。

排序存在两种场景：升序和降序，这里仅讨论升序的情况。

冒泡思想

冒泡排序文字描述：

依次比较数组中响铃两个元素的大小，若前一个大于后一个，则交换两个元素。

两两比较完一遍称为一轮冒泡，结果是最大元素排至最后。

重复以上步骤，直到所有元素有序。

经典实现

为了能更好地展示冒泡排序的主要思想，我将数据准备工作定义在 main() 方法中。

public static void main(String[] args) {
    int[] nums = {5,9,7,4,6,1,3,2,8};
    System.out.println("排序前 " + Arrays.toString(nums));
    bubbleSort(nums);
    System.out.println("排序后 " + Arrays.toString(nums));
}

public static void bubbleSort(int[] nums){

}

冒泡排序比较与交换

交换数组中两个位置的元素，可以采用下面的通用代码：

public static void swap(int[] nums, int m, int n){
    int tmp = nums[m];
    nums[m] = nums[n];
    nums[n] = tmp;
}

比较相邻元素：

public static void bubbleSort(int[] nums){
    // 遍历数组中每个元素
    for(int j = 0; j < nums.length - 1; j++){
        // 左右两个元素比较，如果左边的元素大于右边元素，就和右边元素交换
        if(nums[j] > nums[j+1]){
            swap(nums, j, j+1);
        }
    }
}

此时，我们可以看一下结果。实际上，一趟遍历，可以把数组中最大的元素移动到数组末尾。

既然一次遍历可以将最大数冒泡到最右边，我们可以多进行几轮遍历。

public static void bubbleSort(int[] nums){
    // 遍历 n 次
    for(int i = 0; i< nums.length - 1; i++) {
        // 遍历数组中每个元素
        for (int j = 0; j < nums.length - 1; j++) {
            // 左右两个元素比较，如果左边的元素大于右边元素，就和右边元素交换
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
            }
        }
    }
}

减少比较次数

为了观察内部的细节，可以在内层循环中添加一些日志：

public static void bubbleSort(int[] nums){
    for(int i = 0; i< nums.length - 1; i++) {
        for (int j = 0; j < nums.length - 1; j++) {
            System.out.print("比较 " + nums[j] + " 与 " + nums[j+1] + "; ");
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
            }
        }
        System.out.println();
    }
}

观察每一次遍历的最后几次比较，可以发现有很多无意义的比较，因为我们已经可以确定每一趟遍历过后，右边的数已经排好序了，不需要再进行比较了。

为此，只需要如下修改：

for (int j = 0; j < nums.length - 1 - i; j++) {

每遍历一次，就可以忽略最右边已经排序好的数据。

从打印结果可以看到，我们少了一半的比较次数，也能得到正确的结果。

降低遍历次数

在内层循环中，我们通过一些方法降低了比较次数，再来看看外层循环。

public static void bubbleSort(int[] nums){
    for(int i = 0; i< nums.length - 1; i++) {
        for (int j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
            }
        }
        System.out.println("第" + (i+1) + "次遍历后 " + Arrays.toString(nums));
    }
}

从下面的结果可以看到，我们第 6 次遍历后，数据已经有序了。当数据有序以后，还进行了几轮遍历，我们应该想办法停止循环。

如何知道当前数组已经有序？

可以通过是否有元素交换得到当前数据是否有序。

下面定义一个 sorted 变量，如果该变量没有因交换元素而变更，就跳出外层循环。

public static void bubbleSort(int[] nums){
    for(int i = 0; i< nums.length - 1; i++) {
        boolean sorted = true;
        for (int j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                sorted = false;
            }
        }
        if(sorted){
            break;
        }
        System.out.println("第" + (i+1) + "次遍历后 " + Arrays.toString(nums));
    }
}

可以看到，当数组整体有序以后，不再进行后续遍历，直接得到结果。

冒泡改进

我们换一个数据样本，此时的数据基本有序：

int[] nums = {1,3,4,6,7,2,8,9};

将内层循环的比较日志打印出来：

即使部分数据已经有序了，我们还是在不断地比较。

为了减少不不必要的比较次数，可以引入一个中间变量，记录最后一次数据交换的前一个位置。然后下一次遍历只需要到这个记录的位置即可。

为什么可以这样？

数据最后一次交换的位置后面的元素一定是排序好的，否则还会发生元素交换。

用 last 记录每次数据交换的位置，最终跳出内层循环时，last 记录的就是最后一次数据交换的前一个位置。

注意内层循环的终止条件是上一轮最后一次数据交换的位置。

for (int j = 0; j < cnt; j++) {

为了记录这个位置，需要再使用一个中间变量 cnt 记录该值。

更进一步，当 last 为 0 时，说明已经没有数据交换了，所有数据已经有序，我们可以提前跳出循环。

public static void bubbleSortV2(int[] nums){
    int cnt = nums.length - 1;
    for(int i = 0; i< nums.length - 1; i++) {
        int last = 0;
        for (int j = 0; j < cnt; j++) {
            System.out.print("比较 " + nums[j] + " 与 " + nums[j+1] + "; ");
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                last = j;
            }
        }
        cnt = last;
        System.out.println();
        if(last == 0){
            break;
        }
    }
}

和之前的版本相比，明显的比较次数减少了。

再观察外层循环，由于此时的变量 i 没有参与任何逻辑处理，我们可以将其简化为 while(true)：

public static void bubbleSortV2(int[] nums){
    int cnt = nums.length - 1;
    while(true) {
        int last = 0;
        for (int j = 0; j < cnt; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                last = j;
            }
        }
        cnt = last;
        if(last == 0){
            break;
        }
    }
}

元素近乎有序时

来个更极端的场景，只有极少数的元素无序时，我们采用原始的冒泡排序：

public static void bubbleSort(int[] nums){
    for(int i = 0; i< nums.length - 1; i++) {
        boolean sorted = true;
        for (int j = 0; j < nums.length - 1 - i; j++) {
            System.out.print("比较 " + nums[j] + " 与 " + nums[j+1] + "; ");
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                sorted = false;
            }
        }
        System.out.println();
        if(sorted){
            break;
        }
    }
}

假设元素个数 n，比较的次数为 (n – 1) + (n – 2)，当 n 足够大时，比较次数接近 2n。

改进版的冒泡排序：

public static void bubbleSortV2(int[] nums){
    int cnt = nums.length - 1;
    for(int i = 0; i< nums.length - 1; i++) {
        int last = 0;
        for (int j = 0; j < cnt; j++) {
            System.out.print("比较 " + nums[j] + " 与 " + nums[j+1] + "; ");
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                last = j;
            }
        }
        cnt = last;
        System.out.println();
        if(last == 0){
            break;
        }
    }
}

假设元素个数 n，比较的次数为 n。当 n 足够大时，n 次比较和 2n 次比较差距明显。

完整代码

public class Bubble {

    public static void main(String[] args) {
        int[] nums = {5,9,7,4,6,1,3,2,8};
//        int[] nums = {1,3,4,6,7,2,8,9};
//        int[] nums = {1,3,2,4,5,6,8,9};
        System.out.println("排序前 " + Arrays.toString(nums));
        bubbleSort(nums);
//        bubbleSortV2(nums);
        System.out.println("排序后 " + Arrays.toString(nums));
    }

    /**
     * 改进的冒泡排序
     */
    public static void bubbleSortV2(int[] nums){
        int cnt = nums.length - 1;
        for(int i = 0; i< nums.length - 1; i++) {
            int last = 0;
            for (int j = 0; j < cnt; j++) {
                System.out.print("比较 " + nums[j] + " 与 " + nums[j+1] + "; ");
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    last = j;
                }
            }
            cnt = last;
            System.out.println();
            if(last == 0){
                break;
            }
        }
    }

    /**
     * 经典的冒泡排序
     */
    public static void bubbleSort(int[] nums){
        for(int i = 0; i< nums.length - 1; i++) {
            boolean sorted = true;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                System.out.print("比较 " + nums[j] + " 与 " + nums[j+1] + "; ");
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    sorted = false;
                }
            }
            System.out.println();
            if(sorted){
                break;
            }
        }
    }

    /**
     * 数组中两数交换
     */
    public static void swap(int[] nums, int m, int n){
        int tmp = nums[m];
        nums[m] = nums[n];
        nums[n] = tmp;
    }
}