基本思想

兩個(gè)數(shù)比較大小，大數(shù)上浮，小數(shù)下沉！因?yàn)楦_了的時(shí)候那個(gè)狀態(tài)相似，所以簡(jiǎn)稱冒泡！
簡(jiǎn)單來說就是這樣：比如有兩個(gè)數(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;
      }
    }
  }
}

上面的寫法也是最簡(jiǎn)單最直接的，兩層for循環(huán)就可以將數(shù)組排好序。但是對(duì)于一些極端情況并沒有考慮進(jìn)去，比如有這樣一個(gè)數(shù)組 int[] array = {1, 2, 3, 4, 5, 6, 8, 7}; ，第一趟就可以將數(shù)組排好序，那么后續(xù)的步驟就完全不用再執(zhí)行了，為了節(jié)省算法的執(zhí)行時(shí)間，可以使用一個(gè)狀態(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)化寫法的意圖簡(jiǎn)單概括一下：
在一趟排序中，只要數(shù)組中有元素發(fā)生了交換，就判定數(shù)組還沒有排好序，也就是說只要有一趟排序的過程中沒有發(fā)生元素的交換，那么就說明這個(gè)數(shù)組已經(jīng)是排好序了，后續(xù)的排序步驟完全可以不用執(zhí)行，大大節(jié)省時(shí)間。

假如初始數(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í)行的時(shí)候flag的值是false，進(jìn)入下面的 if 條件判斷，直接結(jié)束循環(huán)，后面6次就不會(huì)再去執(zhí)行了，是不是節(jié)省了一些時(shí)間？