什么是快速排序？基本思想是：取n條要排序的記錄中的任意一條（通常是第一條記錄），將記錄放在最后的位置，整個數(shù)據(jù)間隔被這個記錄分成兩個子間隔。所有小于記錄關鍵字的關鍵字放在前面的子區(qū)間，所有大于記錄關鍵

什么是快速排序？

基本思想是：取n條要排序的記錄中的任意一條（通常是第一條記錄），將記錄放在最后的位置，整個數(shù)據(jù)間隔被這個記錄分成兩個子間隔。所有小于記錄關鍵字的關鍵字放在前面的子區(qū)間，所有大于記錄關鍵字的關鍵字放在后面的子區(qū)間，記錄放在兩個子區(qū)間的中間。這個過程稱為快速排序。然后對所有兩個子間隔重復上述過程，直到每個子間隔中只有一個記錄。簡言之，每次排序都使表的第一個元素進入最終位置，將數(shù)據(jù)間隔一分為二，然后遞歸地繼續(xù)子間隔的劃分，直到子間隔的長度為1。

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

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

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

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

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

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