冒泡排序

冒泡排序( Bubble Sort) 一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

图1 冒泡排序

冒泡排序流程如图1所示：
假设有一个无序序列 {1, 4 , 6, 0, 3, 2, 5, 9}
从9开始两两比较，数字较小的上浮。
第一轮：2比3小，2上浮；0比前面的数字都小，上浮到第一位；
第二轮：2比6，4小，上浮到4的上方；
第三轮：3上浮到4上方；
第四轮：5上浮到6上方。
代码实现：

//冒泡排序
private static int[] bubbleSort(int[] a) {
    for(int i=0; i<a.length; i++) {
        for(int j=a.length-1; j>i; j--) {
            int temp;
            if(a[j]<a[j-1]) {
                temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
    return a;
}

public static void main(String[] args) {
    int[] a = {1, 4 , 6, 0, 3, 2, 5, 9};
    int[] b = bubbleSort(a);
    System.out.print("Bubble sort:\n");
    for(int i=0; i<a.length; i++) {
        System.out.print(b[i] + ", ");
    }
}

输出结果：
Bubble sort:
0, 1, 2, 3, 4, 5, 6, 9,

优化：

这样的冒泡排序并非最优。举个例子，对于无序数组{1,2,3,4,5,0}, 只需要一轮冒泡排序就可以得到从小到大的数组。如果按照上述的代码，需要执行n轮比较。其实除了第一轮比较是有用的，其他的比较都多余。因此我们可以加一个flag来实现对算法改进。

private  static  boolean flag;
//冒泡排序
private static int[] bubbleSort(int[] a) {
    for(int i=0; i<a.length; i++) {
        flag = true;
        for(int j=a.length-1; j>i; j--) {
            int temp;
            if(a[j]<a[j-1]) {
                temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
                flag = false;
            }
        }

        if (flag) {
            break;
        }
    }
    return a;
}

冒泡排序的时间复杂度O（n^2）