摘要：用來標(biāo)示該輪冒泡排序中，數(shù)組是否是有序的。適用情況當(dāng)冒泡算法運(yùn)行到后半段的時候，如果此時數(shù)組已經(jīng)有序了，需要提前結(jié)束冒泡排序。當(dāng)?shù)谝惠喢芭菖判蚪Y(jié)束后，元素會被移動到下標(biāo)的位置。

這篇文章包含了你一定知道的，和你不一定知道的冒泡排序。

gif看不了可以點(diǎn)擊【原文】查看gif。

源碼: 【地址】

可能對于大多數(shù)的人來說比如我，接觸的第一個算法就是冒泡排序。

我看過的很多的文章都把冒泡排序描述成我們喝的汽水，底部不停的有二氧化碳的氣泡往上冒，還有描述成魚吐泡泡，都特別的形象。

其實結(jié)合一杯水來對比很好理解，將我們的數(shù)組豎著放進(jìn)杯子，數(shù)組中值小的元素密度相對較小，值大的元素密度相對較大。這樣一來，密度大的元素就會沉入杯底，而密度小的元素會慢慢的浮到杯子的最頂部，稍微專業(yè)一點(diǎn)描述如下。

冒泡算法會運(yùn)行多輪，每一輪會依次比較數(shù)組中相鄰的兩個元素的大小，如果左邊的元素大于右邊的元素，則交換兩個元素的位置。最終經(jīng)過多輪的排序，數(shù)組最終成為有序數(shù)組。

我們先不聊空間復(fù)雜度和時間復(fù)雜度的概念，我們先通過一張動圖來了解一下冒泡排序的過程。

這個圖形象的還原了密度不同的元素上浮和下沉的過程。

private void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        exchange(arr, j, j + 1);
      }
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

各位大佬看了上面的代碼之后先別激動，坐下坐下，日常操作?？赡芎芏嗟牡谝粋€冒泡排序算法就是這么寫的，比如我，同時還自我感覺良好，覺得算法也不過如此。

我們還是以數(shù)組[5, 1, 3, 7, 6, 2, 4]為例，我們通過動圖來看一下過程。

思路很簡單，我們用兩層循環(huán)來實現(xiàn)冒泡排序。

第一層，控制冒泡排序總共執(zhí)行的輪數(shù)，例如例子數(shù)組的長度是7，那么總共需要執(zhí)行6輪。如果長度是n，則需要執(zhí)行n-1輪

第二層，負(fù)責(zé)從左到右依次的兩兩比較相鄰元素，并且將大的元素交換到右側(cè)

這就是冒泡排序V1的思路。

下表是通過對一個0-100000的亂序數(shù)組的標(biāo)準(zhǔn)樣本，使用V1算法進(jìn)行排序所總共執(zhí)行的次數(shù)，以及對同一個數(shù)組執(zhí)行100次V1算法的所花的平均時間。

仔細(xì)看動圖我們可以發(fā)現(xiàn)，每一輪的排序，都從數(shù)組的最左端再到最右。而每一輪的冒泡，都可以確定一個最大的數(shù)，固定在數(shù)組的最右邊，也就是密度最大的元素會冒泡到杯子的最上面。

還是拿上面的數(shù)組舉例子。下圖是第一輪冒泡之后數(shù)組的元素位置。

第二輪排序之后如下。

可以看到，每一輪排序都會確認(rèn)一個最大元素，放在數(shù)組的最后面，當(dāng)算法進(jìn)行到后面，我們根本就沒有必要再去比較數(shù)組后面已經(jīng)有序的片段，我們接下來針對這個點(diǎn)來優(yōu)化一下。

這是優(yōu)化之后的代碼。

private void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        exchange(arr, j, j + 1);
      }
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

優(yōu)化之后的實現(xiàn)，也就變成了我們動圖中所展示的過程。

每一步之后都會確定一個元素在數(shù)組中的位置，所以之后的每次冒泡的需要比較的元素個數(shù)就會相應(yīng)的減1。這樣一來，避免了去比較已經(jīng)有序的數(shù)組，從而減少了大量的時間。

可能會有人看到，時間大部分已經(jīng)會覺得滿足了。從數(shù)據(jù)上看，執(zhí)行的次數(shù)減少了50%，而運(yùn)行的時間也減少了20%，在性能上已經(jīng)是很大的提升了。而且已經(jīng)減少了7億次的執(zhí)行次數(shù)，已經(jīng)很NB了。 那是不是到這就已經(jīng)很完美了呢？

答案是No。

同理，我們還是拿上面長度為7的數(shù)組來舉例子，只不過元素的位置有所不同，假設(shè)數(shù)組的元素如下。

[7, 1, 2, 3, 4, 5, 6]

我們再來一步一步的執(zhí)行V2算法， 看看會發(fā)生什么。

第一步執(zhí)行完畢后，數(shù)組的情況如下。

繼續(xù)推進(jìn)，當(dāng)?shù)谝惠唸?zhí)行完畢后，數(shù)組的元素位置如下。

這個時候，數(shù)組已經(jīng)排序完畢，但是按照目前的V2邏輯，仍然有5輪排序需要繼續(xù)，而且程序會完整的執(zhí)行完5輪的排序，如果是100000輪呢？這樣將會浪費(fèi)大量的計算資源。

private void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    boolean flag = true;
    for (int j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        exchange(arr, j, j + 1);
      }
    }
    if (flag) {
      break;
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

我們在V2代碼的基礎(chǔ)上，在第一層循環(huán)，也就是控制總冒泡輪數(shù)的循環(huán)中，加入了一個標(biāo)志為flag。用來標(biāo)示該輪冒泡排序中，數(shù)組是否是有序的。每一輪的初始值都是true。

當(dāng)?shù)诙友h(huán)，也就是冒泡排序的元素兩兩比較完成之后，flag的值仍然是true，則說明在這輪比較中沒有任何元素被交換了位置。也就是說，數(shù)組此時已經(jīng)是有序狀態(tài)了，沒有必要再執(zhí)行后續(xù)的剩余輪數(shù)的冒泡了。

所以，如果flag的值是true，就直接break了（沒有其他的操作return也沒毛病）。

大家看到數(shù)據(jù)可能有點(diǎn)懵逼。

你這個優(yōu)化之后，運(yùn)行時間執(zhí)行次數(shù)都沒有減少。你這優(yōu)化的什么東西？

其實，這就要說到算法的適用性了。V3的優(yōu)化是針對原始數(shù)據(jù)中存在一部分或者大量的數(shù)據(jù)已經(jīng)是有序的情況，V3的算法對于這樣的樣本數(shù)據(jù)才最適用。

其實是我們還沒有到優(yōu)化這種情況的那一步，但是其實仍然有這樣的說法，面對不同的數(shù)據(jù)結(jié)構(gòu)，幾乎沒有算法是萬能的

而目前的樣本數(shù)據(jù)仍然是隨機(jī)的亂序數(shù)組，所以并不能發(fā)揮優(yōu)化之后的算法的威力。所謂對癥下藥，同理并不是所有的算法都是萬能的。對于不同的數(shù)據(jù)我們需要選擇不同的算法。例如我們選擇[9999,1,2,…,9998]這行的數(shù)據(jù)做樣本來分析，我們來看一下V3算法的表現(xiàn)。

可以看到，提升非常明顯。

當(dāng)冒泡算法運(yùn)行到后半段的時候，如果此時數(shù)組已經(jīng)有序了，需要提前結(jié)束冒泡排序。V3針對這樣的情況就特別有效。

嗯，什么？為什么不是結(jié)束語？那是因為還有一種沒有考慮到啊。

我們總結(jié)一下前面的算法能夠處理的情況。

V1：正常亂序數(shù)組

V2：正常亂序數(shù)組，但對算法的執(zhí)行次數(shù)做了優(yōu)化

V3：大部分元素已經(jīng)有序的數(shù)組，可以提前結(jié)束冒泡排序

還有一種情況是冒泡算法的輪數(shù)沒有執(zhí)行完，甚至還沒有開始執(zhí)行，后半段的數(shù)組就已經(jīng)有序的數(shù)組，例如如下的情況。

這種情況，在數(shù)組完全有序之前都不會觸發(fā)V3中的提前停止算法，因為每一輪都有交換存在，flag的值會一直是true。而下標(biāo)2之后的所有的數(shù)組都是有序的，算法會依次的冒泡完所有的已有序部分，造成資源的浪費(fèi)。我們怎么來處理這種情況呢？

我們可以在V3的基礎(chǔ)之上來做。

當(dāng)?shù)谝惠喢芭菖判蚪Y(jié)束后，元素3會被移動到下標(biāo)2的位置。在此之后沒有再進(jìn)行過任意一輪的排序，但是如果我們不做處理，程序仍然會繼續(xù)的運(yùn)行下去。

我們在V3的基礎(chǔ)上，加上一個標(biāo)識endIndex來記錄這一輪最后的發(fā)生交換的位置。這樣一來，下一輪的冒泡就只冒到endIndex所記錄的位置即可。因為后面的數(shù)組沒有發(fā)生任何的交換，所以數(shù)組必定有序。

private void bubbleSort(int[] arr) {
  int endIndex = arr.length - 1;
  for (int i = 0; i < arr.length - 1; i++) {
    boolean flag = true;
    int endAt = 0;
    for (int j = 0; j < endIndex; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        endAt = j;
        exchange(arr, j, j + 1);
      }
    }
    endIndex = endAt;
    if (flag) {
      break;
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

這一節(jié)仍然不是結(jié)束語...

我們來看一下這種情況。

對于這種以上的算法都將不能發(fā)揮其應(yīng)有的作用。每一輪算法都存在元素的交換，同時，直到算法完成以前，數(shù)組都不是有序的。但是如果我們能直接從右向左冒泡，只需要一輪就可以完成排序。這就是雞尾酒排序，冒泡排序的另一種優(yōu)化，其適用情況就是上圖所展示的那種。

private void bubbleSort(int[] arr) {
  int leftBorder = 0;
  int rightBorder = arr.length - 1;

  int leftEndAt = 0;
  int rightEndAt = 0;

  for (int i = 0; i < arr.length / 2; i++) {
    boolean flag = true;
    for (int j = leftBorder; j < rightBorder; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        exchange(arr, j, j + 1);
        rightEndAt = j;
      }
    }
    rightBorder = rightEndAt;
    if (flag) {
      break;
    }

    flag = true;
    for (int j = rightBorder; j > leftBorder; j--) {
      if (arr[j] < arr[j - 1]) {
        flag = false;
        exchange(arr, j, j - 1);
        leftEndAt = j;
      }
    }
    leftBorder = leftEndAt;
    if (flag) {
      break;
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{2, 3, 4, 5, 6, 7, 1};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

第一層循環(huán)同樣用于控制總的循環(huán)輪數(shù)，由于每次需要從左到右再從右到左，所以總共的輪數(shù)是數(shù)組的長度 / 2。

內(nèi)存循環(huán)則負(fù)責(zé)先實現(xiàn)從左到右的冒泡排序，再實現(xiàn)從右到左的冒泡，并且同時結(jié)合了V4的優(yōu)化點(diǎn)。

我們來看一下V5與V4的對比。

以下是對同一個數(shù)組，使用每一種算法對其運(yùn)行100次的平均時間和執(zhí)行次數(shù)做的的對比。

而冒泡排序的時間復(fù)雜度分為最好的情況和最快的情況。

最好的情況為O(n). 也就是我們在V5中提到的那種情況，數(shù)組2, 3, 4, 5, 6, 7, 1。使用雞尾酒算法，只需要進(jìn)行一輪冒泡，即可完成對數(shù)組的排序。

最壞的情況為O(n^2).也就是V1，V2，V3和V4所遇到的情況，幾乎大部分?jǐn)?shù)據(jù)都是無序的。

往期文章：

聊聊微服務(wù)集群當(dāng)中的自動化工具
go源碼解析-Println的故事
用go-module作為包管理器搭建go的web服務(wù)器
WebAssembly完全入門——了解wasm的前世今身
小強(qiáng)開飯店-從單體應(yīng)用到微服務(wù)

相關(guān)：
微信公眾號：   SH的全棧筆記（或直接在添加公眾號界面搜索微信號LunhaoHu）