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);
        }
    }
}

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

排序前 [5, 9, 7, 4, 6, 1, 3, 2, 8]
排序后 [5, 7, 4, 6, 1, 3, 2, 8, 9]

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

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);
            }
        }
    }
}
排序前 [5, 9, 7, 4, 6, 1, 3, 2, 8]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9]

减少比较次数

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

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();
    }
}
排序前 [5, 9, 7, 4, 6, 1, 3, 2, 8]
比较 5 与 9; 比较 9 与 7; 比较 9 与 4; 比较 9 与 6; 比较 9 与 1; 比较 9 与 3; 比较 9 与 2; 比较 9 与 8;
比较 5 与 7; 比较 7 与 4; 比较 7 与 6; 比较 7 与 1; 比较 7 与 3; 比较 7 与 2; 比较 7 与 8; 比较 8 与 9;
比较 5 与 4; 比较 5 与 6; 比较 6 与 1; 比较 6 与 3; 比较 6 与 2; 比较 6 与 7; 比较 7 与 8; 比较 8 与 9;
比较 4 与 5; 比较 5 与 1; 比较 5 与 3; 比较 5 与 2; 比较 5 与 6; 比较 6 与 7; 比较 7 与 8; 比较 8 与 9;
比较 4 与 1; 比较 4 与 3; 比较 4 与 2; 比较 4 与 5; 比较 5 与 6; 比较 6 与 7; 比较 7 与 8; 比较 8 与 9;
比较 1 与 3; 比较 3 与 2; 比较 3 与 4; 比较 4 与 5; 比较 5 与 6; 比较 6 与 7; 比较 7 与 8; 比较 8 与 9;
比较 1 与 2; 比较 2 与 3; 比较 3 与 4; 比较 4 与 5; 比较 5 与 6; 比较 6 与 7; 比较 7 与 8; 比较 8 与 9;
比较 1 与 2; 比较 2 与 3; 比较 3 与 4; 比较 4 与 5; 比较 5 与 6; 比较 6 与 7; 比较 7 与 8; 比较 8 与 9;
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9]

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

为此,只需要如下修改:

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

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

排序前 [5, 9, 7, 4, 6, 1, 3, 2, 8]
比较 5 与 9; 比较 9 与 7; 比较 9 与 4; 比较 9 与 6; 比较 9 与 1; 比较 9 与 3; 比较 9 与 2; 比较 9 与 8;
比较 5 与 7; 比较 7 与 4; 比较 7 与 6; 比较 7 与 1; 比较 7 与 3; 比较 7 与 2; 比较 7 与 8;
比较 5 与 4; 比较 5 与 6; 比较 6 与 1; 比较 6 与 3; 比较 6 与 2; 比较 6 与 7;
比较 4 与 5; 比较 5 与 1; 比较 5 与 3; 比较 5 与 2; 比较 5 与 6;
比较 4 与 1; 比较 4 与 3; 比较 4 与 2; 比较 4 与 5;
比较 1 与 3; 比较 3 与 2; 比较 3 与 4;
比较 1 与 2; 比较 2 与 3;
比较 1 与 2;
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9]

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

降低遍历次数

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

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 次遍历后,数据已经有序了。当数据有序以后,还进行了几轮遍历,我们应该想办法停止循环。

排序前 [5, 9, 7, 4, 6, 1, 3, 2, 8]
第1次遍历后 [5, 7, 4, 6, 1, 3, 2, 8, 9]
第2次遍历后 [5, 4, 6, 1, 3, 2, 7, 8, 9]
第3次遍历后 [4, 5, 1, 3, 2, 6, 7, 8, 9]
第4次遍历后 [4, 1, 3, 2, 5, 6, 7, 8, 9]
第5次遍历后 [1, 3, 2, 4, 5, 6, 7, 8, 9]
第6次遍历后 [1, 2, 3, 4, 5, 6, 7, 8, 9]
第7次遍历后 [1, 2, 3, 4, 5, 6, 7, 8, 9]
第8次遍历后 [1, 2, 3, 4, 5, 6, 7, 8, 9]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9]

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

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

下面定义一个 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));
    }
}

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

排序前 [5, 9, 7, 4, 6, 1, 3, 2, 8]
第1次遍历后 [5, 7, 4, 6, 1, 3, 2, 8, 9]
第2次遍历后 [5, 4, 6, 1, 3, 2, 7, 8, 9]
第3次遍历后 [4, 5, 1, 3, 2, 6, 7, 8, 9]
第4次遍历后 [4, 1, 3, 2, 5, 6, 7, 8, 9]
第5次遍历后 [1, 3, 2, 4, 5, 6, 7, 8, 9]
第6次遍历后 [1, 2, 3, 4, 5, 6, 7, 8, 9]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9]

冒泡改进

我们换一个数据样本,此时的数据基本有序:

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

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

排序前 [1, 3, 4, 6, 7, 2, 8, 9]
比较 1 与 3; 比较 3 与 4; 比较 4 与 6; 比较 6 与 7; 比较 7 与 2; 比较 7 与 8; 比较 8 与 9;
比较 1 与 3; 比较 3 与 4; 比较 4 与 6; 比较 6 与 2; 比较 6 与 7; 比较 7 与 8;
比较 1 与 3; 比较 3 与 4; 比较 4 与 2; 比较 4 与 6; 比较 6 与 7;
比较 1 与 3; 比较 3 与 2; 比较 3 与 4; 比较 4 与 6;
比较 1 与 2; 比较 2 与 3; 比较 3 与 4;
排序后 [1, 2, 3, 4, 6, 7, 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;
        }
    }
}
排序前 [1, 3, 4, 6, 7, 2, 8, 9]
比较 1 与 3; 比较 3 与 4; 比较 4 与 6; 比较 6 与 7; 比较 7 与 2; 比较 7 与 8; 比较 8 与 9;
比较 1 与 3; 比较 3 与 4; 比较 4 与 6; 比较 6 与 2;
比较 1 与 3; 比较 3 与 4; 比较 4 与 2;
比较 1 与 3; 比较 3 与 2;
比较 1 与 2;
排序后 [1, 2, 3, 4, 6, 7, 8, 9]

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

再观察外层循环,由于此时的变量 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;
        }
    }
}
排序前 [1, 3, 2, 4, 5, 6, 8, 9]
比较 1 与 3; 比较 3 与 2; 比较 3 与 4; 比较 4 与 5; 比较 5 与 6; 比较 6 与 8; 比较 8 与 9;
比较 1 与 2; 比较 2 与 3; 比较 3 与 4; 比较 4 与 5; 比较 5 与 6; 比较 6 与 8;
排序后 [1, 2, 3, 4, 5, 6, 8, 9]

假设元素个数 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;
        }
    }
}
排序前 [1, 3, 2, 4, 5, 6, 8, 9]
比较 1 与 3; 比较 3 与 2; 比较 3 与 4; 比较 4 与 5; 比较 5 与 6; 比较 6 与 8; 比较 8 与 9;
比较 1 与 2;
排序后 [1, 2, 3, 4, 5, 6, 8, 9]

假设元素个数 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;
    }
}