閑來(lái)無(wú)事，研究下算法，發(fā)現(xiàn)這個(gè)算法其實(shí)比開(kāi)發(fā)難度大的，首先你的理解算法的意義，其次你得有個(gè)抽象概念，其實(shí)算法最大的難點(diǎn)在于你怎么樣通過(guò)最優(yōu)的方法來(lái)實(shí)現(xiàn)，昨天同事問(wèn)我，你知道每一個(gè)算法的使用場(chǎng)景嗎？我當(dāng)時(shí)愣住了，誠(chéng)然，算法有時(shí)候?qū)懙某鰜?lái)，但是你未必知道它的使用場(chǎng)景，所以有時(shí)候研究算法還是得知道這個(gè)算法的由來(lái)，為什么要這樣去做，這樣做有什么優(yōu)點(diǎn)。原來(lái)發(fā)現(xiàn)還有很多東西要學(xué)的，好了，不廢話，今天來(lái)講講歸并排序。

歸并排序，可能很多人不熟悉，但是我說(shuō)一個(gè)場(chǎng)景，可能很類似，最近的LOL比賽看了的同學(xué)可能明白，16支隊(duì)分成四個(gè)組，然后勝者再分成兩個(gè)組，最后角逐出冠軍，其實(shí)這個(gè)分組，就跟歸并中很類似，其實(shí)歸并排序使用的是分而治之的思想來(lái)實(shí)現(xiàn)的，先分在合，那么怎么通過(guò)這個(gè)來(lái)實(shí)現(xiàn)的呢？我畫了一個(gè)步驟圖和代碼圖

先看步驟圖

首先我們來(lái)模擬一個(gè)數(shù)組76948573，那么我們先來(lái)談?wù)?b>分，怎么分？我們知道首先分成兩個(gè)小集合，見(jiàn)步驟一，將一個(gè)數(shù)組分解兩個(gè)小的數(shù)組，怎么分呢？我們來(lái)看看，首先我們確定首個(gè)元素的下標(biāo) startindex和最后一個(gè)元素的小標(biāo)endindex;,那么分的時(shí)候以（startindex+endindex）/2；

那么繼續(xù)分，這個(gè)時(shí)候有點(diǎn)變化，見(jiàn)步驟一中左邊，此時(shí)如果給左邊繼續(xù)分組，那么此時(shí)應(yīng)該從startindex到mid這之間的元素分組，右邊就是mid+1到endindex;

那么步驟二中的各個(gè)小分組繼續(xù)分，那么直到每一個(gè)分組中只有一個(gè)元素為止。那么如何一直分下去直到一個(gè)元素能，

看到這里是不是有點(diǎn)熟悉，就是這個(gè)函數(shù)自己調(diào)用自己，沒(méi)錯(cuò)就是遞歸。這個(gè)就能將原數(shù)據(jù)分組成步驟四，好了，現(xiàn)在分了，那么就需要比較了，怎么比較呢？

接下來(lái)我們就代碼圖中的1-6來(lái)對(duì)照步驟圖來(lái)厘清邏輯。首先看步驟圖中步驟四到步驟五，首先需要一個(gè)大集合來(lái)儲(chǔ)存計(jì)較合并后的結(jié)果。

1------>就是創(chuàng)建儲(chǔ)存結(jié)果的結(jié)果，這個(gè)數(shù)組是多大呢？就是合并的元素個(gè)數(shù)，因?yàn)閕ndex是從0開(kāi)始的，所以endindex - startindex +1就是元素個(gè)數(shù),。

2------->這三個(gè)臨時(shí)變量是做什么的呢？我們看步驟五到步驟六，

首先p1記錄左邊集合操作的位置，p2記錄右邊集合位置，p記錄合并后集合操作位置，在這個(gè)步驟中首先6跟右邊4比較，然后再跟9比較，這個(gè)時(shí)候比較晚后發(fā)現(xiàn)4是最小的，這個(gè)時(shí)候?qū)?放入大集合中第一個(gè)位置。在這一步驟操作完，p1移到7這個(gè)元素的位置，同事p2移到9元素這個(gè)位置，p移到4后面一個(gè)位置。

3-------->結(jié)合2來(lái)看，如果p1到了7元素這個(gè)位置，且p2到了9元素這個(gè)位置，說(shuō)明步驟四到步驟五中的元素都互相比較完了。那么合并元素的集合將數(shù)據(jù)裝入。

4,5,6--------->結(jié)合步驟圖其實(shí)就是拿左邊元素跟右邊元素去比較。如果左邊小于右邊，那么先將左邊放入大集合中，如果左邊集合大于右邊集合，那么將右邊先裝入大集合中

到了這里是否合并完成了呢？并沒(méi)有，有一種情況就是左邊元素都比右邊元素小，或者左邊元素都比右邊元素大，那么不用比較，直接復(fù)制到大集合中

這個(gè)情況很容易漏掉的，注意此過(guò)程；

最后將大集合賦值給原數(shù)組