冒泡排序及其改进

    public static void bubbleSort(int[] arr) {
        
        int temp = 0;
        
        for(int i = 0; i < arr.length; i++) {    //每次排一个，排arr.length次
            for(int j = 0; j < arr.length -1 - i; j++) {    //每次排好，跟剩下的 ***arr.length-1-i*** 个数排
                if(arr[j] > arr[j + 1]) {    //相邻交换，if中决定大的或小的放后面
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }       
    }
    
    public static void bubbleSort_isSorted(int[] arr) {    //设置标志位isSorted，如一轮没发生交换，则证明已有序
        
        boolean isSorted = false;
        int temp = 0;
        
        for(int i = 0; i < arr.length; i++) {
            isSorted = true;
            for(int j = 0; j < arr.length - 1 - i; j++) {    
                if(arr[j] > arr[j + 1]) {   
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    isSorted = false;
                }
            }
            if(isSorted) {
                break;
            }
        }       
    }
    
    public static void bubbleSort_boundary(int[] arr) {    //增加有序边界
        
        boolean isSorted = false;
        int temp = 0;
        
        //int left = 0;无法确定左边是否有序，交换后小的在左，但不确定是否比前面的小。
        int lastChangeIndex = 0;
        int right = arr.length - 1;
        
        for(int i = 0; i < arr.length; i++) {
            isSorted = true;
            for(int j = 0; j < right; j++) {    
                if(arr[j] > arr[j + 1]) {   
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    
                    isSorted = false;
                    lastChangeIndex = j + 1;
                }
            }
            right = lastChangeIndex;    //每一轮后，才确定边界。
            if(isSorted) {
                break;
            }
        }       
    }