更快，更好的冒泡排序

冒泡排序优化

// 冒泡排序的基本实现
class Main {
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        // i用于记录已经放好的最大值数组
        for(int i = 0; i < len-1; i++) {
            // 用于向后冒泡，依次交换大值
            for(int j = 0; j < len - i - 1; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j+1);
                }
            }
        }
        return;
    }
    
    public static void swap(int[] arr, int n, int m) {
        int temp = arr[n];
        arr[n] = arr[m];
        arr[m] = temp;
    }
}

基本的冒泡在思路上很好理解，但仍然有一些笨拙：

如果一个数组已经基本有序：[ 1，3，2，4，5，6 ] ，那么在发生少数几次交换后，数组就已经有序，此时没必要继续遍历排序

优化一：如果一次遍历中，没有发生交换，说明数组已经有序，结束排序

// 冒泡排序：优化一
class Main {
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        // flag 用于判断是否发生了交换
        boolean flag;
        // i用于记录已经放好的最大值数组
        for(int i = 0; i < len-1; i++) {
            flag = true；
            // 用于向后冒泡，依次交换大值
            for(int j = 0; j < len - i - 1; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j+1);
                    // 发生交换，不可跳出
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
        return;
    }
    
    public static void swap(int[] arr, int n, int m) {
        int temp = arr[n];
        arr[n] = arr[m];
        arr[m] = temp;
    }
}

又如果数组并不是基本有序，而是后半段有序：[ 4，3，2，1，5，6，7，8，9 ]，冒泡排序遍历后半段的遍历也是没必要的

试想一下，某次冒泡排序后，第五个数字后直到结尾都没有发生交换，是否就是说明第五个数之后的数组已经是有序的

优化二：记录最后的比较位置，之后视为有序

// 冒泡排序：优化二
class Main {
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        // flag 用于判断是否发生了交换
        boolean flag;
        // lastChange 用于记录最后一个无序地址（之后为有序）
        int lastChange = len - 1;
        // i用于记录已经放好的最大值数组
        for(int i = 0; i < len; i++) {
            flag = true;
            // midChange 用于暂时记录每一轮的最后交换地址
            int midChange = 0;
            // 用于向后冒泡，依次交换大值
            for(int j = 0; j < lastChange; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j+1);
                    // 发生交换，不可跳出
                    flag = false;
                    midChange = j;
                }
            }
            if(flag) {
                break;
            }
            // 记住最后交换地址，修改遍历范围
            midChange = lastChange;
        }
        return;
    }
    
    public static void swap(int[] arr, int n, int m) {
        int temp = arr[n];
        arr[n] = arr[m];
        arr[m] = temp;
    }
}