冒泡排序及复杂度分析、进一步优化

问题：如何对一个数组进行排序比如 int a[] = {3,4,5,2,1,6,0}

冒泡排序算法的思路：每次将相邻两个数比较大小，如果第一个数比第二个数大，就交换他们两个，也就是把其中较大的数交换到右边，这样一趟比较下来，最右边的元素就是这个数组中最大的数了；再对剩下的n-1个数继续这样比较，找到数组中第二个大的数……

java代码的实现：

public void bubbleSort(Int[] a){
    for(int i = 0;i<a.length-1;i++){     //外层循环控制比较的趟数n-1
        for(int j = 0;j<a.length-1-i;j++){     //内部循环控制每趟比较的次数n-i
            if(a[j]>a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

最佳情况时间复杂度：
正序的数组，比较n(n-1)/2次，交换0次，所以时间复杂度为：O(n^2)
最差情况时间复杂度：
反序的数组，比较n(n-1)/2次，交换3n(n-1)/2次，所以时间复杂度为：O(n^2)
平均时间复杂度：O(n^2)
稳定性：相同的元素不会交换位置，算是一种比较稳定的排序算法。

进一步优化：由于正序的数组比较一趟下来就已经拍好序了，所以可以设置一个标志位，来避免不必要的循环：

public void bubbleSort(int[] a) {
       for(int i=0;i<a.length-1;i++){
           boolean flag = true;
           for(int j=0;j<a.length-1-i;j++){
               if(a[j]>a[j+1]){
                   int temp=a[j];
                   a[j]=a[j+1];
                   a[j+1]=temp;
                   flag = false;
               }
           }
           if(flag)
               break;
       }    
   }

优化之后，佳情况时间复杂度：
正序的数组，比较n-1次，交换0次，所以时间复杂度为：O(n)