如何熟練掌握歸并排序

這篇文章主要介紹“如何熟練掌握歸并排序”，在日常操作中，相信很多人在如何熟練掌握歸并排序問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”如何熟練掌握歸并排序”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

歸并排序 (Merge Sort)

歸并排序是必須要熟練掌握的排序算法，是面試高頻考點(diǎn)，下面我們就一起來(lái)扒一扒歸并排序吧，原理很簡(jiǎn)單，大家一下就能搞懂。

袁記菜館內(nèi)

第 23 屆食神爭(zhēng)霸賽開(kāi)賽啦!

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

第一場(chǎng) PK：每個(gè)分店選出兩名廚師，首先進(jìn)行店內(nèi) PK,選出店內(nèi)里的勝者

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

第三場(chǎng) PK：最后剩下的兩名勝者進(jìn)行PK,選出最后的勝者。

示意圖如下

廚神爭(zhēng)霸賽

上面的例子大家應(yīng)該不會(huì)陌生吧，其實(shí)我們歸并排序和食神選拔賽的流程是有些相似的，下面我們一起來(lái)看一下歸并排序吧。

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

歸并排序使用的就是分治思想。顧名思義就是分而治之，將一個(gè)大問(wèn)題分解成若干個(gè)小的子問(wèn)題來(lái)解決。小的子問(wèn)題解決了，大問(wèn)題也就解決了。分治后面會(huì)專(zhuān)門(mén)寫(xiě)一篇文章進(jìn)行描述，這里先簡(jiǎn)單提一下。

下面我們通過(guò)一個(gè)圖片來(lái)描述一下歸并排序的數(shù)據(jù)變換情況，見(jiàn)下圖。

歸并排序

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

視頻號(hào)

視頻中歸并步驟大家有沒(méi)有看懂呀，沒(méi)看懂也不用著急，下面我們一起來(lái)拆解一下，歸并過(guò)程共分三步走。

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

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

合并

第三步：當(dāng)某一小集合元素全部放入大集合中，則需將另一小集合中剩余的所有元素存到大集合中，見(jiàn)下圖

好啦，看完視頻和圖解是不是能夠?qū)懗鰝€(gè)大概啦，了解了算法原理之后代碼寫(xiě)起來(lái)就很簡(jiǎn)單啦，

下面我們看代碼吧。

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

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) {         //第一步，定義一個(gè)新的臨時(shí)數(shù)組         int[] temparr = new int[right -left + 1];         int temp1 = left, temp2 = mid + 1;         int index = 0;         //對(duì)應(yīng)第二步，比較每個(gè)指針指向的值，小的存入大集合         while (temp1 <= mid && temp2 <= right) {             if (arr[temp1] <= arr[temp2]) {                 temparr[index++] = arr[temp1++];             } else {                 temparr[index++] = arr[temp2++];             }         }         //對(duì)應(yīng)第三步，將某一小集合的剩余元素存到大集合中         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,0+left,right-left+1);      } }

歸并排序時(shí)間復(fù)雜度分析

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

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

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

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

歸并排序的空間復(fù)雜度分析

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

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

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

等等還沒(méi)完嘞，不要走呀。

歸并排序的遞歸實(shí)現(xiàn)是比較常見(jiàn)的，也是比較容易理解的，下面我們一起來(lái)扒一下歸并排序的迭代寫(xiě)法。看看他是怎么實(shí)現(xiàn)的。

我們通過(guò)一個(gè)視頻來(lái)了解下迭代方法的思想

視頻號(hào)

是不是通過(guò)視頻了解個(gè)大概啦，下面我們來(lái)對(duì)視頻進(jìn)行解析。

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

比如此時(shí)小集合大小為 1 。兩個(gè)小集合分別為 [3],[1]。

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

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

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

下面我們直接看代碼吧。

注：遞歸法和迭代法的 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);          }          //歸并最后兩個(gè)序列          if (i + k < len) {              merge(array,i,i+k-1,len-1);          }      }      public void merge (int[] arr,int left, int mid, int right) {         //第一步，定義一個(gè)新的臨時(shí)數(shù)組         int[] temparr = new int[right -left + 1];         int temp1 = left, temp2 = mid + 1;         int index = 0;         //對(duì)應(yīng)第二步，比較每個(gè)指針指向的值，小的存入大集合         while (temp1 <= mid && temp2 <= right) {             if (arr[temp1] <= arr[temp2]) {                 temparr[index++] = arr[temp1++];             } else {                 temparr[index++] = arr[temp2++];             }         }         //對(duì)應(yīng)第三步，將某一小集合的剩余元素存到大集合中         if (temp1 <= mid) System.arraycopy(arr, temp1, temparr, index, mid - temp1 + 1);         if (temp2 <= right) System.arraycopy(arr, temp2, temparr, index, right -temp2 + 1);            //將大集合的元素復(fù)制回原數(shù)組         System.arraycopy(temparr,0,arr,0+left,right-left+1);      } }

到此，關(guān)于“如何熟練掌握歸并排序”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！