冒泡排序( 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）
