堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu),，并同時(shí)滿足堆積的性質(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）,，又稱合并排序,，是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（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) 。

二分查找算法

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

二分查找算法

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

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

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

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

BFPRT（線性查找算法）

BFPRT算法又稱中位數(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），是搜索算法的一種,。它的基本思想是沿著樹的深度遍歷樹的節(jié)點(diǎn),，盡可能深的搜索樹的分支。當(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)始,，沿著樹的寬度遍歷樹的節(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ì)列中,。