轉(zhuǎn)自：
http://m.shnenglu.com/bujiwu/archive/2008/10/26/65146.html
CODE:http://m.shnenglu.com/Files/bujiwu/HeapSort.rar參考文章：
http://www.cnblogs.com/xiaotao823/articles/1055399.htmlhttp://zhidao.baidu.com/question/1003067.html1、 堆排序定義
n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱為堆性質(zhì))：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。
【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對(duì)應(yīng)的完全二叉樹分別如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆。
根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆。
注意：
①堆中任一子樹亦是堆。
②以上討論的堆實(shí)際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
3、堆排序特點(diǎn)
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點(diǎn)是：在排序過(guò)程中，將R[l..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系【參見(jiàn)二叉樹的順序存儲(chǔ)結(jié)構(gòu)】，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。
4、堆排序與直接插入排序的區(qū)別
直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實(shí)上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過(guò)，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。
堆排序可通過(guò)樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。
5、堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無(wú)序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。
1 /*
2 堆排序
3 (1)用大根堆排序的基本思想
4 ① 先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無(wú)序區(qū)
5 ② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無(wú)序區(qū)的最后一個(gè)記錄R[n]交換，
6 由此得到新的無(wú)序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
7 ③ 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R[1..n-1]調(diào)整為堆。
8 然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，
9 由此得到新的無(wú)序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n- 2].keys≤R[n-1..n].keys，
10 同樣要將R[1..n-2]調(diào)整為堆。
11 ……
12 直到無(wú)序區(qū)只有一個(gè)元素為止。
13 (2)大根堆排序算法的基本操作：
14 ① 初始化操作：將R[1..n]構(gòu)造為初始堆；
15 ② 每一趟排序的基本操作：將當(dāng)前無(wú)序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序區(qū)調(diào)整為堆(亦稱重建堆)。
16 注意：
17 ①只需做n-1趟排序，選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。
18 ②用小根堆排序與利用大根堆類似，只不過(guò)其排序結(jié)果是遞減有序的。
19 堆排序和直接選擇排序相反：在任何時(shí)刻，堆排序中無(wú)序區(qū)總是在有序區(qū)之前，
20 且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止。
21 */
22
23 //生成大根堆
24 void HeapAdjust(int SortData[],int StartIndex, int Length)
25 {
26 while(2*StartIndex+1 < Length)
27 {
28 int MinChildrenIndex = 2*StartIndex+1 ;
29 if(2*StartIndex+2 < Length )
30 {
31 //比較左子樹和右子樹，記錄最大值的Index
32 if(SortData[2*StartIndex+1]<SortData[2*StartIndex+2])
33 {
34 MinChildrenIndex = 2*StartIndex+2;
35 }
36 }
37 if(SortData[StartIndex] < SortData[MinChildrenIndex])
38 {
39 //交換i與MinChildrenIndex的數(shù)據(jù)
40 int tmpData =SortData[StartIndex];
41 SortData[StartIndex] =SortData[MinChildrenIndex];
42 SortData[MinChildrenIndex] =tmpData;
43 //堆被破壞，需要重新調(diào)整
44 StartIndex = MinChildrenIndex ;
45 }
46 else
47 {
48 //比較左右孩子均大則堆未破壞，不再需要調(diào)整
49 break;
50 }
51 }
52
53 return;
54 }
55
56 //堆排序
57 void HeapSortData(int SortData[], int Length)
58 {
59 int i=0;
60
61 //將Hr[0,Lenght-1]建成大根堆
62 for (i=Length/2-1; i>=0; i--)
63 {
64 HeapAdjust(SortData, i, Length);
65 }
66
67 for (i=Length-1; i>0; i--)
68 {
69 //與最后一個(gè)記錄交換
70 int tmpData =SortData[0];
71 SortData[0] =SortData[i];
72 SortData[i] =tmpData;
73 //將H.r[0..i]重新調(diào)整為大根堆
74 HeapAdjust(SortData, 0, i);
75 }
76
77 return;
78 }