2018-06-13 冒泡排序

冒泡排序
两个for循环 先--后++；
n-1 ~ 1
1~ i (从头到尾逐个比较，注意数组不要溢出)

时间复杂度：
当i=n-1时, 执行n-1次循环
当i=n-2时, 执行n-2次循环
....
....
当i=1时, 执行1次循环
总循环次数为 1+2+3+...+(n-2)+(n-1)=(n-1 +1)*(n-1)/2=n(n-1)/2;

    public static void BubbleSort(int[] a){
        int n = a.length;
        int flag =1;
        int temp;
        // 总共n-1趟排序（n个数，只要n-1个是有序的那这个数组就是有序的）
        for(int i=n-1; i>=1; i-- ){
       //每次从0到i(没有用n-1,因为此时后面已经有序的不需要再比较了)
       //每执行一次大循环，则最后一个数字所在的位置是正确的，后面的比较不需要再计算这些数字了
            for(int j=1; j<=i; j++){
                if(a[j-1] >a[j]){
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                    flag =0;
                }
            }
            if(flag ==1){
                //说明数组是有序的直接退出
                return;
            }
        }
    }