算法描述:
1.臨近的數(shù)字兩兩進(jìn)行比較,按照從小到大順序進(jìn)行交換,直到到達(dá)有序區(qū)域挺尿。
2.如果未排序區(qū)域非空，重復(fù)步驟1。
舉個(gè)例子：以下是{5, 1, 12, -5, 16}的排序過(guò)程
排序過(guò)程
PS：博主還發(fā)現(xiàn)了一個(gè)非常好的算法可視化過(guò)程示例，請(qǐng)見(jiàn)1.
復(fù)雜度分析
時(shí)間：最優(yōu)平均和最差都是O(n2)
空間：O(1).
是穩(wěn)定的排序算法凯力。
在前文的描述中，可以看到對(duì)于已經(jīng)排序的數(shù)列而言礼华，即最優(yōu)情況下咐鹤，O(n2)次的比較是不必要的。如果在某趟遍歷過(guò)程中并沒(méi)有發(fā)生任何的交換圣絮，則可以認(rèn)為數(shù)列已經(jīng)有序祈惶，程序可以終止。查看優(yōu)化后的冒泡排序代碼請(qǐng)參考2扮匠。
冒泡排序代碼(未優(yōu)化)
public void bubbleSort(int[] arr) {
int temp;
for (int j = arr.length - 1; j > 0; j--) {
for (int i = 0; i < j; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
冒泡排序代碼(優(yōu)化)
public void bubbleSort( int [] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
