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

堆排序算法

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

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

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

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

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

歸并排序

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

歸并排序

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

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

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

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

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

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

二分查找算法

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

二分查找算法

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

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

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

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

BFPRT（線性查找算法）

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

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

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

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

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

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

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

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

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

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

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

1.訪問頂點v,；

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

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

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

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

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

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

1.首先將根節(jié)點放入隊列中,。

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