基本思想
兩個數(shù)比較大小峭状，大數(shù)上浮克滴，小數(shù)下沉优床！因為跟水開了的時候那個狀態(tài)相似劝赔，所以簡稱冒泡！
簡單來說就是這樣：比如有兩個數(shù)a和b胆敞，如果a>b着帽，就將a和b的位置互換。
最直接寫法
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
上面的寫法也是最簡單最直接的移层，兩層for循環(huán)就可以將數(shù)組排好序仍翰。但是對于一些極端情況并沒有考慮進(jìn)去幽钢，比如有這樣一個數(shù)組 int[] array = {1, 2, 3, 4, 5, 6, 8, 7}; 歉备，第一趟就可以將數(shù)組排好序，那么后續(xù)的步驟就完全不用再執(zhí)行了匪燕，為了節(jié)省算法的執(zhí)行時間蕾羊，可以使用一個狀態(tài)位來標(biāo)記數(shù)組是否已經(jīng)排好序喧笔，只要可以判斷出數(shù)組已經(jīng)排好序了，那么后續(xù)的遍歷就完全不用了龟再。所以就有了下面的優(yōu)化寫法书闸。
優(yōu)化寫法
public static void bubbleSort(int[] arr) {
int temp;
boolean flag;
for (int i = 0; i < arr.length - 1; i++) {
flag = false;
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
flag = true;
}
}
if (!flag) {
break;
}
}
}
這種優(yōu)化寫法的意圖簡單概括一下：
在一趟排序中，只要數(shù)組中有元素發(fā)生了交換利凑，就判定數(shù)組還沒有排好序浆劲，也就是說只要有一趟排序的過程中沒有發(fā)生元素的交換，那么就說明這個數(shù)組已經(jīng)是排好序了哀澈，后續(xù)的排序步驟完全可以不用執(zhí)行牌借，大大節(jié)省時間。
假如初始數(shù)組就是int[] array = {1, 2, 3, 4, 5, 6, 8, 7};割按，通過斷點(diǎn)調(diào)試的方式可以發(fā)現(xiàn)膨报，第一趟排序的結(jié)果是1, 2, 3, 4, 5, 6, 7, 8：
- 如果使用普通寫法，最外層的循環(huán)需要執(zhí)行 8 次适荣，也就是說還需要執(zhí)行 7 趟现柠；
- 如果使用優(yōu)化寫法，最外層的循環(huán)只需要執(zhí)行 2 次弛矛，第一趟執(zhí)行完數(shù)組已經(jīng)排好序了够吩，第二趟執(zhí)行的時候flag的值是false，進(jìn)入下面的 if 條件判斷丈氓，直接結(jié)束循環(huán)周循，后面6次就不會再去執(zhí)行了，是不是節(jié)省了一些時間扒寄？
