sort不需要像動態(tài)規(guī)劃的問題一樣考慮每一種劃分情況？

針對你的問題：

為什么歸并排序merge sort不需要像動態(tài)規(guī)劃的問題一樣考慮每一種劃分情況？

我的分析如下：

遞歸的重要性不言而喻，它是很多算法實現(xiàn)的基礎，比如含有分治思想的算法（歸并排序，二分查找），有關遍歷二叉樹的算法，或者求解數(shù)學遞推式的算法（斐波那契數(shù)列，n的階乘），回溯法，動態(tài)規(guī)劃等等， 一提到遞歸總有點發(fā)蒙，理論上比較好理解，但是一遇到復雜一點的遞歸算法，在大腦中很難想象遞歸在計算機中是怎么實現(xiàn)的。跟著一步步debug才終于搞明白，所以在這里先把過程給記錄下來。

歸并排序算法：就是運用分治的思想，把排序的過程變?yōu)橄劝褦?shù)組分成左右兩個部分，分別排序，再將排好序的兩個數(shù)組合并成一個有序數(shù)組。

重點分析一下代碼中 Merge_sort_c這個遞歸函數(shù)，首先是終止條件p>=r ，遞歸必須要有終止條件，否則就會陷入循環(huán)最終導致棧溢出。為啥會棧溢出？遞歸調(diào)用在底層其實是對線程棧的壓棧和出棧操作，每調(diào)用一次都會壓棧一次，并記錄相關的局部變量信息，線程棧的內(nèi)存是非常有限的，而遞歸調(diào)用如果是無限的，那么很快就會消耗完所有的內(nèi)存資源，最終導致內(nèi)存溢出。

接下來是兩個調(diào)用了Merge_sort_c 函數(shù)本身也就是遞歸調(diào)用，將這兩個遞歸調(diào)用分別編號#1和#2.在本例中,待排序的數(shù)組里面有6個元素(下標0-5)， 那么他們是怎么被壓棧又出棧的呢？如下圖所示: