摘要:用來標示該輪冒泡排序中,數組是否是有序的。適用情況當冒泡算法運行到后半段的時候,如果此時數組已經有序了,需要提前結束冒泡排序。當第一輪冒泡排序結束后,元素會被移動到下標的位置。
這篇文章包含了你一定知道的,和你不一定知道的冒泡排序。
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.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 % |
大家看到數據可能有點懵逼。
你這個優化之后,運行時間執行次數都沒有減少。你這優化的什么東西?
其實,這就要說到算法的適用性了。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 % |
以下是對同一個數組,使用每一種算法對其運行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)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74993.html
摘要:然而和分別提出了完全相反的的概念事件冒泡和事件捕獲。所有的節點中包含了這兩個方法,它們都接受個參數要處理的事件名作為事件處理程序的函數和一個布爾值。事件流級事件規定的事件流包括三個階段事件捕獲階段處于目標階段事件冒泡階段。 事件流描述的是從頁面中接受事件的順序。然而ie和netscape分別提出了完全相反的的概念:事件冒泡和事件捕獲。下面就說說這兩種事件流: 事件冒泡 事件冒泡,就是說...
摘要:然而和分別提出了完全相反的的概念事件冒泡和事件捕獲。所有的節點中包含了這兩個方法,它們都接受個參數要處理的事件名作為事件處理程序的函數和一個布爾值。事件流級事件規定的事件流包括三個階段事件捕獲階段處于目標階段事件冒泡階段。 事件流描述的是從頁面中接受事件的順序。然而ie和netscape分別提出了完全相反的的概念:事件冒泡和事件捕獲。下面就說說這兩種事件流: 事件冒泡 事件冒泡,就是說...
摘要:良好的排序算法具有進行最少的比較和交換的特征。冒泡排序是一個基于比較的排序算法,被認為是效率最低的排序算法之一。現在讓我們使用實現冒泡排序算法。插入排序到目前為止,我們已經看到了兩種基于比較的排序算法。 預警 本文適合對于排序算法不太了解的新手同學觀看,大佬直接忽略即可。因為考慮到連貫性,所以篇幅較長。老鐵們看完需要大概一個小時,但是從入門到完全理解可能需要10個小時(哈哈哈,以我自己...
摘要:多練練排序算法,不僅能夠讓我們知道一些排序方法的底層實現細節,更能夠鍛煉我們的思維,提升編程能力。排序算法的穩定性一個穩定的排序,指的是在排序之后,相同元素的前后順序不會被改變,反之就稱為不穩定。 1. 導言 因為這是排序算法系列的第一篇文章,所以多啰嗦幾句。 排序是很常見的算法之一,現在很多編程語言都集成了一些排序算法,比如Java 的Arrays.sort()方法,這種方式讓我們可...
閱讀 1357·2021-10-09 09:44
閱讀 1440·2021-09-28 09:36
閱讀 15927·2021-09-22 15:55
閱讀 1239·2021-09-22 15:45
閱讀 2199·2021-09-02 09:48
閱讀 2783·2019-08-29 17:19
閱讀 2296·2019-08-29 10:54
閱讀 906·2019-08-23 18:40