堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu),，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。算法步驟如下：

堆排序算法

1. 創(chuàng)建一個(gè)堆H[0..n-1],；

2. 把堆首（最大值）和堆尾互換,；

3. 把堆的尺寸縮小1，并調(diào)用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置,；

4.重復(fù)步驟2,，直到堆的尺寸為1。

堆排序的平均時(shí)間復(fù)雜度為Ο(nlogn) ,。

歸并排序

歸并排序（Mergesort）,，又稱(chēng)合并排序，是建立在歸并操作上的一種有效的排序算法,。該算法是采用分治法（DivideandConquer）的一個(gè)非常典型的應(yīng)用,。算法步驟如下：

歸并排序

1.申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和,，該空間用來(lái)存放合并后的序列,；

2.設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置,；

3.比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置,；

4.重復(fù)步驟3直到某一指針達(dá)到序列尾,；

5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

歸并排序的平均時(shí)間復(fù)雜度為Ο(nlogn) ,。

二分查找算法

二分查找算法,，也稱(chēng)二分搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法,。算法步驟如下：

二分查找算法

1. 搜索過(guò)程從數(shù)組的中間元素開(kāi)始,，如果中間元素正好是要查找的元素,，則搜索過(guò)程結(jié)束；

2. 如果某一特定元素大于或者小于中間元素,，則在數(shù)組大于或小于中間元素的那一半中查找返回步驟1,；

3. 如果在某一步驟數(shù)組為空，則代表找不到,。

這種搜索算法每一次比較都使搜索范圍縮小一半,。折半搜索每次把搜索區(qū)域減少一半，二分查找算法的時(shí)間復(fù)雜度為Ο(logn) ,。

BFPRT（線性查找算法）

BFPRT算法又稱(chēng)中位數(shù)的中位數(shù)算法,，由Blum、Floyd,、Pratt,、Rivest、Tarj提出,，并以他們的名字命名,。該算法的思想與快速排序思想相似，通過(guò)修改快速選擇算法的主元選取方法,，提高算法在最壞情況下的時(shí)間復(fù)雜度,，適用于解決為從某n個(gè)元素的序列中選出第k大（第k小）的元素的問(wèn)題,。具體算法步驟如下：

1.將n個(gè)元素每5個(gè)一組,，分成n/5（上界）組。

2.取出每一組的中位數(shù),，任意排序方法,，比如插入排序。

3.遞歸的調(diào)用selection算法查找上一步中所有中位數(shù)的中位數(shù),，設(shè)為x,，偶數(shù)個(gè)中位數(shù)的情況下設(shè)定為選取中間小的一個(gè)。

4.用x來(lái)分割數(shù)組,，設(shè)小于等于x的個(gè)數(shù)為k,，大于x的個(gè)數(shù)即為n-k。

5.若i==k,，返回x,；若ik，在大于x的元素中遞歸查找第i-k小的元素,。

終止條件是：n=1時(shí),，返回的即是i小元素。

BFPRT可以保證在最壞情況下仍為線性時(shí)間復(fù)雜度。該算法在最壞情況下,，依然能達(dá)到o(n)的時(shí)間復(fù)雜度,。

DFS（深度優(yōu)先搜索）

深度優(yōu)先搜索算法（Depth-First-Search），是搜索算法的一種,。它的基本思想是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn),，盡可能深的搜索樹(shù)的分支。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過(guò),，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn),。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn),，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過(guò)程,，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問(wèn)為止。算法步驟如下：

DFS（深度優(yōu)先搜索）

1.訪問(wèn)頂點(diǎn)v,；

2.依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā),，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問(wèn),；

3.若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn),，則從一個(gè)未被訪問(wèn)的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷,，直到圖中所有頂點(diǎn)均被訪問(wèn)過(guò)為止。

深度優(yōu)先搜索屬于盲目搜索,，是圖論中的經(jīng)典算法,，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮恚猛負(fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問(wèn)題,，如最大路徑問(wèn)題等等,。一般用堆數(shù)據(jù)結(jié)構(gòu)來(lái)輔助實(shí)現(xiàn)DFS算法。

BFS（廣度優(yōu)先搜索）

廣度優(yōu)先搜索算法（Breadth-First-Search）,，是一種圖形搜索算法,。它的基本思想是從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn),。如果所有節(jié)點(diǎn)均被訪問(wèn),，則算法中止。算法步驟如下：

BFS（廣度優(yōu)先搜索）

1.首先將根節(jié)點(diǎn)放入隊(duì)列中,。

2.從隊(duì)列中取出第一個(gè)節(jié)點(diǎn),，并檢驗(yàn)它是否為目標(biāo)。如果找到目標(biāo),，則結(jié)束搜尋并回傳結(jié)果,；否則將它所有尚未檢驗(yàn)過(guò)的直接子節(jié)點(diǎn)加入隊(duì)列中。