一、基本介绍

**冒泡排序（Bubble Sorting）的基本思想是：**通过对待排序序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

二、优化前的代码

package cn.zzw.algorithm.sort1;

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {

        int[] array={9,8,3,6,5,4};
        BubbleSort(array);

    }

    public static void BubbleSort(int array[])
    {
        for (int i = 0; i < array.length-1; i++)
        {
            for(int j=0;j<array.length-1-i;j++)
            {
                if(array[j]>array[j+1])
                {
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            System.out.println("第"+(i+1)+"趟排序结果为：");
            System.out.println(Arrays.toString(array));
        }

        System.out.println("=====================");
        System.out.println("最终的排序的结果为"+ Arrays.toString(array));
    }

}

测试结果：

"C:\Program Files\Java\jdk1.8.0_181\bin\java.exe" "-javaagent:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\lib\idea_rt.jar=20309:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_181\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\rt.jar;C:\Users\1\IdeaProjects\algorithm\out\production\algorithm" cn.zzw.algorithm.sort1.BubbleSort
第1趟排序结果为：
[8, 3, 6, 5, 4, 9]
第2趟排序结果为：
[3, 6, 5, 4, 8, 9]
第3趟排序结果为：
[3, 5, 4, 6, 8, 9]
第4趟排序结果为：
[3, 4, 5, 6, 8, 9]
第5趟排序结果为：
[3, 4, 5, 6, 8, 9]
=====================
最终的排序的结果为[3, 4, 5, 6, 8, 9]

Process finished with exit code 0

三、冒泡排序算法的优化

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在 排序过程中设置一个标志 flag 判断元素是否进行过交换，从而减少不必要的比较。

如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序，这个就是优化。

四、优化后的代码

package cn.zzw.algorithm.sort1;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class BubbleSort {

    public static void main(String[] args) {

        int[] array={9,8,3,6,5,4};
        BubbleSort(array);

        /*
        测试80000个数据冒泡排序所用的时间
        int[] arr=new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i]=(int)(Math.random()*800000);
        }

        Date date1=new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format1 = simpleDateFormat.format(date1);
        System.out.println("排序前的时间是："+format1);

        BubbleSort(arr);

        Date date2=new Date();
        String format2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间是："+format2);
        
         */

    }

    public static void BubbleSort(int array[])
    {
        boolean flag=false;
        for (int i = 0; i < array.length-1; i++)
        {
            for(int j=0;j<array.length-1-i;j++)
            {
                if(array[j]>array[j+1])
                {
                    flag=true;
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }

            if(!flag)
            {
                break;
            }
            else
            {
                flag=false;
            }
            System.out.println("第"+(i+1)+"趟排序结果为：");
            System.out.println(Arrays.toString(array));
        }

        System.out.println("=====================");
        System.out.println("最终的排序的结果为"+ Arrays.toString(array));
    }

}

测试结果：

"C:\Program Files\Java\jdk1.8.0_181\bin\java.exe" "-javaagent:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\lib\idea_rt.jar=22975:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_181\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\rt.jar;C:\Users\1\IdeaProjects\algorithm\out\production\algorithm" cn.zzw.algorithm.sort1.BubbleSort
第1趟排序结果为：
[8, 3, 6, 5, 4, 9]
第2趟排序结果为：
[3, 6, 5, 4, 8, 9]
第3趟排序结果为：
[3, 5, 4, 6, 8, 9]
第4趟排序结果为：
[3, 4, 5, 6, 8, 9]
=====================
最终的排序的结果为[3, 4, 5, 6, 8, 9]

Process finished with exit code 0

排序前的时间是：2021-02-08 22:16:31
排序前的时间是：2021-02-08 22:16:45