最近在招聘過程中，發(fā)現(xiàn)好多小伙伴最基礎(chǔ)的一些算法回答，接下來會(huì)做一個(gè)系列，把基礎(chǔ)的排序等算法采用動(dòng)畫的形式做解析。

這是第一篇「冒泡排序」。

冒泡排序思想

冒泡排序(Bubble Sort)是一種交換排序，基本思想是「兩兩比較相鄰記錄，如果逆序則進(jìn)行交換，直到?jīng)]有逆序的記錄為止」。

冒泡算法有很多種實(shí)現(xiàn)方式，我們在這里只列舉出來兩種實(shí)現(xiàn)方式來講解冒泡排序。

排序原理

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2. 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

排序動(dòng)畫

「冒泡排序示意動(dòng)畫」

排序?qū)崿F(xiàn)

「簡單的冒泡排序」

  public static void sort(int[] arg) {
    //冒泡排序
    for (int i = 0; i < arg.length - 1; i++) {
      for (int j = arg.length - 1; j > i; j--) {
        if (arg[j] < arg[j - 1]) {//交換兩個(gè)數(shù)字
          int temp = arg[j];
          arg[j] = arg[j - 1];
          arg[j - 1] = temp;
        }
      }
    }
  }

上面的代碼是根據(jù)動(dòng)畫進(jìn)行的實(shí)現(xiàn)，假設(shè)我們的數(shù)據(jù)為{7,5,1,3,2,6}，當(dāng)i=0時(shí)，進(jìn)行第一輪排序，變量j由5開始一直循環(huán)到1，逐個(gè)進(jìn)行兩兩相鄰數(shù)字的比較，最后將數(shù)字最小的1排到第一位，當(dāng)i=1時(shí)，進(jìn)行第二輪排序，變量j由5開始一直循環(huán)到2，逐個(gè)進(jìn)行兩兩相鄰數(shù)字的比較，最后將數(shù)字2排到第二位，依次進(jìn)行i的下一輪比較，最終實(shí)現(xiàn)了數(shù)據(jù)的排序。

在這個(gè)過程中，由于數(shù)字像是浮起來的泡泡，所以稱之為冒泡排序。

排序優(yōu)化

上面的算法還有優(yōu)化的空間嗎？我們來看下面的這組數(shù)據(jù)，比如{6,5,4,3,1,2}，經(jīng)過一輪排序已經(jīng)變?yōu)榱藍(lán)6,5,4,3,2,1}，第二輪開始排序之后，還是{6,5,4,3,2,1}，數(shù)字的順序是沒有改變的，說明數(shù)字已經(jīng)處于排序的狀態(tài)了，則沒有必要進(jìn)行排序，所以還可以進(jìn)行優(yōu)化，代碼如下：

  public void sort(int[] arg) {
    //冒泡排序優(yōu)化
    for (int i = 0; i < arg.length - 1; i++) {
      boolean isSorted = true;
      for (int j = arg.length - 1; j > i; j--) {
        if (arg[j] < arg[j - 1]) {//交換兩個(gè)數(shù)字
          int temp = arg[j];
          arg[j] = arg[j - 1];
          arg[j - 1] = temp;
          isSorted = false;//如果有數(shù)據(jù)交換，則isSorted為false
        }
      }
      if (isSorted) {//isSorted為true，說明沒有進(jìn)行數(shù)據(jù)交換，數(shù)據(jù)已經(jīng)有序，則退出循環(huán)
        break;
      }
    }
  }

這樣經(jīng)過上面的優(yōu)化，冒泡排序會(huì)避免在數(shù)據(jù)已經(jīng)有序的情況下繼續(xù)進(jìn)行數(shù)據(jù)循環(huán)比較，性能得到了一定的提升。

冒泡排序的復(fù)雜度分析

數(shù)據(jù)正序的情況

比如數(shù)據(jù)為{6,5,4,3,2,1}，按照優(yōu)化后的算法，只需要，只會(huì)進(jìn)行5次比較，也就是n-1次的比較，所以時(shí)間復(fù)雜度為O{n}

數(shù)據(jù)逆序的情況

最壞的情況就是全部數(shù)據(jù)都是逆序，比如{6,5,4,3,2,1}，(n(n-1))/2次的數(shù)據(jù)操作和數(shù)據(jù)移動(dòng)，所以總的時(shí)間復(fù)雜度為 (O(n2))

「綜合上面的情況，冒泡排序的時(shí)間復(fù)雜度為(O(n2))」