1.1 原理
??這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）站故，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣皆怕，故名“冒泡排序”。
??1. 比較相鄰的元素西篓。如果第一個(gè)比第二個(gè)大愈腾，就交換他們兩個(gè)。
??2. 對(duì)每一對(duì)相鄰元素做同樣的工作岂津，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)虱黄。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)吮成。
??3. 針對(duì)所有的元素重復(fù)以上的步驟橱乱，除了最后一個(gè)。
??4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟粱甫，直到?jīng)]有任何一對(duì)數(shù)字需要比較泳叠。
image.png
1.2 代碼
private static void sort(int[] array) throws Exception {
if (array == null || array.length == 0) {
throw new Exception("the array is null or no element...");
}
System.out.println("冒泡排序優(yōu)化前...");
int n = array.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
System.out.println("第" + (i + 1) + "輪后: " + Arrays.toString(array));
}
}
第1輪后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
第2輪后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
第3輪后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
第4輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第5輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第6輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第7輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第8輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
第9輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
??從上述的log打印中，可以看出來(lái)：在第4輪時(shí)就已經(jīng)排好序了魔种，所以從第5輪到第9輪均是無(wú)用操作析二。
private static void optimizeSort(int[] array) throws Exception {
if (array == null || array.length == 0) {
throw new Exception("the array is null or no element...");
}
System.out.println("冒泡排序優(yōu)化后...");
int n = array.length;
for (int i = 0; i < n; i++) {
// 設(shè)定一個(gè)排序完成的標(biāo)記
// 若為 true，則表示此次循環(huán)沒(méi)有進(jìn)行交換节预，即待排序列已經(jīng)有序叶摄，排序已然完成
boolean success = true;
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
success = false;
}
}
if (success) {
break;
}
System.out.println("第" + (i + 1) + "輪后: " + Arrays.toString(array));
}
}
第1輪后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
第2輪后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
第3輪后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
第4輪后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
1.3 復(fù)雜度
- 時(shí)間復(fù)雜度：
兩層循環(huán)，第1次遍歷n次(n個(gè)元素)安拟，第二次遍歷n-1次蛤吓，... 依次類(lèi)推。因此糠赦，表達(dá)式如下：
- 空間復(fù)雜度：
沒(méi)有利用新的數(shù)組來(lái)幫助完成排序算法会傲，我們認(rèn)為其空間復(fù)雜度為
