你知道和你不知道的冒泡排序

你知道和你不知道的冒泡排序

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

gif看不了可以點擊【原文】查看gif。

1. 什麼是冒泡排序

可能對於大多數的人來說比如我,接觸的第一個算法就是冒泡排序。

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

其實結合一杯水來對比很好理解,將我們的數組豎著放進杯子,數組中值小的元素密度相對較小,值大的元素密度相對較大。這樣一來,密度大的元素就會沉入杯底,而密度小的元素會慢慢的浮到杯子的最頂部,稍微專業一點描述如下。

冒泡算法會運行多輪,每一輪會依次比較數組中相鄰的兩個元素的大小,如果左邊的元素大於右邊的元素,則交換兩個元素的位置。最終經過多輪的排序,數組最終成為有序數組。

2. 排序過程展示

我們先不聊空間複雜度和時間複雜度的概念,我們先通過一張動圖來了解一下冒泡排序的過程。

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

3. 算法V1

3.1 代碼實現

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]

3.2 實現分析

各位大佬看了上面的代碼之後先別激動,坐下坐下,日常操作。可能很多的第一個冒泡排序算法就是這麼寫的,比如我,同時還自我感覺良好,覺得算法也不過如此。

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

思路很簡單,我們用兩層循環來實現冒泡排序。

  • 第一層,控制冒泡排序總共執行的輪數,例如例子數組的長度是7,那麼總共需要執行6輪。如果長度是n,則需要執行n-1輪
  • 第二層,負責從左到右依次的兩兩比較相鄰元素,並且將大的元素交換到右側

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

下錶是通過對一個0-100000的亂序數組的標準樣本,使用V1算法進行排序所總共執行的次數,以及對同一個數組執行100次V1算法的所花的平均時間。

算法執行情況 結果
樣本 [0 – 100000] 的亂序數組
算法 V1 執行的總次數 99990000 次(9999萬次
算法 V1 運行 100 次的平均時間 181 ms

4. 算法V2

4.1 實現分析

仔細看動圖我們可以發現,每一輪的排序,都從數組的最左端再到最右。而每一輪的冒泡,都可以確定一個最大的數,固定在數組的最右邊,也就是密度最大的元素會冒泡到杯子的最上面。

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

第二輪排序之後如下。

可以看到,每一輪排序都會確認一個最大元素,放在數組的最後面,當算法進行到後面,我們根本就沒有必要再去比較數組後面已經有序的片段,我們接下來針對這個點來優化一下。

4.2 代碼實現

這是優化之後的代碼。

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]

優化之後的實現,也就變成了我們動圖中所展示的過程。

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

算法執行情況 結果
樣本 [0 – 10000] 的亂序數組
算法 V2 執行的總次數 49995000 次(4999萬次
算法 V2 運行 100 次的平均時間 144 ms
運行時間與 V1 對比 V2 運行時間減少 20.44 %
執行次數與 V1 對比 V2 運行次數減少 50.00 %

可能會有人看到,時間大部分已經會覺得滿足了。從數據上看,執行的次數減少了50%,而運行的時間也減少了20%,在性能上已經是很大的提升了。而且已經減少了7億次的執行次數,已經很NB了。 那是不是到這就已經很完美了呢?

答案是No

4.3 哪裡可以優化

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

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

我們再來一步一步的執行V2算法, 看看會發生什麼。

第一步執行完畢后,數組的情況如下。

繼續推進,當第一輪執行完畢后,數組的元素位置如下。

這個時候,數組已經排序完畢,但是按照目前的V2邏輯,仍然有5輪排序需要繼續,而且程序會完整的執行完5輪的排序,如果是100000輪呢?這樣將會浪費大量的計算資源。

5. 算法V3

5.1 代碼實現

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]

5.2 實現分析

我們在V2代碼的基礎上,在第一層循環,也就是控制總冒泡輪數的循環中,加入了一個標誌為flag。用來標示該輪冒泡排序中,數組是否是有序的。每一輪的初始值都是true。

當第二層循環,也就是冒泡排序的元素兩兩比較完成之後,flag的值仍然是true,則說明在這輪比較中沒有任何元素被交換了位置。也就是說,數組此時已經是有序狀態了,沒有必要再執行後續的剩餘輪數的冒泡了。

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

算法執行情況 結果
樣本 [0 – 10000] 的亂序數組
算法 V3 執行的總次數 49993775
算法 V3 運行 100 次的平均時間 142 ms
運行時間與 V2 對比 V3 運行時間減少 00.00 %
執行次數與 V2 對比 V3 運行次數減少 00.00 %

5.3 數據分析

大家看到數據可能有點懵逼。

你這個優化之後,運行時間執行次數都沒有減少。你這優化的什麼東西?

其實,這就要說到算法的適用性了。V3的優化是針對原始數據中存在一部分或者大量的數據已經是有序的情況,V3的算法對於這樣的樣本數據才最適用。

其實是我們還沒有到優化這種情況的那一步,但是其實仍然有這樣的說法,面對不同的數據結構,幾乎沒有算法是萬能的

而目前的樣本數據仍然是隨機的亂序數組,所以並不能發揮優化之後的算法的威力。所謂對症下藥,同理並不是所有的算法都是萬能的。對於不同的數據我們需要選擇不同的算法。例如我們選擇[9999,1,2,…,9998]這行的數據做樣本來分析,我們來看一下V3算法的表現。

算法執行情況 結果
樣本 [0 – 10000] 的亂序數組
算法 V3 執行的總次數 19995
算法 V3 運行 100 次的平均時間 1 ms
運行時間與 V3 亂序樣例對比 V3 運行時間減少 99.96 %
執行次數與 V3 亂序樣例對比 V3 運行次數減少 99.29 %

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

5.4 適用情況

當冒泡算法運行到後半段的時候,如果此時數組已經有序了,需要提前結束冒泡排序。V3針對這樣的情況就特別有效。

6. 算法V4

嗯,什麼?為什麼不是結束語?那是因為還有一種沒有考慮到啊。

6.1 適用情況總結

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

  • V1:正常亂序數組
  • V2:正常亂序數組,但對算法的執行次數做了優化
  • V3:大部分元素已經有序的數組,可以提前結束冒泡排序

還有一種情況是冒泡算法的輪數沒有執行完,甚至還沒有開始執行,後半段的數組就已經有序的數組,例如如下的情況。

這種情況,在數組完全有序之前都不會觸發V3中的提前停止算法,因為每一輪都有交換存在,flag的值會一直是true。而下標2之後的所有的數組都是有序的,算法會依次的冒泡完所有的已有序部分,造成資源的浪費。我們怎麼來處理這種情況呢?

6.2 實現分析

我們可以在V3的基礎之上來做。

當第一輪冒泡排序結束后,元素3會被移動到下標2的位置。在此之後沒有再進行過任意一輪的排序,但是如果我們不做處理,程序仍然會繼續的運行下去。

我們在V3的基礎上,加上一個標識endIndex來記錄這一輪最後的發生交換的位置。這樣一來,下一輪的冒泡就只冒到endIndex所記錄的位置即可。因為後面的數組沒有發生任何的交換,所以數組必定有序。

6.3 代碼實現

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]

7. 算法V5

這一節仍然不是結束語…

7.1 算法優化

我們來看一下這種情況。

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

7.2 代碼實現

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]

7.3 實現分析

第一層循環同樣用於控制總的循環輪數,由於每次需要從左到右再從右到左,所以總共的輪數是數組的長度 / 2。

內存循環則負責先實現從左到右的冒泡排序,再實現從右到左的冒泡,並且同時結合了V4的優化點。

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

算法執行情況 結果
樣本 [2,3,4…10000,1] 的數組
算法 V5 執行的總次數 19995
算法 V5 運行 100 次的平均時間 1 ms
運行時間與 V4 對比 V5 運行時間減少 99.97 %
執行次數與 V4 對比 V5 運行次數減少 99.34 %

8. 總結

以下是對同一個數組,使用每一種算法對其運行100次的平均時間和執行次數做的的對比。

[0 – 10000] 的亂序數組 V1 V2 V3 V4 V5
執行時間(ms) 184 142 143 140 103
執行次數(次) 99990000 49995000 49971129 49943952 16664191
大部分有序的情況 V1 V2 V3 V4 V5
執行時間(ms) 181 141 146 145 107
執行次數(次) 99990000 49995000 49993230 49923591 16675618

而冒泡排序的時間複雜度分為最好的情況和最快的情況。

  • 最好的情況為O($n$). 也就是我們在V5中提到的那種情況,數組2, 3, 4, 5, 6, 7, 1。使用雞尾酒算法,只需要進行一輪冒泡,即可完成對數組的排序。
  • 最壞的情況為O($n^2$).也就是V1,V2,V3和V4所遇到的情況,幾乎大部分數據都是無序的。

往期文章:

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

相關:

  • 微信公眾號: SH的全棧筆記(或直接在添加公眾號界面搜索微信號LunhaoHu)

【精選推薦文章】

自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"