當前位置:首頁 > 公眾號精選 > 架構(gòu)師社區(qū)
[導讀]下面介紹的大家就需要熟練掌握了,是面試高頻考點,該文章分別用了遞歸法和迭代法實現(xiàn) 2 路歸并,希望對大家有一丟丟的幫助。

之前給大家介紹了幾個簡單排序,大家只需了解即可,下面介紹的大家就需要熟練掌握了,是面試高頻考點,該文章分別用了遞歸法和迭代法實現(xiàn) 2 路歸并,希望對大家有一丟丟的幫助。

歸并排序 (Merge Sort)

歸并排序是必須要熟練掌握的排序算法,是面試高頻考點,下面我們就一起來扒一扒歸并排序吧,原理很簡單,大家一下就能搞懂。

袁記菜館內(nèi)

第 23 屆食神爭霸賽開賽啦!

袁廚想在自己排名前4的分店中,挑選一個最優(yōu)秀的廚師來參加食神爭霸賽,選拔規(guī)則如下。

第一場 PK:每個分店選出兩名廚師,首先進行店內(nèi) PK,選出店內(nèi)里的勝者

第二場 PK: 然后店內(nèi)的優(yōu)勝者代表分店挑戰(zhàn)其他某一分店的勝者(半決賽)

第三場 PK:最后剩下的兩名勝者進行PK,選出最后的勝者。

示意圖如下

今天說的是必須要熟練掌握的歸并排序

廚神爭霸賽

上面的例子大家應該不會陌生吧,其實我們歸并排序和食神選拔賽的流程是有些相似的,下面我們一起來看一下歸并排序吧。

歸并這個詞語的含義就是合并,并入的意思,而在我們的數(shù)據(jù)結(jié)構(gòu)中的定義是將兩個或兩個以上的有序表合成一個新的有序表。而我們這里說的歸并排序就是使用歸并的思想實現(xiàn)的排序方法。

歸并排序使用的就是分治思想。顧名思義就是分而治之,將一個大問題分解成若干個小的子問題來解決。小的子問題解決了,大問題也就解決了。分治后面會專門寫一篇文章進行描述,這里先簡單提一下。

下面我們通過一個圖片來描述一下歸并排序的數(shù)據(jù)變換情況,見下圖。

今天說的是必須要熟練掌握的歸并排序

歸并排序

我們簡單了解了歸并排序的思想,從上面的描述中,我們可以知道算法的歸并過程是比較難實現(xiàn)的,這也是這個算法的重點,我們先通過一個視頻來看一下歸并函數(shù)的具體步驟,看完我們這個視頻就能懂個大概啦。

視頻中歸并步驟大家有沒有看懂呀,沒看懂也不用著急,下面我們一起來拆解一下,歸并過程共分三步走。

第一步:創(chuàng)建一個額外大集合用于存儲歸并結(jié)果,長度則為那兩個小集合的和,從視頻中也可以看出

第二步:我們從左自右比較兩個指針指向的值,將較小的那個存入大集合中,存入之后指針移動,并繼續(xù)比較,直到某一小集合的元素全部都存到大集合中。見下圖

今天說的是必須要熟練掌握的歸并排序

合并

第三步:當某一小集合元素全部放入大集合中,則需將另一小集合中剩余的所有元素存到大集合中,見下圖

今天說的是必須要熟練掌握的歸并排序

好啦,看完視頻和圖解是不是能夠?qū)懗鰝€大概啦,了解了算法原理之后代碼寫起來就很簡單啦,

下面我們看代碼吧。

注:這里用了System.arraycopy(),大家也可以使用其他方法,其中的五個參數(shù)分別是,源數(shù)組,目的數(shù)組,源數(shù)組起始索引,目的數(shù)組放置的起始索引,復制的長度

class Solution { public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1); return nums;
    } public void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = left + ((right - left) >> 1);
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);
            merge(arr,left,mid,right);
        }
    } //歸并 public void merge(int[] arr,int left, int mid, int right) { //第一步,定義一個新的臨時數(shù)組 int[] temparr = new int[right -left + 1]; int temp1 = left, temp2 = mid + 1; int index = 0; //對應第二步,比較每個指針指向的值,小的存入大集合 while (temp1 <= mid && temp2 <= right) { if (arr[temp1] <= arr[temp2]) { temparr[index++] = arr[temp1++]; } else {
                temparr[index++] = arr[temp2++];
            }
        } //對應第三步,將某一小集合的剩余元素存到大集合中 if (temp1 <= mid) System.arraycopy(arr, temp1, temparr, index, mid - temp1 + 1); if (temp2 <= right) System.arraycopy(arr, temp2, temparr, index, right -temp2 + 1);    
        System.arraycopy(temparr,0,arr,left,right-left+1); 
    }
}

歸并排序時間復雜度分析

我們一趟歸并,需要將兩個小集合的長度放到大集合中,則需要將待排序序列中的所有記錄掃描一遍所以時間復雜度為O(n)。

歸并排序把集合一層一層的折半分組,則由完全二叉樹的深度可知,整個排序過程需要進行 logn(向上取整)次,則總的時間復雜度為 O(nlogn)。

另外歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無關(guān),所以在最好,最壞,平均情況下時間復雜度均為 O(nlogn) 。

雖然歸并排序時間復雜度很穩(wěn)定,但是他的應用范圍卻不如快速排序廣泛,這是因為歸并排序不是原地排序算法,空間復雜度不為 O(1),那么他的空間復雜度為多少呢?

歸并排序的空間復雜度分析

歸并排序所創(chuàng)建的臨時結(jié)合都會在方法結(jié)束時釋放,單次歸并排序的最大空間是 n ,所以歸并排序的空間復雜度為 O(n).

歸并排序的穩(wěn)定性分析

歸并排序的穩(wěn)定性,要看我們的 merge 函數(shù),我們代碼中設(shè)置了 arr[temp1] <= arr[temp2] ,當兩個元素相同時,先放入arr[temp1] 的值到大集合中,所以兩個相同元素的相對位置沒有發(fā)生改變,所以歸并排序是穩(wěn)定的排序算法。

今天說的是必須要熟練掌握的歸并排序

等等還沒完嘞,不要走呀。
歸并排序的 遞歸實現(xiàn)是比較常見的 ,也是比較容易理解的,下面我們一起來扒一下歸并排序的迭代寫法。看看他是怎么實現(xiàn)的。

我們通過一個視頻來了解下迭代方法的思想

是不是通過視頻了解個大概啦,下面我們來對視頻進行解析。

迭代實現(xiàn)的歸并排序是將小集合合成大集合,小集合大小為 1,2,4,8,…..。依次迭代,見下圖

今天說的是必須要熟練掌握的歸并排序

比如此時小集合大小為 1 。兩個小集合分別為 [3],[1]。

然后我們根據(jù)合并規(guī)則,見第一個視頻,將[3],[1]合并到臨時數(shù)組中,則小的先進,進而實現(xiàn)了排序,然后再將臨時數(shù)組的元素復制到原來數(shù)組中。則實現(xiàn)了一次合并。

下面則繼續(xù)合并[4],[6]。具體步驟一致。所有的小集合合并完成后,則小集合的大小變?yōu)?2,繼續(xù)執(zhí)行剛才步驟,見下圖。

今天說的是必須要熟練掌握的歸并排序

此時子集合的大小為 2 ,則為 [2,5],[1,3] 繼續(xù)按照上面的規(guī)則合并到臨時數(shù)組中完成排序。這就是迭代法的具體執(zhí)行過程,

下面我們直接看代碼吧。

注:遞歸法和迭代法的 merge 函數(shù)代碼一樣。

class Solution { public int[] sortArray (int[] nums) { //代表子集合大小,1,2,4,8,16..... int k = 1; int len = nums.length; while (k < len) { mergePass(nums,k,len); k *= 2;
        } return nums;

    } public void mergePass (int[] array, int k, int len) { int i; for (i = 0; i < len-2*k; i += 2*k) { //歸并 merge(array,i,i+k-1,i+2*k-1);
         } //歸并最后兩個序列 if (i + k < len) { merge(array,i,i+k-1,len-1);
         }

    } public void merge (int[] arr,int left, int mid, int right) { //第一步,定義一個新的臨時數(shù)組 int[] temparr = new int[right -left + 1]; int temp1 = left, temp2 = mid + 1; int index = 0; //對應第二步,比較每個指針指向的值,小的存入大集合 while (temp1 <= mid && temp2 <= right) { if (arr[temp1] <= arr[temp2]) { temparr[index++] = arr[temp1++]; } else {
                temparr[index++] = arr[temp2++];
            }
        } //對應第三步,將某一小集合的剩余元素存到大集合中 if (temp1 <= mid) System.arraycopy(arr, temp1, temparr, index, mid - temp1 + 1); if (temp2 <= right) System.arraycopy(arr, temp2, temparr, index, right -temp2 + 1); //將大集合的元素復制回原數(shù)組 System.arraycopy(temparr,0,arr,left,right-left+1); 
    }
}


通過上面的視頻解析和代碼,希望大家能夠?qū)w并排序給拿下,下面會給大家寫一下,歸并排序在實際刷題時的應用,感謝閱讀。


免責聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!

本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉