1. 各種排序演算法實現和比較
1、 堆排序定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
注意：
①堆中任一子樹亦是堆。
②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
3、堆排序特點
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。
4、堆排序與直接插入排序的區別
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重復執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
5、堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。
（3）堆排序的演算法：
void HeapSort(SeqIAst R)
{ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i；
BuildHeap(R)； //將R[1-n]建成初始堆
for(i=n;i1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最後一個記錄交換
Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質
} //endfor
} //HeapSort
（4） BuildHeap和Heapify函數的實現
因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。
① Heapify函數思想方法
每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換後，新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其餘任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。
"篩選法"調整堆
R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小於這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換後又可能使結點R[large]違反堆性質，同樣由於該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。
具體的演算法
②BuildHeap的實現
要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。
顯然只有一個結點的樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ， -1，…，1的結點作為根的子樹都調整為堆即可。
具體演算法。
5、大根堆排序實例
對於關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見。
6、 演算法分析
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1)，
它是不穩定的排序方法。
2. 數據結構與演算法--堆和堆排序
堆排序是一種原地的、時間復雜度為 O(nlogn) 的排序演算法。
堆是一種特殊的樹。
只要滿足這兩點，它就是一個堆：
對於每個節點的值都大於等於子樹中每個節點值的堆，我們叫做 「大頂堆」 。對於每個節點的值都小於等於子樹中每個節點值的堆，我們叫做 「小頂堆」 。
完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。下標可以直接計算出左右字數的下標。（數組中下標為 i 的節點，左子節點下標為 i∗2 ，右子節點下標為 i∗2+1，父節點的下標為 i/2 。）
如果我們把新插入的元素放到堆的最後，你可以看我畫的這個圖，是不是不符合堆的特性了？於是，我們就需要進行調整，讓其重新滿足堆的特性，這個過程我們起了一個名字，就叫做 堆化（heapify） 。
堆化實際上有兩種，從下往上和從上往下。這里我先講從下往上的堆化方法。
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。
我們把最後一個節點放到堆頂，然後利用同樣的父子節點對比方法。對於不滿足父子節點大小關系的，互換兩個節點，並且重復進行這個過程，直到父子節點之間滿足大小關系為止。這就是 從上往下的堆化方法 。
一個包含 n 個節點的完全二叉樹，樹的高度不會超過 log2n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，也就是 O(logn)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以，往堆中插入一個元素和刪除堆頂元素的時間復雜度都是 O(logn)。
這里我們藉助於堆這種數據結構實現的排序演算法，就叫做堆排序。這種排序方法的時間復雜度非常穩定，是 O(nlogn)，並且它還是原地排序演算法。
從後往前處理數組，並且每個數據都是從上往下堆化。
因為葉子節點往下堆化只能自己跟自己比較，所以我們直接從最後一個非葉子節點開始，依次堆化就行了。
建堆的時間復雜度就是 O(n)。 推導過程見 極客時間--數據結構與演算法之美
建堆結束之後，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。我們把它跟最後一個元素交換，那最大元素就放到了下標為 n 的位置。
這個過程有點類似上面講的「刪除堆頂元素」的操作，當堆頂元素移除之後，我們把下標為 n 的元素放到堆頂，然後再通過堆化的方法，將剩下的 n−1 個元素重新構建成堆。堆化完成之後，我們再取堆頂的元素，放到下標是 n−1 的位置，一直重復這個過程，直到最後堆中只剩下標為 1 的一個元素，排序工作就完成了。
整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序演算法。堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是 O(n)，排序過程的時間復雜度是 O(nlogn)，所以，堆排序整體的時間復雜度是 O(nlogn)。
堆排序不是穩定的排序演算法，因為在排序的過程，存在將堆的最後一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。
堆這種數據結構幾個非常重要的應用：優先順序隊列、求 Top K 和求中位數。
假設我們有 100 個小文件，每個文件的大小是 100MB，每個文件中存儲的都是有序的字元串。我們希望將這些 100 個小文件合並成一個有序的大文件。這里就會用到優先順序隊列。
這里就可以用到優先順序隊列，也可以說是堆。我們將從小文件中取出來的字元串放入到小頂堆中，那堆頂的元素，也就是優先順序隊列隊首的元素，就是最小的字元串。我們將這個字元串放入到大文件中，並將其從堆中刪除。然後再從小文件中取出下一個字元串，放入到堆中。循環這個過程，就可以將 100 個小文件中的數據依次放入到大文件中。
我們可以用優先順序隊列來解決。我們按照任務設定的執行時間，將這些任務存儲在優先順序隊列中，隊列首部（也就是小頂堆的堆頂）存儲的是最先執行的任務。
如何在一個包含 n 個數據的數組中，查找前 K 大數據呢？我們可以維護一個大小為 K 的小頂堆，順序遍歷數組，從數組中取出數據與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，並且將這個元素插入到堆中；如果比堆頂元素小，則不做處理，繼續遍歷數組。這樣等數組中的數據都遍歷完之後，堆中的數據就是前 K 大數據了。
中位數，顧名思義，就是處在中間位置的那個數。
使用兩個堆：一個大頂堆， 一個小頂堆。 小頂堆中的數據都大於大頂堆中的數據。
如果新加入的數據小於等於大頂堆的堆頂元素，我們就將這個新數據插入到大頂堆；否則，我們就將這個新數據插入到小頂堆。
也就是說，如果有 n 個數據，n 是偶數，我們從小到大排序，那前 2n 個數據存儲在大頂堆中，後 2n 個數據存儲在小頂堆中。這樣，大頂堆中的堆頂元素就是我們要找的中位數。如果 n 是奇數，情況是類似的，大頂堆就存儲 2n+1 個數據，小頂堆中就存儲 2n 個數據。
極客時間--數據結構與演算法之美--28 | 堆和堆排序：為什麼說堆排序沒有快速排序快？
3. 100w個數,用最快的方法,求從小到大排序後的前五個數（cc++程序）
我面試的時候有問到過，因為數據量很大，所以要同時考慮空間問題。標准答案是採用堆排序。
求從小到大排序後的前五個數，就是求最小的5個數。
具體做法是：
構建一個只有5個元素的max－heap，那麼根結點就是這5個數中最大的數，然後開始遍歷數組，如果遇到的數比max－heap的根結點還大，直接跳過，遇到比max－heap根結點小的數，就替代根結點，然後對這個max－heap進行維護（也就是排序，保證heap的特徵）。那麼遍歷完數組後，這個max－heap的5個元素就是最小的5個數。
關於堆排序的代碼應該不難找，或者我今天有空的時候寫給你～
4. 堆排序過程
1，實用的排序演算法：選擇排序
（1）選擇排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在後面n-i個待排序元素中選擇排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟做完，待排序元素只剩下一個，就不用再選了。
（2）三種常用的選擇排序方法
1>直接選擇排序
2>錦標賽排序
3>堆排序
其中，直接排序的思路和實現都比較簡單，並且相比其他排序演算法，直接選擇排序有一個突出的優勢——數據的移動次數少。
（3）直接選擇排序簡介
1>直接選擇排序（select sort）是一種簡單的排序方法，它的基本步驟是：
1）在一組元素V[i]~V[n-1]中選擇具有最小排序碼的元素；
2）若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素對調；
3）在這組元素中剔除這個具有最小排序碼的元素，在剩下的元素V[i+1]~V[n-1]中重復執行1、2步驟，直到剩餘元素只有一個為止。
2>直接選擇排序使用注意
它對一類重要的元素序列具有較好的效率，這就是元素規模很大，而排序碼卻比較小的序列。因為對這種序列進行排序，移動操作所花費的時間要比比較操作的時間大的多，而其他演算法移動操作的次數都要比直接選擇排序來的多，直接選擇排序是一種不穩定的 排序方法。
3>直接選擇排序C++函數代碼
//函數功能，直接選擇排序演算法對數列排序
//函數參數，數列起點，數列終點
void dselect_sort(const int start, const int end) {
for (int i = start; i < end; ++i) {
int min_position = i;
for (int j = i + 1; j <= end; ++j) { //此循環用來尋找最小關鍵碼
if (numbers[j] < numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己與自己交換
swap(numbers[min_position], numbers[i]);
（4）關於錦標賽排序
直接選擇排序中，當n比較大時，排序碼的比較次數相當多，這是因為在後一趟比較選擇時，往往把前一趟已經做過的比較又重復了一遍，沒有把前一趟的比較結果保留下來。
錦標賽排序（tournament sort）克服了這一缺點。它的思想與體育比賽類似，就是把待排序元素兩兩進行競賽，選出其中的勝利者，之後勝利者之間繼續競賽，再選出其中的勝利者，然後重復這一過程，最終構造出勝者樹，從而實現排序的目的。
2，堆排序的排序過程
（1）個人理解：堆排序是選擇排序的一種，所以它也符合選擇排序的整體思想。直接選擇排序是在還未成序的元素中逐個比較選擇，而堆排序是首先建立一個堆（最大堆或最小堆），這使得數列已經「大致」成序，之後只需要局部調整來重建堆即可。建立堆及重建堆這一過程映射到數組中，其實就是一個選擇的過程，只不過不是逐個比較選擇，而是藉助完全二叉樹來做到有目的的比較選擇。這也是堆排序性能優於直接選擇排序的一個體現。
（2）堆排序分為兩個步驟：
1>根據初始輸入數據，利用堆的調整演算法形成初始堆；
2>通過一系列的元素交換和重新調整堆進行排序。
（3）堆排序的排序思路
1>前提，我們是要對n個數據進行遞增排序，也就是說擁有最大排序碼的元素應該在數組的末端。
2>首先建立一個最大堆，則堆的第一個元素heap[0]具有最大的排序碼，將heap[0]與heap[n-1]對調，把具有最大排序碼的元素交換到最後，再對前面n-1個元素，使用堆的調整演算法siftDown(0,n-2)，重新建立最大堆。結果具有次最大排序碼的元素又浮到堆頂，即heap[0]的位置，再對調heap[0]與heap[n-2]，並調用siftDown(0，n-3)，對前n-2個元素重新調整，……如此反復，最後得到一個數列的排序碼遞增序列。
（4）堆排序的排序過程：
下面給出局部調整成最大堆的函數實現siftDown()，這個函數在前面最小堆實現博文中的實現思路已經給出，只需做微小的調整即可用在這里建立最大堆。