希爾排序的算法思想 為什么歸并排序merge sort不需要像動(dòng)態(tài)規(guī)劃的問題一樣考慮每一種劃分情況?
為什么歸并排序merge sort不需要像動(dòng)態(tài)規(guī)劃的問題一樣考慮每一種劃分情況?為什么合并排序不需要像動(dòng)態(tài)規(guī)劃那樣考慮每個(gè)分區(qū)?遞歸的重要性不言而喻。它是許多算法的基礎(chǔ),例如具有分治思想的算法(合并排
為什么歸并排序merge sort不需要像動(dòng)態(tài)規(guī)劃的問題一樣考慮每一種劃分情況?
為什么合并排序不需要像動(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)過一步一步的調(diào)試,我們終于明白了,所以我們先把這個(gè)過程記錄下來。
:就是利用分而治之的思想,排序的過程就是先把數(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)用是無限的,它將很快消耗所有的內(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)要排序,那么如何將它們從堆棧中按出?如下圖所示:
合并排序和歸并排序是同一種排序方法嗎?
合并排序是一種穩(wěn)定的算法(即相同大小的元素可以保持排序前的順序,3212升序排序結(jié)果為1223,排序前后兩個(gè)2的順序保持不變),這在某些場景中非常重要。合并排序是最常用的外部排序方法(當(dāng)要排序的記錄放在外部內(nèi)存中并且內(nèi)存不能容納所有數(shù)據(jù)時(shí),合并排序仍然適用)。當(dāng)然,合并排序也適用于內(nèi)部排序)。合并排序中的“分離”和“組合”的過程是組合的,也就是說,每次都要做“分離”和“組合”的工作,而不是先“分離”再“組合”(分離很簡單,就是說不能再分離,不能再分離。嗯,這樣想是不對(duì)的。分離后,就不能合并了。記住,“分離”和“結(jié)合”是結(jié)合在一起的。)