冒泡排序详解

mambaJava

已于 2022-09-28 19:27:40 修改

阅读量1.7k

点赞数 1

分类专栏：数据结构与算法系列文章标签：算法排序算法 java

于 2020-04-01 18:34:55 首次发布

本文链接：https://blog.csdn.net/Mr_Programming_Liu/article/details/105223941

版权

数据结构与算法系列专栏收录该内容

1 篇文章

订阅专栏

本文详细介绍了冒泡排序的概念、图例、两种优化版本的实现，并分析了冒泡排序的时间复杂度，包括最好、最坏和平均情况。此外，还讨论了冒泡排序作为原地排序和稳定排序的特点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一、冒泡排序介绍

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

二、冒泡排序图例

下面来看一个冒泡排序的实例，方便理解冒泡的过程（此处以升序为例）：
第一轮
第二轮
第三轮
第四轮
第五轮
第六轮
第七轮
第八轮

三、冒泡排序实现

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

}

执行结果如下：
执行结果1

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

}

执行结果如下：
执行结果2
接着回顾前面的图例，第二轮结束时，最后发生交换的是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;
            }
        }
    }

}

执行结果如下：
执行结果3

四、冒泡排序分析

1、冒泡排序是原地排序算法

因为冒泡排序过程中并不需要开辟新的数组空间，只需要常数个变量用于标记或者交换，所以冒泡排序是原地排序算法。

2、冒泡排序是稳定排序算法

在比较交换操作过程中，如果第一个元素大于第二个元素，我们才交换两个元素，两个元素相等时，保持不变。所以两个相等的元素在排序前后的相对位置并不会发生变化，所以冒泡排序是稳定排序算法。

3、时间复杂度是O(n²)

最好情况

此时数组本身已经有序，冒泡排序只需要一轮就可退出，时间复杂度为O(n)

最坏情况

此时数组本身是逆序的，完成冒泡排序需要n轮，比较的次数为n+(n-1)+(n-2)+…+2+1，时间复杂度为O(n²)

平均情况

鉴于对最坏情况下的时间复杂度分析，得出平均情况下的时间复杂度为O(n²)

乐于分享

最后放上笔者和几位好朋友(其中有博士、硕士、教师、工程师)一起用来记录分享的公众号【淹没在互联网的浪潮】，里面会分享心路历程、学习心得、各种经验等方面，不限于技术和学习，同时也会分享我们的所见所闻。如果有需要的话可以关注一下，有什么想看的分享话题也可以直接在公众号文章下留言。希望对大家能有所帮助，少走些弯路！