堆排序（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.比較兩個指針所指向的元素,，選擇相對小的元素放入到合并空間,，并移動指針到下一位置；

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

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ù)雜度。該算法在最壞情況下,，依然能達到o(n)的時間復(fù)雜度,。

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

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

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

1.訪問頂點v；

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

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

深度優(yōu)先搜索屬于盲目搜索，是圖論中的經(jīng)典算法,，利用深度優(yōu)先搜索算法可以產(chǎn)生目標圖的相應(yīng)拓撲排序表,，利用拓撲排序表可以方便的解決很多相關(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é)點,，并檢驗它是否為目標,。如果找到目標，則結(jié)束搜尋并回傳結(jié)果,；否則將它所有尚未檢驗過的直接子節(jié)點加入隊列中,。