冒泡算法及优化方案

冒泡算法，就是比较两个相邻的元素的大小，根据比较结果进行交换，一直比较到最后一个元素，此时经过一轮比较交换，最后一个元素应该为最大或者最小值。然后再次比较一轮，这次只比较到倒数第二个元素，如此往复，一直比较到第一个元素。

常规写法

    public void maopao1(int[]arr){
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 1; j <= i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }

优化写法1

记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；

    public void maopao2(int[]arr){
        boolean swaped = true;
        for (int i = 0; i < arr.length; i++) {
            if(!swaped){
                break;
            }
            swaped = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j +1] < arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaped = true;
                }
            }
        }
    }

一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
经过优化的写法：

优化写法3

除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

    public void maopao3(int[]arr){
        boolean swaped = true;
        int swapedIndex = -1;
        int lastSwapedIndex = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            if(!swaped){
                break;
            }
            swaped = false;
            for (int j = 0; j < lastSwapedIndex; j++) {
                if (arr[j + 1] < arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaped = true;
                    swapedIndex = j;
                }
            }
            lastSwapedIndex = swapedIndex;

        }
    }