1熟嫩、冒泡排序（Bubble Sort）
冒泡排序是一種簡單的排序算法蚓让。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素屉更，如果它們的順序錯誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換洒缀，也就是說該數(shù)列已經(jīng)排序完成瑰谜。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
1.1 算法描述
- 比較相鄰的元素树绩。如果第一個比第二個大萨脑，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作饺饭，從開始第一對到結(jié)尾的最后一對渤早，這樣在最后的元素應(yīng)該會是最大的數(shù)；
- 針對所有的元素重復(fù)以上的步驟瘫俊，除了最后一個鹊杖；
- 重復(fù)步驟1~3，直到排序完成扛芽。
1.2 動圖演示
冒泡排序
1.3 代碼實現(xiàn)
/**
* 冒泡排序
*
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
return array;
}
1.4 循環(huán)解讀
- 范例：32951
| 內(nèi)外層循環(huán)數(shù) | 內(nèi)層循環(huán)1 | 內(nèi)層循環(huán)2 | 內(nèi)層循環(huán)3 | 內(nèi)層循環(huán)4 | 備注 |
|---|---|---|---|---|---|
| 外層循環(huán)1 | 23951 | 23951 | 23591 | 23519 | 保證末位最大 |
| 外層循環(huán)2 | 23519 | 23519 | 23159 | 倒數(shù)第二位比末位小 | |
| 外層循環(huán)3 | 23159 | 21359 | 倒數(shù)第三位比后一位小 | ||
| 外層循環(huán)4 | 12359 | 倒數(shù)第四位比后一位小 |
1.5 算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(n2)
