為什么歸并排序merge sort不需要像動態(tài)規(guī)劃的問題一樣考慮每一種劃分情況？為什么合并排序不需要像動態(tài)規(guī)劃那樣考慮每個分區(qū)？遞歸的重要性不言而喻。它是許多算法的基礎(chǔ)，例如具有分治思想的算法（合并排

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

為什么合并排序不需要像動態(tài)規(guī)劃那樣考慮每個分區(qū)？

遞歸的重要性不言而喻。它是許多算法的基礎(chǔ)，例如具有分治思想的算法（合并排序、二叉搜索）、遍歷二叉樹的算法，或者求解數(shù)學(xué)遞歸（斐波那契序列、n的階乘）、回溯、動態(tài)規(guī)劃等算法，當(dāng)談到遞歸時，總是有點混亂。理論上更容易理解，但當(dāng)涉及到更復(fù)雜的遞歸算法時，很難想象遞歸是如何在計算機(jī)中實現(xiàn)的。經(jīng)過一步一步的調(diào)試，我們終于明白了，所以我們先把這個過程記錄下來。

：就是利用分而治之的思想，排序的過程就是先把數(shù)組分成左右兩部分，分別排序，然后把有序的兩個數(shù)組組合成一個有序的數(shù)組。

重點分析merge在代碼中的作用，sort是一個遞歸函數(shù)，第一個是終止條件P>=R，遞歸必須有終止條件，否則會陷入循環(huán)，最終導(dǎo)致堆棧溢出。為什么堆棧溢出？實際上，底部的遞歸調(diào)用是按下并退出線程堆棧的操作。每次調(diào)用都會按一次堆棧，并記錄相關(guān)的局部變量信息。線程堆棧的內(nèi)存非常有限。如果遞歸調(diào)用是無限的，它將很快消耗所有的內(nèi)存資源，并最終導(dǎo)致內(nèi)存溢出。

下兩個調(diào)用merge#sort?C函數(shù)本身也是一個遞歸調(diào)用，兩個遞歸調(diào)用分別編號為?1和?2。在本例中，數(shù)組中有六個元素（下標(biāo)0-5）要排序，那么如何將它們從堆棧中按出？如下圖所示，

在快速排序、堆排序、歸并排序中，什么排序是穩(wěn)定的？

合并排序是一種穩(wěn)定的排序算法。歸并排序的穩(wěn)定性分析：歸并排序是將序列遞歸地劃分為短序列，遞歸的退出是短序列只有一個或兩個序列，然后將每個有序的段序列歸并為一個有序的長序列，繼續(xù)歸并直到所有的原序列都是有序的。可以發(fā)現(xiàn)，當(dāng)有一個或兩個元素時，一個元素不會交換，如果兩個元素大小相等且沒有外部干擾，穩(wěn)定性不會被破壞。然后，在合并短序列的過程中，不破壞穩(wěn)定性。如果在合并過程中兩個當(dāng)前元素相等，則將前一序列中的元素保存在結(jié)果序列的前面，以保證合并的穩(wěn)定性。因此，合并排序也是一種穩(wěn)定的排序算法。擴(kuò)展數(shù)據(jù)：算法穩(wěn)定性判斷方法：常用排序算法中，堆排序、快速排序、希爾排序、直接選擇排序為不穩(wěn)定排序算法，基數(shù)排序、氣泡排序、直接插入排序、半插入排序、合并排序為穩(wěn)定排序算法。對于不穩(wěn)定排序算法，只需舉例說明其不穩(wěn)定性；對于穩(wěn)定排序算法，必須對算法進(jìn)行分析才能得到穩(wěn)定的特征。需要注意的是，排序算法是否穩(wěn)定取決于具體的算法。不穩(wěn)定算法在一定條件下可以成為穩(wěn)定算法，穩(wěn)定算法在一定條件下也可以成為不穩(wěn)定算法。例如，快速排序原本是一種不穩(wěn)定的排序方法，但如果要排序的記錄中只有一組具有相同鍵的記錄，并且選定的軸值只是組中相同鍵的一個，則快速排序是穩(wěn)定的。