常见排序算法之冒泡排序

文章目录

• ​​1、概述​​
• ​​2、传统代码​​
• ​​3、优化后代码​​
• ​​4、测试案例​​

1、概述

冒泡排序（Bubble Sort），是一种的较简单且常见的的排序算法。

它重复地访问排序的元素列，依次比较两个相邻的元素，如果顺序不符合要求就把他们进行交换。访问元素的工作是重复地进行，当没有相邻元素需要交换时，说明该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

2、传统代码

核心思想：我们每一次的排序只是为了得到一个最大值，并且放到末尾。然后再将剩下的数据进行排序，注意此时末尾的已经确定的值不需要再进行比较排序。即比较次数为：( n-1 ) + ( n-2 ) + ( n-3 ) + …

从小到达的排序测试代码：

public class BubbleSortTest01 {
    public static void main(String[] args) {
        int[] arr = {1,1, 2, 2, 25, 23, 5};

        int tem;
        //1.进行数组长度-1次排序（最后只剩一个数字时就不需要排序）
        for (int i = 0; i < arr.length - 1; i++) {
            //2.每排一次序，最大的一个数字就会被确定，所以比较的次数依次减少
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //3.拿前一个数字直接和下一个数字进行比较，然后确定是否需要互换数值
                if (arr[j] > arr[j + 1]) {
                    tem = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tem;
                }
            }
            System.out.println("第"+i+"次排序：");
            System.out.println(Arrays.toString(arr));
        }
    }
}

3、优化后代码

传统的比较方法容易有一个弊端，假设我们传入的数组本身就是一个有序的数组，但是有序数组依然会执行相应的比较逻辑。我们可以利用标志位来解决这个问题

public class BubbleSortTest02 {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 25, 23, -5};
        int tem;
        //1.设置一个标志位，用于判断本次遍历过程，是否进行了交换顺序
        boolean flag;
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    //2.如果进行了排序，就修改对应的标志位
                    flag = true;
                    tem = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tem;
                }

            }

            //3.如果一次循环种没有进行交换，那就直接返回
            if (flag == false) {
                System.out.println("结束");
                return;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

4、测试案例

利用我们以有的条件，进行一个小案例的测试：计算将数组长度为80000的乱序数组排序所花费的时间

package pers.mobian.maopao;

import java.util.Arrays;

public class BubbleSortTest03 {
    public static void main(String[] args) {
        //1.创建一个大小为80000的随机数数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        //2.将数组进行冒泡排序
        bubbleSort(arr);
        long end = System.currentTimeMillis();

        //3.打印花费的时间
        System.out.println("冒泡排序花费的时间为：" + (end - start));

    }
    //将冒泡排序封装成一个方法
    public static void bubbleSort(int[] arr) {
        int tem;
        boolean flag;
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;

            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    tem = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tem;
                }
            }
            if (flag == false) {
                return;
            }
        }
    }
}