Java算法总结之冒泡排序（详解）

        冒泡排序（默认升序）

算法原理：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，每一轮最后的元素应该会是最大的数。 

代码示例：

/**
 * 基本原理
 * @param 整型数组arr
 * @return 整型数组arr
*/
public int[] BubbleSortBasic(int[] arr){
        for(int i = 0;i < arr.length;i++){//排序所需的趟数
            for(int j = 0;j < arr.length - 1 - i;j++){//每趟比较次数
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"次排序："+Arrays.toString(arr));
        }
        
        return arr;
}

运行结果：

从运行结果可以看出，14个数字，需要进行14次排序操作才可以得到最后的结果，但是在第8次已经得到最后的结果，后面运行的排序都是可以省略的。

优化一下代码：

/**
 * 优化
 * @param 整型数组arr
 * @return 整型数组arr
* boolean flag  优化，检查每一趟之后是否有序
*/
public int[] BubbleSortOptimize(int[] arr){
        for(int i = 0;i < arr.length;i++){//排序所需的趟数
            
            boolean flag = false;
            for(int j = 0;j < arr.length - 1 - i;j++){//每趟比较次数
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            System.out.println("第"+(i+1)+"次排序："+Arrays.toString(arr));
            if(flag == false){//如果已经有序，则返回排序后的数组
                break;
            }
        }
        
        return arr;
}

运行结果：

从运行结果可以看出，14个数字，需要进行9次排序操作才可以得到最后的结果，但是在第8次已经得到最后的结果，第9次排序是因为需要检验前面的排序也没有得到正确的排序结果。

优化后的排序算法，减少遍历次数，更加高效，建议使用。