冒泡排序的优化

原始的冒泡排序相对而言是非常耗时的，即使一个数组经过几轮交换已经变的有序了，例如 [2,1,3,4,5,6,7] 这个数组，经过第一轮，已经变成有序的了，但顽固的冒泡还是要继续进行没有营养的两两比较，从而牺牲了时间。

//冒泡排序
    public void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=arr.length-1;j>i;j--){
                if(arr[j]<arr[j-1]){
                    int tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                }
            }
        }
    }

冒泡排序的算法优化

如果用一个flag来判断一下，当前数组是否已经有序，如果有序就退出循环，这样可以明显的提高冒泡排序的表现

由于冒泡排序的时间复杂度为 O(n²) 所以当数据越多的时候，越慢，非常不适合大数据的排序。

对于上面的序列我们发现，含有10个元素的序列需要45次比较（第一趟9次，第二趟8次，第三趟7次，....... ，第九趟1次），那么真的需要45次吗？对于下面的这种序列{1,2,4,5,8,9,10,14,15,13}，使用上面的算法也是45次，但观察发现该序列大部分是有序的，第一趟将15沉底放置最后，得到{1,2,4,5,8,9,10,14,13,15}，第二趟将14沉底放置最后，得到{1,2,4,5,8,9,10,13,14,15}，从第三趟到最后一趟都无需再移动，所以那些比较都是徒劳的，因此，我们对上述算法进行如下优化，减少算法的比较次数。优化的方法就是加一个标志位，记录本趟比较是否发生交换，下一趟根据这个标志位，若上一次没有交换，则本趟比较无需进行。

    //冒泡排序的改良版
    public void bubbleSort_plus(int[] arr){
        boolean flag=true;
        for(int i=0;i<arr.length-1&&flag;i++){
            flag=false;
            for(int j=arr.length-1;j>i;j--){
                if(arr[j]<arr[j-1]){
                    flag=true;
                    int tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                }
            }
        }
    }

总体来说，冒泡排序的效率是较为低下的，在数据量小的情况下可以使用，否则应该选择其他的排序算法。