從歸并排序引發(fā)的思考
點擊上方“服務端思維”，選擇“設為星標”
回復”669“獲取獨家整理的精選資料集
回復”加群“加入全國服務端高端社群「后端圈」
有非常多的同學，包括小孩子都曾經(jīng)或者正在覺得用代碼實現(xiàn)某個算法就像是在做腦經(jīng)急轉彎——看過答案之后你會覺得非常簡單，但自己就是寫不出來>_<
問題到底是出在哪里了呢？本篇文章從一個非常簡單，但卻蘊含著十分重要的算法思想的歸并排序入手，以一個完全小白的視角來考慮一下我們實現(xiàn)這個算法的時候到底會遇到哪些坑，以及如何解決它們。
什么是歸并排序？
為防止一部分小伙伴可能并不知道歸并排序是個啥，我們先來介紹一下。
歸并排序是一個非常經(jīng)典的排序算法，這個算法特簡單，一句話就可以描述完：將一個待排序數(shù)組分成兩個子數(shù)組，先分別對兩個子數(shù)組進行排序，然后再將兩個排好序的子數(shù)組合并成一個大的排序數(shù)組。
簡單的描述里隱藏著3個細節(jié)：
?細節(jié)1：問題的分解（Divide）：如何將一個待排序數(shù)組拆分成兩個子數(shù)組？
?細節(jié)2：子問題的解決（Conquer）：如何對兩個子數(shù)組進行排序？
?細節(jié)3：子問題的合并（Combine）：如何將兩個有序的子數(shù)組合并為一個大的有序數(shù)組？
下邊分析一下上述3個細節(jié)。
細節(jié)1
將一個數(shù)組拆分成兩個子數(shù)組非常簡單，只需要算出中間元素的下標，那我們可以規(guī)定：
?從數(shù)組開頭的元素到中間元素屬于一個子數(shù)組
?從中間元素的后一個元素開始，到數(shù)組最后一個元素屬于另一個子數(shù)組
中間元素的下標 = (起始元素的下標 + 末尾元素的下標) / 2小貼士：這里請大家思考一下我們?yōu)槭裁床挥脭?shù)組中包含元素數(shù)量除以2的方式來計算中間元素的下標，如果以這種方式計算中間元素的下標的話會發(fā)生什么事情（友情提示：可以按照數(shù)組中包含元素數(shù)量是單數(shù)還是雙數(shù)來分開討論）。
細節(jié)2
細節(jié)2其實很好解決，在對某個子數(shù)組進行排序時，可以將這個子數(shù)組繼續(xù)分成兩個子子數(shù)組，先對這兩個子子數(shù)組進行排序，然后再將這兩個排好序的子子數(shù)組進行排序，就完成了對子數(shù)組的排序。
子子數(shù)組怎么排？繼續(xù)拆成兩個更小的數(shù)組排唄。這里成功的進入了套娃模式，直到某個子子子...子數(shù)組里只包括1個元素就不用再拆了。
也就是說我們可以將子問題繼續(xù)拆分成多個子子問題，然后進入套娃模式，直到某個子問題足夠簡單為止（本例中就是直到子數(shù)組中僅包含1個元素為止）。
當然，上邊的描述不是很直觀，我們具體舉個例子看一下。
我們有一個無序數(shù)組[2, 7, 1, 4, 6, 5, 0, 4]：
這個數(shù)組包含8個元素，我們把它分成兩個組：1組和2組，每個組都包含4個元素：
包含4個元素的數(shù)組還是太長了，繼續(xù)將1組和2組分別拆分成2個組，現(xiàn)在就能得到4個組：1.1組、1.2組、2.1組、2.2組，每個組都包含2個元素：
繼續(xù)拆分包含2個元素的數(shù)組，將得到8個組：1.1.1組、1.1.2組、1.2.1組、1.2.2組、2.1.1組、2.1.2組、2.2.1組、2.2.2組，每個組只包含1個元素：
現(xiàn)在各個組僅包含1個元素，不能再拆分了，就可以對組中元素進行排序了。很顯然，僅有1個元素的數(shù)組本身就是已經(jīng)排好序的，也就是說：1.1.1組、1.1.2組、1.2.1組、1.2.2組、2.1.1組、2.1.2組、2.2.1組、2.2.2組這些僅包含1個元素的數(shù)組本身就是有序的，不用再額外進行排序了。
細節(jié)3
細節(jié)3其實也很好解決，只要從頭開始遍歷兩個子數(shù)組，每次都把兩個子數(shù)組中較小的元素加入到最后的結果中即可。
比方說有兩個包含2個元素的已排序數(shù)組[2, 7]和[1, 4]，我們想把這兩個數(shù)組合并為一個大的有序數(shù)組，那么我們可以定義兩個變量i和j：
?i表示第1個子數(shù)組的下標，初始指向第1個子數(shù)組的開頭元素。
?j表示第2個子數(shù)組的下標，初始指向第2個子數(shù)組的開頭元素。
如下圖所示：
接著就可以依次向存放最終結果的數(shù)組中填入元素了：
?第1步：當前i指向的元素是2，j指向的元素是1，比較i和j指向的元素哪個更小，由于2>1，所以將j指向的元素1填入結果數(shù)組中，并將j自增1，效果如下圖所示：
?第2步：當前i指向的元素是2，j指向的元素是4，比較i和j指向的元素哪個更小，由于2<4，所以將i指向的元素2填入結果數(shù)組中，并將i自增1，效果如下圖所示：
?第3步：當前i指向的元素是7，j指向的元素是4，比較i和j指向的元素哪個更小，由于7>4，所以將j指向的元素4填入結果數(shù)組中，并將j自增1，效果如下圖所示：
?第4步：當前i指向的元素是7，第2個子數(shù)組中的元素已經(jīng)遍歷完了，所以直接遍歷第1個子數(shù)組即可，即將i指向的元素7填入結果數(shù)組收納柜，并將i自增1，效果如下圖所示：
知道了如何合并兩個有序數(shù)組為一個大的有序數(shù)組之后，我們就可以完成子問題的合并了。
繼續(xù)看在處理細節(jié)2時引入的例子：1.1.1組、1.1.2組、1.2.1組、1.2.2組、2.1.1組、2.1.2組、2.2.1組、2.2.2組中僅包含1個元素，相當于子問題已經(jīng)得到解決，現(xiàn)在需要合并子問題了：
?將1.1.1組、1.1.2組中的有序數(shù)組合并，使1.1組成為有序數(shù)組；
?將1.2.1組、1.2.2組中的有序數(shù)組合并，使1.2組成為有序數(shù)組；
?將2.1.1組、2.1.2組中的有序數(shù)組合并，使2.1組成為有序數(shù)組；
?將2.2.1組、2.2.2組中的有序數(shù)組合并，使2.2組成為有序數(shù)組；
如下圖所示：
小貼士：
我們將2.1組的顏色加重，以表明組中的元素順序進行了重排。
現(xiàn)在1.1組、1.2組、2.1組、2.2組分別是4個有序數(shù)組，可以繼續(xù)合并子問題：
?將1.1組、1.2組中的有序數(shù)組合并，使1組成為有序數(shù)組；
?將2.1組、2.2組中的有序數(shù)組合并，使2組成為有序數(shù)組；
如下圖所示：
現(xiàn)在1組和2組分別是兩個有序數(shù)組，可以繼續(xù)合并子問題：
?將1組和2組中的有序數(shù)組合并為一個有序數(shù)組。如下圖所示：
至此，最初排序包含8個元素的數(shù)組的原始問題就得到了解決！
好了，這個算法的流程就描述完了。相信絕大部分小伙伴還是可以輕松理解上述歸并排序的算法流程的，說起來也可以頭頭是道，但是一旦落實到筆上，就有點心有余而力不足的趕腳了，下面就來分析一下到底是哪里難住了我們~
Talk is cheap, show me the code
實現(xiàn)算法的語言并不是重點，我們下邊將以Java為例，來看看如何寫代碼來實現(xiàn)歸并排序。
首先我們是要寫一個用于排序的函數(shù)，就把它命名為mergeSort吧，該函數(shù)用于對一個存儲整數(shù)的int數(shù)組進行排序，我想100%的小伙伴能完成下面代碼的編寫：
public void mergeSort(int[] arr) {}
如果int數(shù)組arr中沒有任何元素或者僅包含1個元素，那壓根兒就不用排序了，我猜90%的同學可以把下述校驗參數(shù)的代碼寫出來：
public void mergeSort(int[] arr) {if (arr.length <= 1)return;}
小貼士：
校驗參數(shù)十分重要，是展開后續(xù)過程的第一步，還是有很大一部分同學著急后續(xù)實現(xiàn)而忘記校驗參數(shù)的。
下邊到了真正精彩的地方了！
我們需要把數(shù)組分成兩半，然后分別進行排序。這里出現(xiàn)了歸并排序的一個糾結點：
?糾結點：?拆分出的子數(shù)組應該存儲到哪里？
之所以說是一個糾結點，是因為可以有2種實現(xiàn)思路：
?思路1：為每個子數(shù)組都創(chuàng)建一個新的存儲空間來存儲它們。
?思路2：還使用原數(shù)組保存子數(shù)組，使用額外的下標變量將其區(qū)分開即可。
很顯然思路2比思路1更省存儲空間，但思路1可能更簡單。我們接下來分別實現(xiàn)一下思路1和思路2。
思路1 如何實現(xiàn)
首先我們需要把原數(shù)組切成兩半，然后創(chuàng)建兩個新數(shù)組，并將原數(shù)組中對應的元素填入到新數(shù)組中，這個代碼也并不難寫，如下所示：
public void mergeSort(int[] arr) {if (arr.length <= 1)return;int mid = (0 + arr.length-1)/2;int[] a1 = new int[mid+1];int[] a2 = new int[arr.length-1-mid];copyArr(arr, 0, mid, a1);copyArr(arr, mid+1, arr.length-1, a2);}
首先我們需要計算中間元素的下標，用初始元素下標（例子中就是0）和末尾元素下標（例子中就是arr.length-1）的加和除以2即可得到中間元素的下標：
int mid = (0 + arr.length-1)/2;然后創(chuàng)建兩個數(shù)組a1和a2：
?a1中存放原數(shù)組中下標0到mid的元素，共mid+1個元素。?a2中存放原數(shù)組中下標mid+1到arr.length-1的元素，共(arr.length-1) - (mid+1) + 1，也就是arr.length-1-mid個元素。
然后將原數(shù)組中下標0到mid的元素復制到新數(shù)組a1中，將原數(shù)組中下標mid+1到arr.length-1的元素復制到新數(shù)組a2中。copyArr是我們自己創(chuàng)建的一個復制數(shù)組元素的工具方法（工具方法十分簡單，就不多嘮叨了）：
/*** 將源數(shù)組中指定下標的元素復制到目標數(shù)組中* @param source 源數(shù)組* @param low 源數(shù)組初始下標* @param high 源數(shù)組末尾下標* @param dest 目標數(shù)組*/private void copyArr(int[] source, int low, int high, int[] dest) {for (int i=low; i <= high; i++) {dest[i-low] = source[i];}}
然后我們就應該：
?步驟1：給一個子數(shù)組進行排序；
?步驟2：給另一個子數(shù)組進行排序；
?步驟3：將步驟1和步驟2的得到的兩個有序子數(shù)組合并為1個有序數(shù)組。
因為有3個步驟，所以我們需要定義3個函數(shù)，但由于步驟1和步驟2其實只是對某個數(shù)組進行排序，所以此時我們可以遞歸調(diào)用mergeSort函數(shù)即可。
對于步驟3，我們可以新定義一個merge方法來完成將兩個子數(shù)組合并為一個有序數(shù)組的功能，那么現(xiàn)在mergeSort函數(shù)就變成了這樣：
public void mergeSort(int[] arr) {if (arr.length <= 1)return;int mid = (arr.length-1)/2;int[] a1 = new int[mid+1];int[] a2 = new int[arr.length-1-mid];copyArr(arr, 0, mid, a1);copyArr(arr, mid+1, arr.length-1, a2);mergeSort(a1);mergeSort(a2);merge(a1, a2, arr);}
好了，現(xiàn)在mergeSort函數(shù)就已經(jīng)寫完了，接下來就只需實現(xiàn)merge方法即可。merge方法用于將兩個有序數(shù)組合并為一個有序數(shù)組，所以它的原型應該被定義為：
private void merge(int[] s1, int[] s2, int[] dest) {}
其中s1和s2是兩個子數(shù)組，dest是目標數(shù)組。
下邊需要定義幾個變量：
?i表示第1個子數(shù)組的下標，初始指向第1個子數(shù)組的開頭元素，也就是0。
?j表示第2個子數(shù)組的下標，初始指向第2個子數(shù)組的開頭元素，也就是0。
?pos表示目前要填充目標數(shù)組哪個下標的元素，初始為0。
我們需要將目標數(shù)組填滿，所以引入一個for循環(huán)，從目標數(shù)組開頭元素開始，直到最后一個元素為止。代碼如下所示：
private void merge(int[] s1, int[] s2, int[] dest) {int i = 0;int j = 0;for (int pos = 0; pos < dest.length; pos++) {// 這里寫入填充內(nèi)容}}
下邊的任務就是填充for循環(huán)中的內(nèi)容了，我們需要：
?比較s1[i]和s2[j]的大?。喝绻鹲1[i]較小，則把s1[i]填入dest[pos]中，并將i自增1；如果s2[j]較小，則把s2[j]填入dest[pos]中，并把j自增1。
那么代碼就可以寫成這樣：
private void merge(int[] s1, int[] s2, int[] dest) {int i = 0;int j = 0;for (int pos = 0; pos < dest.length; pos++) {if (s1[i] <= s2[j]) {dest[pos] = s1[i++];} else {dest[pos] = s2[j++];}}}
上述代碼忽略了一個最最重要的情況：如果s1先被遍歷完，也就是i為s1.length時，接下來就不能訪問s1[i]了，否則會拋出數(shù)組越界異常；如果s2先被遍歷完，也就是j為s2.length時，接下來也不能訪問s2[j]了，否則也會拋出數(shù)組越界異常。
忘記邊界條件在編碼實現(xiàn)算法時是極其容易出現(xiàn)，并且導致錯誤的問題。為簡單起見，我們可以先考慮邊界條件，然后再處理通用內(nèi)容。在本例中，我們可以先處理一下s1遍歷完以及s2遍歷完的情況，然后再比較s1[i]和s2[j]的大小，如下所示：
private void merge(int[] s1, int[] s2, int[] dest) {int i = 0;int j = 0;for (int pos = 0; pos < dest.length; pos++) {//如果s1已經(jīng)遍歷完，直接把s2[j]復制給dest[pos]，并給j自增1if (i == s1.length){dest[pos] = s2[j++];}//如果s2已經(jīng)遍歷完，直接把s1[i]復制給dest[pos]，并給i自增1else if (j == s2.length) {dest[pos] = s1[i++];}//以下是正常情況下的比較else if (s1[i] <= s2[j]) {dest[pos] = s1[i++];} else {dest[pos] = s2[j++];}}}
小貼士：
可以看到，增加判斷邊界條件的代碼時，代碼量會增大一倍甚至更多，我們之后可以介紹以下如何使用哨兵來顯著減少代碼量。
這樣，采用思路1，也就是單獨為子數(shù)組分配存儲空間的方式實現(xiàn)歸并排序的過程我們嘮叨完了，再來看一下采用思路2如何實現(xiàn)。
思路2 如何實現(xiàn)
思路1的弊病其實很明顯，就是每次調(diào)用mergeSort函數(shù)時，如果待排序數(shù)組中包含大于1個的元素，那就需要拆分成2個子數(shù)組，需要額外的為這兩個子數(shù)組分配存儲空間。
如果我們不想付出這些額外的成本，直接使用原數(shù)組來存儲子數(shù)組，那么在對子數(shù)組進行排序時就不得不指定該子數(shù)組對應的起始下標和結束下標是什么，所以我們不得不再定義一個用于排序子數(shù)組的函數(shù)，我們可以把它稱作mergeSort0，該函數(shù)原型如下所示：
private void mergeSort0(int[] arr, int low, int high) {}
其中arr是原始數(shù)組，low指的是子數(shù)組的起始下標，high指的是子數(shù)組的結束下標。
既然子數(shù)組的形式變成了原始數(shù)組+起始和結束下標的形式，那相應的把兩個有序子數(shù)組合并為一個有序數(shù)組的merge函數(shù)的參數(shù)也需要變一下了。
我們在拆分某個數(shù)組為兩個子數(shù)組時，是采用下邊的方法進行拆分的：
?從數(shù)組開頭的元素到中間元素屬于一個子數(shù)組
?從中間元素的后一個元素開始，到數(shù)組最后一個元素屬于另一個子數(shù)組
我們把被拆分數(shù)組開頭元素的下標稱作low，把中間元素下標稱作mid，把末尾元素的下標稱作high，那么被拆分出來的子數(shù)組的下標范圍就是：
?low?~?mid?屬于一個子數(shù)組
?mid+1?~?high屬于一個子數(shù)組
在合并子數(shù)組時，我們只需要知道low、mid、high是多少即可知道這兩個子數(shù)組的下標范圍分別是多少，那么merge函數(shù)的原型應該長這樣：
private void merge(int[] arr, int low, int mid, int high) {}
有了給子數(shù)組排序的函數(shù)mergeSort0和合并有序子數(shù)組的函數(shù)merge，那我們就可以這樣改寫mergeSort：
public void mergeSort(int[] arr) {if (arr.length <= 1)return;int mid = (arr.length-1)/2;mergeSort0(arr, 0, mid);mergeSort0(arr, mid+1, arr.length-1);merge(arr, 0, mid, arr.length-1);}
下邊先來實現(xiàn)以下mergeSort0，需要下邊這些步驟：
?校驗參數(shù)
?將待排序數(shù)組拆分成兩個子數(shù)組
?先給1個子數(shù)組排序
?再給另一個子數(shù)組排序
?將兩個已排序的子數(shù)組合并成一個有序數(shù)組
下邊看一下具體的代碼：
private void mergeSort0(int[] arr, int low, int high) {// 校驗參數(shù)，如果數(shù)組包含元素個數(shù)不大于1，則不需排序if (low >= high)return;// 計算中間元素位置int mid = (low + high)/2;// 給一個子數(shù)組排序mergeSort0(arr, low, mid);// 給另一個子數(shù)組排序mergeSort0(arr, mid+1, high);// 將兩個已排序子數(shù)組合并為一個有序數(shù)組merge(arr, low, mid, high);}
這樣mergeSort0就寫完了，該看一下merge函數(shù)如何編寫了，不過這時候會有一個巨大的問題：子數(shù)組占用原數(shù)組的存儲空間！
比方說某個數(shù)組有4個元素[2, 7, 1, 4]，它的兩個子數(shù)組都是有序的，分別是：[2, 7]和[1, 4]，如下圖所示：
如果我們想對上圖中的兩個子數(shù)組進行合并，由于j指向的元素1小于i指向的元素2，所以會將1放置在結果數(shù)組中的首個元素中，而結果數(shù)組就是原數(shù)組的話，直接就會把原數(shù)組的首個元素2給覆蓋掉！這是萬萬不能忍的。
為解決上述問題，我們需要一個臨時的存儲空間來存儲有序子數(shù)組內(nèi)容，這樣在將結果寫回原數(shù)組時才不會破壞子數(shù)組。這個臨時的存儲空間可以在merge函數(shù)內(nèi)開辟，但是這樣的話每調(diào)用一次merge函數(shù)都需要開辟一段臨時的存儲空間，也可以作為一個全局變量只申請一次存儲空間。很顯然后者優(yōu)雅一些，我們這里采用后者。
首先我們定義一個名叫tmp的成員變量：
private int[] tmp;然后改寫以下mergeSort函數(shù)，給tmp數(shù)組分配存儲空間：
public void mergeSort(int[] arr) {//給全局變量tmp分配存儲空間tmp = new int[arr.length];if (arr.length <= 1)return;int mid = (arr.length-1)/2;mergeSort0(arr, 0, mid);mergeSort0(arr, mid+1, arr.length-1);merge(arr, 0, mid, arr.length-1);}
然后我們在merge函數(shù)里就可以使用這個tmp數(shù)組了（由于在討論思路1的實現(xiàn)時已經(jīng)詳細討論過merge函數(shù)的實現(xiàn)，所以我們這里就不花大篇幅討論下邊改版后的merge函數(shù)了）：
private void merge(int arr[], int low, int mid, int high) {int i = low;int j = mid+1;//將子數(shù)組的內(nèi)容先復制到tmp數(shù)組中for (int pos = low; pos <= high; pos++) {tmp[pos] = arr[pos];}for (int pos = low; pos <= high; pos++) {if (i == mid+1) {arr[pos] = tmp[j++];}else if (j == high + 1) {arr[pos] = tmp[i++];}else if (tmp[i] <= tmp[j]) {arr[pos] = tmp[i++];} else {arr[pos] = tmp[j++];}}}
好的，大功告成！
再回頭看一下我們是不是還可以優(yōu)化什么地方呢？
大家如果仔細觀察一下mergeSort和mergeSort0兩個函數(shù)的代碼就會發(fā)現(xiàn)，它們的功能是極其類似的！只不過mergeSort里指定的開始元素為恒定的0，結束元素為恒定的arr.length-1，而mergeSort0里用變量low和high來替代。當程序中出現(xiàn)了相同功能的代碼時，一定要看一下能不能將功能相同的代碼合并起來！?在本例中，mergeSort中的代碼起始和調(diào)用一次mergeSort0(arr, 0, arr.length-1)是相同的，所以我們再精簡一下mergeSort函數(shù)：
public void mergeSort(int[] arr) {tmp = new int[arr.length];mergeSort0(arr, 0, arr.length-1);}
好的，這回才算大功告成了！
總結回顧
歸并排序算法極其簡單，但它背后所體現(xiàn)的分治思想卻是那么的重要，我們下邊再來梳理一下分治思想，大概分為3步：
1.分（Divide）：即將一個大問題拆分為若干個小問題（在歸并排序中就是將待排序數(shù)組拆分成2個子數(shù)組）。2.治（Conquer）：使用遞歸的形式繼續(xù)拆解小問題，直到問題小到可以很輕松的解決（在歸并排序中就是將子數(shù)組拆到只剩1個元素，那1個元素就肯定是有序的）。3.合（Combine）：將已解決的子問題合并起來，從而解決大問題（在歸并排序中就是將已排序的子數(shù)組合并成一個有序數(shù)組）。
另外，在具體的歸并排序中，大家需要注意下述問題：
?進行參數(shù)校驗十分必要
?在進行循環(huán)時注意邊界條件的判斷，可以先將特殊情況寫清楚后，再寫通用情況
?如何計算數(shù)組的中間元素以及如何劃分子數(shù)組？選取(起始元素下標+結束元素下標)/2的形式和直接用數(shù)組長度/2有什么區(qū)別。
?如何存儲子數(shù)組？是用額外的存儲空間，還是在原數(shù)組中保存加上起始和結束下標呢？
?在遇到功能相同的代碼時注意合并代碼
小貼士：我們之前在講MySQL的索引合并的時候用到了merge方法，大家還記得嗎？。
好的，以上就是關于實現(xiàn)歸并函數(shù)時的一些思考，希望可以對大家有所幫助。
— 本文結束 —
關注我，回復 「加群」 加入各種主題討論群。
對「服務端思維」有期待，請在文末點個在看
喜歡這篇文章，歡迎轉發(fā)、分享朋友圈
