為什么歸并排序merge sort不需要像動(dòng)態(tài)規(guī)劃的問(wèn)題一樣考慮每一種劃分情況？針對(duì)你的問(wèn)題：為什么歸并排序merge sort不需要像動(dòng)態(tài)規(guī)劃的問(wèn)題一樣考慮每一種劃分情況？我的分析如下：遞歸的重要性

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

針對(duì)你的問(wèn)題：

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

我的分析如下：

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

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

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

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

合并排序和歸并排序是同一種排序方法嗎？

歸并排序是一種穩(wěn)定的算法（即在排序過(guò)程中大小相同的元素能夠保持排序前的順序，3212升序排序結(jié)果是1223，排序前后兩個(gè)2的順序不變），這一點(diǎn)在某些場(chǎng)景下至關(guān)重要。 歸并排序是最常用的外部排序方法（當(dāng)待排序的記錄放在外存上，內(nèi)存裝不下全部數(shù)據(jù)時(shí)，歸并排序仍然適用，當(dāng)然歸并排序同樣適用于內(nèi)部排序）。 歸并排序中“分”與“合”的過(guò)程是結(jié)合在一起的，即每一趟都在做“分”與“合”的工作，并不是先“分”完再“合”（“分”很簡(jiǎn)單，不就是一直二分二分直到不可再分唄，額，這么想就錯(cuò)了，分完就合不起來(lái)了，切記“分”與“合”是結(jié)合在一起的）