本文將介紹排序算法中的歸并排序丸氛，學(xué)習(xí)歸并排序需要很好地理解計(jì)算機(jī)中的分治思想和遞歸思想罚舱。
1 分治思想
歸并排序井辜，利用分而治之的思想，將大的問題管闷，轉(zhuǎn)換成簡(jiǎn)單的粥脚，小的問題來(lái)解決。分治包个，字面上的解釋是“分而治之”刷允，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡(jiǎn)單的直接求解碧囊，原問題的解即子問題的解的合并树灶。在計(jì)算機(jī)科學(xué)中，分治法就是運(yùn)用分治思想的一種很重要的算法糯而。它的核心思想可以用一句話來(lái)概括：大事化小天通，小事化了。
使用分治法解決問題熄驼，需要有兩部分內(nèi)容像寒，一部分是分解，將問題不停分解成更小的子問題谜洽，當(dāng)問題小到一定規(guī)模時(shí)萝映，可以比較容易地解決。一部分是合并阐虚，當(dāng)子問題被解決時(shí)序臂，要通過一定的方法，合并出原問題的解。
2 歸并排序
歸并排序是怎么分的呢奥秆？我們要對(duì)n個(gè)數(shù)排序逊彭，直接排太麻煩，拆成對(duì)兩部分构订，對(duì)n/2個(gè)數(shù)排序侮叮，把它們合并成一個(gè)有序數(shù)組，就是答案悼瘾。對(duì)n/2個(gè)數(shù)排序還是太復(fù)雜囊榜，繼續(xù)二分下去，n/4亥宿，n/8卸勺，n/16……直到分到最小，也就是長(zhǎng)度為1為止烫扼。這個(gè)時(shí)候就不用分了曙求。因?yàn)殚L(zhǎng)度為1本身已經(jīng)有序了。
如圖是歸并排序的一個(gè)例子映企，前四行是對(duì)問題進(jìn)行分解悟狱，后四行是對(duì)子問題進(jìn)行合并，最終得到原始問題的解堰氓。
使用分治的思想解決計(jì)算機(jī)的問題挤渐，分解的部分是比較簡(jiǎn)單的，合并的部分是比較難的双絮，并且這部分的效率也影響到了算法的整體效率挣菲。
對(duì)于歸并排序來(lái)說，合并部分的任務(wù)是掷邦，把有序序列合并成一個(gè)完整的有序序列。怎么合并呢椭赋？
我們把有序序列1和2進(jìn)行合并抚岗，需要另外一片新的空間，用來(lái)存放合并后的數(shù)組哪怔。我們首先比較序列1和2的開頭宣蔚，由于是有序序列，開頭就是最小的元素认境。比較兩個(gè)元素看誰(shuí)更小胚委，把最小的那個(gè)元素添加到合并序列中。添加完之后叉信，把該元素從序列里移除（實(shí)際代碼中并不會(huì)移除亩冬，而是指針直接指向下一個(gè)位置）。以上面圖①為例，2和3比較硅急，2比較小覆享，填入到合并序列中。然后把2去掉营袜。變成②中的情況撒顿。再把3和5比較，3比較小荚板，加入到合并序列中凤壁，把3從原始序列中去掉。如此反復(fù)，直到序列1和2都合并完畢袭灯。
如果出現(xiàn)一個(gè)序列已經(jīng)空了胧瓜，另一個(gè)序列還有多個(gè)元素，直接把這些元素添加到合并序列最后面即可徙鱼。
3 代碼解析
merge_sort函數(shù)定義了長(zhǎng)度為n的輔助數(shù)組，用于歸并排序中合并的過程针姿。
sort函數(shù)袱吆，對(duì)數(shù)組進(jìn)行分割，將問題劃分為左半部分和右半部分兩個(gè)子問題距淫，之后將兩個(gè)子問題進(jìn)行合并绞绒。注意到這里使用了遞歸，使得問題不斷分解榕暇，直到left>=right蓬衡，此時(shí)子問題的數(shù)組長(zhǎng)度為1。
對(duì)遞歸不了解的可以查看
要理解遞歸彤枢，你先要理解遞歸?mp.weixin.qq.com
merge函數(shù)是歸并排序中合并的部分狰晚。它對(duì)兩個(gè)有序序列進(jìn)行合并，合并成大的有序序列缴啡。這部分看代碼不難理解壁晒。
4 效率分析
歸并排序的時(shí)間復(fù)雜度T(n),每次可以分解出相同規(guī)模的子問題，并且這兩個(gè)子問題合并的復(fù)雜度為O(n)业栅，則T(n)=2T(n/2)+O(n)秒咐，根據(jù)主定理可以得到T(n)=O(nlogn)。需要注意的是碘裕，合并部分的時(shí)間復(fù)雜度如果過高携取，比如為O(n^2)，會(huì)導(dǎo)致整體時(shí)間復(fù)雜度變大帮孔。
