[数据结构与算法] （四）Java算法：冒泡排序

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> （四）Java算法：冒泡排序 -> 正文阅读

[数据结构与算法]（四）Java算法：冒泡排序

一、简介

??冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它的工作原理是：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果不是指定顺序（比如从小达到）就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

二、maven依赖

pom.xml

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter</artifactId>
        <version>2.6.0</version>
    </dependency>

    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <version>1.16.14</version>
    </dependency>
</dependencies>

三、多个版本实现

3.1、基础版本

??冒泡排序有很多实现，我们先看看它的最基本的实现。

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSortBase(int[] arr) {
        // 数组的长度
        int length = arr.length;
        // 遍历数组
        for (int i = 0; i < length; i++) {
            log.info("第【{}】轮排序将准备比较【{}】次", i + 1, length - 1 - i);
            for (int j = 0; j < length - 1 - i; j++) {
                // 从小到大排序,如果前一个元素【arr[j] 】比后一个元素【arr[j + 1]】大，则交换位置
                if (arr[j] > arr[j + 1]) {
                    log.info("【{}】与【{}】进行交换", arr[j], arr[j + 1]);
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            log.info("第【{}】轮排序后的结果：{}", i + 1, arr);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{23, 8, 10, 21, 19, 9};
        log.info("要排序的初始化数据：{}", arr);
        //从小到大排序
        bubbleSortBase(arr);
    }

??运行结果（只有满足交换条件的比较才会进行交换）：

--------------------3.1、基础版本-------------------------
要排序的初始化数据：[23, 8, 10, 21, 19, 9]
第【1】轮排序将准备比较【5】次      ---->就是6个数相邻两个数依次进行比较（满足条件的就交换）
【23】与【8】进行交换后数组变成--> [8, 23, 10, 21, 19, 9]
【23】与【10】进行交换后数组变成--> [8, 10, 23, 21, 19, 9]
【23】与【21】进行交换后数组变成--> [8, 10, 21, 23, 19, 9]
【23】与【19】进行交换后数组变成--> [8, 10, 21, 19, 23, 9]
【23】与【9】进行交换后数组变成--> [8, 10, 21, 19, 9, 23]
第【1】轮排序后的结果：[8, 10, 21, 19, 9, 23]
第【2】轮排序将准备比较【4】次      --->第一个最大的数已经排序完毕了，剩下5个数，也就是比较4次了
【21】与【19】进行交换后数组变成--> [8, 10, 19, 21, 9, 23]
【21】与【9】进行交换后数组变成--> [8, 10, 19, 9, 21, 23]
第【2】轮排序后的结果：[8, 10, 19, 9, 21, 23]
第【3】轮排序将准备比较【3】次      --->两个最大的数已经排序完毕了，剩下4个数，也就是比较3次了
【19】与【9】进行交换后数组变成--> [8, 10, 9, 19, 21, 23]
第【3】轮排序后的结果：[8, 10, 9, 19, 21, 23]
第【4】轮排序将准备比较【2】次      --->三个最大的数已经排序完毕了，剩下3个数，也就是比较2次了
【10】与【9】进行交换后数组变成--> [8, 9, 10, 19, 21, 23]
第【4】轮排序后的结果：[8, 9, 10, 19, 21, 23]
第【5】轮排序将准备比较【1】次     --->四个最大的数已经排序完毕了，剩下2个数，也就是比较1次了
第【5】轮排序后的结果：[8, 9, 10, 19, 21, 23]
第【6】轮排序将准备比较【0】次     --->五个最大的数已经排序完毕了，剩下1个数，不用比较了，也就是排完了
第【6】轮排序后的结果：[8, 9, 10, 19, 21, 23]

??我希望大家把这个最基础的版本先搞懂，画图太麻烦了，但是我觉得如果你把文字都看懂了，这里的数据流向的印象就会非常的深刻的，再看后面的两个版本。就容易理解。当然，后面的版本也不是强制要求，如果你想继续优化可以参考后面的两种方法。

3.2、优化版本

??这个版本是怎么来的呢，我们先看一组要排序的数据，调用我们刚才的基础版本。假设我们需要排序的数组数据是：23, 8, 9, 10, 21, 39, 29, 30

    public static void main(String[] args) {
        log.info("--------------------3.2、基础版本-------------------------");
        int[] arr1 = new int[]{23, 8, 9, 10, 21, 39, 29, 30};
        log.info("要排序的初始化数据：{}", arr1);
        //从小到大排序
        bubbleSortBase(arr1);
    }

??基础版本运行结果如下：

--------------------3.2、基础版本-------------------------
要排序的初始化数据：[23, 8, 9, 10, 21, 39, 29, 30]
第【1】轮排序将准备比较【7】次
【23】与【8】进行交换后数组变成--> [8, 23, 9, 10, 21, 39, 29, 30]
【23】与【9】进行交换后数组变成--> [8, 9, 23, 10, 21, 39, 29, 30]
【23】与【10】进行交换后数组变成--> [8, 9, 10, 23, 21, 39, 29, 30]
【23】与【21】进行交换后数组变成--> [8, 9, 10, 21, 23, 39, 29, 30]
【39】与【29】进行交换后数组变成--> [8, 9, 10, 21, 23, 29, 39, 30]
【39】与【30】进行交换后数组变成--> [8, 9, 10, 21, 23, 29, 30, 39]
第【1】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【2】轮排序将准备比较【6】次
第【2】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【3】轮排序将准备比较【5】次
第【3】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【4】轮排序将准备比较【4】次
第【4】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【5】轮排序将准备比较【3】次
第【5】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【6】轮排序将准备比较【2】次
第【6】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【7】轮排序将准备比较【1】次
第【7】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【8】轮排序将准备比较【0】次
第【8】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]

??如果你熟悉基础版本了看这个就很清晰了。我们这个数组经过我们第一次排序后，数据就已经是有序的了，但是我们的程序还是进行比较，比如第【2】轮排序将准备比较【6】次，第【3】轮排序将准备比较【5】次等等。那有什么办法，如果我们的数据已经有序就不用再比较了呢？这就是我们优化版本要解决的，具体实现如下：

    /**
     * 冒泡排序(优化版本--最后几轮排序时剩下的数组数据有序)
     *
     * @param arr
     */
    public static void bubbleSortOptimize(int[] arr) {
        // 数组的长度
        int length = arr.length;
        // 遍历数组
        for (int i = 0; i < length - 1; i++) {
            // 有序标记，每一轮排序的初始值都是true
            boolean isOrderly = true;
            log.info("第【{}】轮排序将准备比较【{}】次", i + 1, length - 1 - i);
            for (int j = 0; j < length - i - 1; j++) {
                // 从小到大排序,如果前一个元素【arr[j] 】比后一个元素【arr[j + 1]】大，则交换位置
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    // 有元素交换，所以不是有序，标记变为false
                    isOrderly = false;
                    log.info("【{}】与【{}】进行交换后数组变成--> {}", arr[j + 1], arr[j], arr);
                }
            }
            log.info("第【{}】轮排序后的结果：{}", i + 1, arr);
            // 如果没有交换,说明数组已经有序了,直接跳出大循环
            if (isOrderly) {
                log.info("第【{}】轮排序后跳出循环", i + 1);
                break;
            }
        }
    }

??从我们优化代码来看，我们就是每一轮排序加了一个标志位isOrderly，标识数组元素是否有序，默认为true标识有序，当我们有元素交换的时候就把标识改成false。当一轮排序完成后，如果值为false，说明本轮排序完成前是无序的（也就是说此次排序有交换元素，本轮排序完成后有可能数组已经有序，所以我这里说是排序完成前）；如果值为true，意味着交换元素，说明本轮排序后数据已经有序了。

??优化版本运行结果如下：

--------------------3.2、优化版本-------------------------
要排序的初始化数据：[23, 8, 9, 10, 21, 39, 29, 30]
第【1】轮排序将准备比较【7】次
【23】与【8】进行交换后数组变成--> [8, 23, 9, 10, 21, 39, 29, 30]
【23】与【9】进行交换后数组变成--> [8, 9, 23, 10, 21, 39, 29, 30]
【23】与【10】进行交换后数组变成--> [8, 9, 10, 23, 21, 39, 29, 30]
【23】与【21】进行交换后数组变成--> [8, 9, 10, 21, 23, 39, 29, 30]
【39】与【29】进行交换后数组变成--> [8, 9, 10, 21, 23, 29, 39, 30]
【39】与【30】进行交换后数组变成--> [8, 9, 10, 21, 23, 29, 30, 39]
第【1】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【2】轮排序将准备比较【6】次
第【2】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【2】轮排序后跳出循环

??从运行结果来看，我们只需要两轮就完成了排序，并且少了很多不必要的比较次数。

3.3、综合版本

??这个版本又是怎么来的呢，我们先看一组要排序的数据，调用我们刚才的优化版本。假设我们需要排序的数组数据是：21, 10, 8, 9, 23, 29, 30, 39

    public static void main(String[] args) {
        log.info("---------------------3.3、优化版本------------------------");
        int[] arr4 = new int[]{21, 10, 8, 9, 23, 29, 30, 39};
        log.info("要排序的初始化数据：{}", arr4);
        //从小到大排序
        bubbleSortOptimize(arr4);
    }

??优化版本运行本次排序结果如下：

---------------------3.3、优化版本------------------------
要排序的初始化数据：[21, 10, 8, 9, 23, 29, 30, 39]
第【1】轮排序将准备比较【7】次
【21】与【10】进行交换后数组变成--> [10, 21, 8, 9, 23, 29, 30, 39]
【21】与【8】进行交换后数组变成--> [10, 8, 21, 9, 23, 29, 30, 39]
【21】与【9】进行交换后数组变成--> [10, 8, 9, 21, 23, 29, 30, 39]
第【1】轮排序后的结果：[10, 8, 9, 21, 23, 29, 30, 39]
第【2】轮排序将准备比较【6】次
【10】与【8】进行交换后数组变成--> [8, 10, 9, 21, 23, 29, 30, 39]
【10】与【9】进行交换后数组变成--> [8, 9, 10, 21, 23, 29, 30, 39]
第【2】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【3】轮排序将准备比较【5】次
第【3】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【3】轮排序后跳出循环

??从运行结果来看，首先我们的数组，后面几位是基本有序的，但是不管是第一轮还是，第二轮，还是第三轮，都要进行一次次的比较，显然是不必要的。我们优化版本是通过增加标志位记录交换位置，后续判断是否已有序，这里我们的综合版本也可以借鉴这个思路，同时把最后交换的位置也记下来，如果一轮排序下来，交换的位置之后的数据说明是不满足交换的条件的，也就是有序的，具体实现如下：

	/**
     * 冒泡排序(综合版本--数组中后面的数据有序)
     *
     * @param arr
     */
    public static void bubbleSortFinal(int[] arr) {
        // 数组的长度
        int len = arr.length;
        // 记录最后一次交换的位置
        int lastExchangeIndex = 0;
        // 无序数列的边界，每轮比较只需要比到这里就可以了
        int borderIndex = len - 1;
        // 遍历数组
        for (int i = 0; i < len - 1; i++) {
            // 有序标记，每一轮排序的初始值都是true
            boolean isOrderly = true;
            log.info("第【{}】轮排序将准备比较【{}】次", i + 1, borderIndex);
            for (int j = 0; j < borderIndex; j++) {
                // 从小到大排序,如果前一个元素【arr[j] 】比后一个元素【arr[j + 1]】大，则交换位置
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    // 有元素交换，所以不是有序，标记变为false
                    isOrderly = false;
                    // 记录一下最后一次元素交换的位置（说明arr[j]后面的元素已经有序，不用再比较了）
                    lastExchangeIndex = j;
                    log.info("【{}】与【{}】进行交换后数组变成--> {}", arr[j + 1], arr[j], arr);
                }
            }
            borderIndex = lastExchangeIndex;
            log.info("第【{}】轮排序后的结果：{}", i + 1, arr);
            // 如果没有交换,说明数组已经有序了,直接跳出大循环
            if (isOrderly) {
                log.info("第【{}】轮排序后跳出循环", i + 1);
                break;
            }
        }
    }

??综合版本运行本次排序结果如下：

---------------------3.3、综合版本------------------------
要排序的初始化数据：[21, 10, 8, 9, 23, 29, 30, 39]
第【1】轮排序将准备比较【7】次
【21】与【10】进行交换后数组变成--> [10, 21, 8, 9, 23, 29, 30, 39]
【21】与【8】进行交换后数组变成--> [10, 8, 21, 9, 23, 29, 30, 39]
【21】与【9】进行交换后数组变成--> [10, 8, 9, 21, 23, 29, 30, 39]
第【1】轮排序后最后的边界索引：2
第【1】轮排序后的结果：[10, 8, 9, 21, 23, 29, 30, 39]
第【2】轮排序将准备比较【2】次
【10】与【8】进行交换后数组变成--> [8, 10, 9, 21, 23, 29, 30, 39]
【10】与【9】进行交换后数组变成--> [8, 9, 10, 21, 23, 29, 30, 39]
第【2】轮排序后最后的边界索引：1
第【2】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【3】轮排序将准备比较【1】次
第【3】轮排序后最后的边界索引：1
第【3】轮排序后的结果：[8, 9, 10, 21, 23, 29, 30, 39]
第【3】轮排序后跳出循环

??从这个结果来看，我们的第一轮排序完记住了最后交换的边界索引，下次循环就是以此边界索引进行比较，从而减少了不必要的比较次数。如果数据很多并且经过几轮排序后，后面的数据已经是有序了，那么这个提升就会很大了。

优化版本	综合版本
第一轮比较 7 次	第一轮比较 7 次
第二轮比较 6 次	第二轮比较 2 次
第三轮比较 5 次	第三轮比较 1 次

总结

基础版本：通用版本，整个排列数据完全无序，处于散列状态
优化版本：通过增加布尔变量 isOrderly 作为标记，如果没有元素交换了，说明剩下的元素已经有序了，不用进行下一轮的排序，排序完成，优化不必要的比较轮次
综合版本：针对一轮排序的比较次数，具体是通过交换元素时记录下它的边界 borderIndex ，边界之前是无序的，边界之后是有序的，有序的那部分就可以不用再比较了，优化掉不必要的比较次数