冒泡排序详解

梧桐树下的

16767人浏览 · 2022-08-27 20:55:53

梧桐树下的 · 2022-08-27 20:55:53 发布

一、冒泡排序介绍

冒泡排序是一种基于比较和交换操作的排序算法。每轮冒泡的过程都是从第一个元素开始，将该元素和相邻下一个元素进行比较和交换，使得较大的元素向右移动（如果该元素大于下一个元素，则两个元素交换；如果该元素小于等于下一个元素，则保持不变）。这样一来，每轮冒泡的过程都可以确定一个元素放在正确的位置上，而这个元素就是剩余元素中最大的元素，正确的位置就是剩余位置中的最右侧的位置。这个过程就像是气泡上浮一样，所以叫做冒泡排序。

二、冒泡排序图例

下面来看一个冒泡排序的实例，方便理解冒泡的过程（此处以升序为例）：

三、冒泡排序实现

1、第一版实现

这是根据前面的过程分析和图例例子直接实现的第一版冒泡排序。

public class BubbleSort {

    private static int number = 0; //记录冒泡排序的轮数

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 6, 2, 1, 4, 8, 7};

        bubbleSort(array);
        System.out.println(Arrays.toString(array));
        System.out.println("共经过" + number + "轮冒泡排序");
    }

    public static void bubbleSort(int[] array) {
        //外层控制冒泡的轮数，循环次数等于数组元素个数
        for (int i = 0; i < array.length; i++) {
            /*
                内层控制每轮冒泡的比较交换过程：
                    每轮都是从数组第一个元素开始进行比较
                    每轮的比较次数依次递减
             */
            for (int j = 0; j < array.length - i - 1; j++) {
                //比较交换
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            number++;
        }
    }

}

执行结果如下：

2、优化版本

回顾上面的图例，可以发现实际上第四轮结束后，数组已经是有序的，所以后面的每轮冒泡都只有比较操作而没有交换操作了。这是因为前面的每轮冒泡不仅会确定一个最大的元素放在最右侧，还会使得较大的元素往右侧移动，所以冒泡排序通常会提前几轮就能达到有序（除非数组是完全逆序的，大家可以举个例子思考一下此时需要多少轮排序【轮数=元素个数】）。优化点1：如果在某轮排序中，没有发生交换操作，说明数组已经有序，可提前退出排序。

优化版本1

public class BubbleSort {

    private static int number = 0; //记录冒泡排序的轮数

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 6, 2, 1, 4, 8, 7};

        bubbleSort(array);
        System.out.println(Arrays.toString(array));
        System.out.println("共经过" + number + "轮冒泡排序");
    }

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean isOccurExchange = false; //表示是否发生交换操作，每轮结束后置为false
            for (int j = 0; j < array.length - i - 1; j++) {
                //比较交换
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isOccurExchange = true;
                }
            }
            number++;
            if (!isOccurExchange) {//说明这轮没有发生元素交换，数组已经有序
                break;
            }
        }
    }

}

执行结果如下：

接着回顾前面的图例，第二轮结束时，最后发生交换的是5和4，实际上元素5、6、7、8均已有序，可是第三轮比较操作依然进行到元素6；第三轮结束时，最后发生交换的是3和1，此时3、4、5、6、7、8已有序，可是第四轮比较操作依然进行到元素5。所以如果能得知每轮排序过程中最后发生交换操作的位置，下一轮比较操作只需要进行到该位置即可结束。优化点2：每轮排序过程中，记录下最后发生交换操作的位置，在下一轮循环中只需要比较到该位置即可，如果该位置为0，即数组第一个元素，说明数组已经有序，可提前退出排序。

优化版本2

public class BubbleSort {

    private static int number = 0; //记录冒泡排序的轮数

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 6, 2, 1, 4, 8, 7};

        bubbleSort(array);
        System.out.println(Arrays.toString(array));
        System.out.println("共经过" + number + "轮冒泡排序");
    }

    public static void bubbleSort(int[] array) {
        int lastExchangeIndex = 0; //记录每轮排序过程中最后发生交换操作的位置
        int unorderedEndIndex = array.length - 1; //记录需要进行比较(无序)范围的最后位置
        for (int i = 0; i < array.length; i++) {
            boolean isOccurExchange = false; //表示是否发生交换操作，每轮结束后置为false
            for (int j = 0; j < unorderedEndIndex; j++) {
                //比较交换
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isOccurExchange = true;
                    //j后面的元素均已有序，下轮排序只需比较到j位置即可
                    lastExchangeIndex = j;
                }
            }

            unorderedEndIndex = lastExchangeIndex;
            number++;
            if (unorderedEndIndex == 0) {//数组已经有序
                break;
            }
            if (!isOccurExchange) {//说明这轮没有发生元素交换，数组已经有序
                break;
            }
        }
    }

}

执行结果如下：