一起学排序算法 - 冒泡排序

2021-11-30 10:09:09  晓掌柜  版权声明：本文为站长原创文章，转载请写明出处

一、什么是冒泡排序

    1.1、文字描述

        冒泡排序是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复的进行直到没有再需要交换，这是也就说明排序已经完成。因为越大的元素会经由交换慢慢‘浮‘到数列的顶端，所以命名为冒泡算法排序。

    1.2、程序描述

        定义一个变量 i = 0，最大值为数列的长度 - 1 , i 与 i + 1 进行比较，如果 i > i + 1 则进行交换。随着 i 的不断增加，直到 i 达到数列长度 - 1。

    附动态图：

二、简单的代码展示    

    我们先进行最基础的操作，依次进行比对。

    PS： 这样会产生一些无效操作，后面我们再进行优化...

    
    public static void main(String[] args) {

        int handleTimes = 0;
        /* 定义一个简单的乱序数组 */
        int[] intArr = {2,4,1,5,6,3,7};
        for (int i = 0;i < intArr.length; i++) {
            /* 开启双重循环 */
            for (int j = 0; j < intArr.length - i - 1; j++) {
                /* 拿到当前操作的数据和下一个进行比较 */
                if (intArr[j] > intArr[j + 1]) {
                    /* 我们按照从小到大排序，如果当前的大于下一个数据则两个数据互换 */
                    int temp = intArr[j];
                    intArr[j] = intArr[j+1];
                    intArr[j+1] = temp;
                }
            }
            System.out.println("第" + handleTimes + "次排序" + CollectionUtils.arrayToList(intArr));
            handleTimes++;
        }
        System.out.println(handleTimes);
        System.out.println(CollectionUtils.arrayToList(intArr));
    }

    输出如下：

三、代码优化    

    通过上面的代码我们可以看到一共进行了7次排序，但是从第四次开始已经是完成了的，后面的都是无效操作。所以我们对代码进行了如下优化：

    ① 定义一个排序生效字段 isChanged，当排序进行时我们使其修改为true

    ② 每次大循环时我们都初始isChengerd为false，当每次大循环结束时，如果isChanged还是false，则进行已经没有进行排序了

    public static void main(String[] args) {

        int handleTimes = 0;
        boolean isChangerd = false;
        /* 定义一个简单的乱序数组 */
        int[] intArr = {2,4,1,5,6,3,7};
        for (int i = 0;i < intArr.length; i++) {
            isChangerd = false;
            /* 开启双重循环 */
            for (int j = 0; j < intArr.length - i - 1; j++) {
                /* 拿到当前操作的数据和下一个进行比较 */
                if (intArr[j] > intArr[j + 1]) {
                    /* 我们按照从小到大排序，如果当前的大于下一个数据则两个数据互换 */
                    int temp = intArr[j];
                    intArr[j] = intArr[j+1];
                    intArr[j+1] = temp;
                    /* 这里定义一个中间变量进行操作 */
                    isChangerd = true;
                }
            }
            System.out.println("第" + handleTimes + "次排序" + CollectionUtils.arrayToList(intArr));
            /* 如果这里如果上面的操作没有交换则说明排序已经完成 */
            if (!isChangerd) {
                break;
            }
            handleTimes++;
        }
        System.out.println(CollectionUtils.arrayToList(intArr));
    }

    输出如下：