《数据结构与算法之冒泡排序（Java实现）》

云丶言 2021-05-28

171

说在前头：本人为大二在读学生，书写文章的目的是为了对自己掌握的知识和技术进行一定的记录，同时乐于与大家一起分享，因本人资历尚浅，能力有限，文章难免存在一些错漏之处，还请阅读此文章的大牛们见谅与斧正。若在阅读时有任何的问题，也可通过评论提出，本人将根据自身能力对问题进行一定的解答。

前言

—

冒泡排序算法的时间复杂度为O(N2)，效率很低，并不适合实际的开发，但算法实现十分简单，适合对算法入门的小伙伴们研究。

—

算法思想

对所有未排序好的数据，自左而右进行多轮对比，相邻的两个数，如果左边的数大于右边的数，两个数位置进行互换，一轮互换后最右边的数认为是最大的数，将该数据“下沉”，下沉后的数据不进行下一轮的对比，一直往复，直到所有待排序的数据只剩下一个数据时，认为数组内的数据已完成排序。（具体流程如下图）

—

具体实现代码

Bubbling.java

package com.bosen.bubbling;


/**
 * <p>冒泡算法</p>
 * @author Bosen 2021/5/26 14:18
 */
public class Bubbling {
    /*
     * 待排序的数组
     */
    private int[] array;


    public Bubbling(int[] array) {
        this.array = array;
    }


    /*
     * 执行冒泡排序
     */
    public void sort() {
        int length = array.length;
        int temp;
        for (int i=0; i<length-1; i++) {
            for (int j=1; j<length; j++) {
                // 左边的数大于右边的数，两个数据位置需进行替换
                if (array[j-1] > array[j]) {
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }
            }
            System.out.print("第"+(i+1)+"轮的排序结果：");
            display();
        }
    }
    
    /*
     * 打印每轮排序信息
     */
    public void display() {
        for (int i : array) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }
}

Test.java

package com.bosen.bubbling;


/**
 * <p>测试类</p>
 * @author Bosen 2021/5/26 14:35
 */
public class Test {
    public static void main(String[] args) {
        Bubbling bubbling = new Bubbling(new int[]{5, 7, 4, 9, 11, 10, 3});
        bubbling.sort();
    }
}

输出结果

—

冒泡算法的缺陷

冒泡算法存在一个很大的缺陷，如果我们存入一个已经排列好的数组给冒泡算法，算法仍然会执行六次对比，如下图输入信息：

这一点是很不合理的，当我们的数组已经排序完毕后，算法就应该停止计算，下面我们探讨下该缺陷的解决方案。

—

冒泡算法优化

要对冒泡算法进行优化，首先我们需要知道在冒泡算法运行的过程中，如何判断数组已经完成了排序，从而停止算法的运行。从上面讲述冒泡原理中我们不难得知，当数组中的数据没有发生数据位置交换的情况时，我们就可以认为，数组已经完成排序。所以，我们只需要判断每一轮对比时有没有发生数据位置的交换就可以知道数据是否已经完成排序。

为此，我们可以增加一个用于判断的布尔类型变量flag，具体优化代码如下

    /*
     * 执行冒泡排序
     */
    public void sort() {
        int length = array.length;
        int temp;
        System.out.print("初始状态：\t");
        display();
        for (int i=0; i<length-1; i++) {
            boolean flag = true;
            for (int j=1; j<length; j++) {
                // 左边的数大于右边的数，两个数据位置需进行替换
                if (array[j-1] > array[j]) {
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                    flag = false;
                }
            }
            if (flag) break;
            System.out.print("第"+(i+1)+"轮的排序结果：");
            display();
        }
    }

输出结果：

因为初始状态是已经排好序的数组，所以并不会进行任何一轮的对比，到这里，我们已经对冒泡排序完成了优化。

总结

—

此篇文章，向大家介绍了冒泡排序算法的基本算法思想，具体代码实现示例，指出了冒泡排序算法的不足之处，并通过具体方案进行算法优化。

👇长按二维码关注

java

文章转载自云丶言，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。