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

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

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

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

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

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

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

和常用的排序算法外，還有哪些奇葩而有趣的排序算法？

排序算法有：冒泡排序-O（n^2）雞尾酒排序-O（n^2）插入排序-O（n^2）桶排序-O（n）計(jì)數(shù)排序-O（n k）合并排序O（NLog n）需要O（n）額外空間就地合并排序-O（n^2）二叉樹排序-O（NLog n）期望時(shí)間；O（n^2）最壞情況時(shí)間；需要O（n）額外空間鴿子洞排序-O（n k）需要O（k）額外空間

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

拿錢讓別人為你安排

！事實(shí)上，各種排序方法都有各自的優(yōu)缺點(diǎn)，適合不同的情況：

排序

插入排序：直接插入排序[shell”s排序

交換排序：冒泡排序[quick sort

選擇排序：直接選擇排序，堆排序；

合并排序：

分配排序：Bin排序，基數(shù)排序

]更多自己研究。

排序方法的選擇主要考慮算法性能和資源占用。這就是速度和存儲(chǔ)空間。