冒泡排序( Bubble Sort) 一種交換排序砾嫉，它的基本思想是：兩兩比較相鄰記錄的關鍵字幼苛，如果反序則交換，直到?jīng)]有反序的記錄為止焕刮。
圖1 冒泡排序
冒泡排序流程如圖1所示：
假設有一個無序序列 {1, 4 , 6, 0, 3, 2, 5, 9}
從9開始兩兩比較舶沿，數(shù)字較小的上浮墙杯。
第一輪：2比3小，2上咐ǖ础高镐；0比前面的數(shù)字都小，上浮到第一位畸冲；
第二輪：2比6嫉髓，4小，上浮到4的上方邑闲；
第三輪：3上浮到4上方算行；
第四輪：5上浮到6上方。
代碼實現(xiàn)：
//冒泡排序
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,
優(yōu)化：
這樣的冒泡排序并非最優(yōu)苫耸。舉個例子州邢，對于無序數(shù)組{1,2,3,4,5,0}, 只需要一輪冒泡排序就可以得到從小到大的數(shù)組。如果按照上述的代碼褪子，需要執(zhí)行n輪比較量淌。其實除了第一輪比較是有用的，其他的比較都多余嫌褪。因此我們可以加一個flag來實現(xiàn)對算法改進呀枢。
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）
