优化冒泡排序

问题：
给定一个整型数组, 实现冒泡排序 (升序排序)

一般我们写出来的是这个代码：

public static void bubbleSort(int[] array) {
        for(int i = 0;i < array.length -1;i++) {
            if(array[i] > array[i+1]) {
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {6,8,13,2,9};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

这个代码呢，不能说他错，但是呢大家都会写，在面试的时候就体现不出来自己的优势，所以我们需要对这个代码进行优化：

1、第一轮的判断将整个数组的最大值放在了最后面，第二轮的判断是将除过第一次选出的最大值以外的剩余数字中的最大值放在了倒数第二位，我们已经知道从后往前是从大到小的顺序已经排好，所以我们没必要每次都进行最后一个数字和前一个数字的比较，我们可以再加个循环，用来减少判断每次后面已经排好的顺序，只进行前面数字的比较排序即可。

第3趟：

第4趟：

2、我们需要判断数组是否已经排好序，防止重复比较
分为两种：一就是给定的数组本身就是有序的，二就是数组在排序的过程中就已排好

下面给出我们优化后的代码：

public static void bubbleSort(int[] array) {
        for(int i = 0;i < array.length -1;i++) {
            boolean flg = true;//标记
            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;
                    flg = false;
                }
            }
            if(flg == true) {
                break; // 说明给定的数组是排好序的数组
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {6,8,13,2,9};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

运行结果：