冒泡排序----深刻理解版本

前面虽然向大家介绍了冒泡排序，但是表达的不是很清楚，这次我带着更深刻的理解向大家介绍以下冒泡排序。

1.冒泡排序

冒泡排序其实是一种排序算法，通过数据之间的相互比较将一堆混乱的数据按照升序或者降序的顺序排列。

2.解题思路

解题思路依然不变，我们首先确立要比较的趟数，和一趟要比较的次数。

第一趟比较（红色部分）

第二趟比较（绿色部分）

第三趟比较（蓝色部分）

第四趟比较

如上图所示，假设我们有五个数据要进行排序，我们要进行4趟排序，第一趟排序要进行比较4次，第二趟排序要比较3次，第三趟排序要比较2次，第四趟排序要进行比较1次。

所以我么得出结论：n个数据要进行排序时，要进行n-1趟排序。这里的趟数也是已经排序好数据的个数。 

代码实现

public class MySort {
    public static void Bubble(int[] arr){
        //确立趟数
        int i=0;
        for(i=0;i< arr.length-1;i++){
            //一趟要比较的次数
            for(int j=0;j< arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr=new int[]{10,8,6,9,3};
        System.out.print("排序前：");
        for(int j:arr){
            System.out.print(j+" ");
        }
        System.out.println();
        Bubble(arr);
        System.out.print("排序后：");
        for(int x:arr){
            System.out.print(x+" ");
        }
    }
}

这里我要介绍以下我更加深刻理解冒泡排序的一点，就是第二个for循环确定一趟要比较的次数，

其实上面是一种已经优化的版本了，未优化的版本循环条件为 j<arr.length-1，在这种情况下，就意味着我们不论是进行哪一趟排序，在这一趟排序循环里面，它都会和所有的数据进行比较。不管之前经过排序就已经排序好的数据。

当我们写成 j<arr.length-1-i时，这里的i代表第几趟排序，经过i趟排序，就表示原本的数据中已经有i个数据已经排序好了，也就是说i也代表排序好的数据，接着我们进行下一趟排序时，这一趟要排序的数据就不会和已经排序好的数据进行比较了，这要就提高的效率。

运行代码，如下图所示

但这还不是更好的优化版本。

先假设我们一开始的数据为10  3  6  8  9。

这时我们只进行一次比较就已经将数据排序好了，但是按照上面的写法，后面还是会进行后面比较的趟数，所以我们可以设计一个标志来确定在某一趟排序的时候，数据是否已经完全排序好了。

优化代码实现

public class MySort {
    public static void Bubble(int[] arr){
        //确立趟数
        int i=0;
        for(i=0;i< arr.length-1;i++){
            boolean flag=true;//标记
            //一趟要比较的次数
            for(int j=0;j< arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    flag=false;
                }
            }
            if(flag==true){
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr=new int[]{10,8,6,9,3};
        System.out.print("排序前：");
        for(int j:arr){
            System.out.print(j+" ");
        }
        System.out.println();
        Bubble(arr);
        System.out.print("排序后：");
        for(int x:arr){
            System.out.print(x+" ");
        }
    }
}

我们设置了一个flag变量，一开始为true，如果有 没排序好的数据就会进入循环，将flag的值变为false，进行完这一趟的排序，就又进行下一趟排序，然后在来确定有无 没排序好的数据，如果没有，就不会进入第二个循环，最终flag的值为true。这时我们根据flag的值为true，就知道此时数据已经完全排序好了。