愛華網(wǎng)1.堆排序是一種樹型選擇排序，它的特點是：在排序過程中，將R[1…n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在聯(lián)系，在當前無序區(qū)中選擇關(guān)鍵字最大（或最小）的記錄。
2.堆排序只需要一個記錄大小的輔助空間。實現(xiàn)堆排序需要解決兩個問題：
一、如何將一個無序序列建成一個初始堆。
二、如何在輸出堆頂元素后，調(diào)用剩余元素使之成為一個新的堆。
3.所謂篩選就是將以結(jié)點i為根結(jié)點的子樹調(diào)整為一個堆。篩選算法的前提是結(jié)點i的左右子樹必須已是堆。
4.顯然只有一個結(jié)點的樹是堆。根據(jù)完全二叉樹的性質(zhì)可知，具有n個結(jié)點的完全二叉樹第n/2個結(jié)點之后的結(jié)點均是葉子結(jié)點，因此這些結(jié)點為根的子樹都已是堆，我們只需要將非葉子結(jié)點作為根的子樹調(diào)用成堆即可。即篩選須從第n/2個元素開始，逐層向上倒退，直至根結(jié)點。
4.初始堆建立以后，就可以進行排序了。
5.堆是一種順序表示的具有堆序性的完全二叉樹。
堆的定義:
n個關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))：
(1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。
堆的這個性質(zhì)使得可以迅速定位在一個序列之中的最小(大)的元素.
堆排序算法的過程如下:1)得到當前序列的最小(大)的元素2)把這個元素和最后一個元素進行交換,這樣當前的最小(大)的元素就放在了序列的最后,而原先的最后一個元素放到了序列的最前面 3)的交換可能會破壞堆序列的性質(zhì)(注意此時的序列是除去已經(jīng)放在最后面的元素),因此需要對序列進行調(diào)整,使之滿足于上面堆的性質(zhì).重復(fù)上面的過程,直到序列調(diào)整完畢為止.
自己實現(xiàn)如下：
#include "stdafx.h"
void sift(inta[],int i,int length)
{
int temp=a[i];
int j=2*i+1;
while(j<length)
{
if(j<length-1&&a[j]<a[j+1])
j++;
if(temp<a[j])
{
a[i]=a[j];
i=j;
j=2*i+1;
}
else
break;
}
a[i]=temp;
}
void HeapSort(inta[],int length)
{
int i;
int temp;
for(i=length/2-1;i>=0;i--)
sift(a,i,length);
for(i=length-1;i>0;i--)
{
temp=a[i];
a[i]=a[0];
a[0]=temp;
sift(a,0,i);
}
}
int _tmain(int argc,_TCHAR* argv[])
{
int i;
inta[]={777,555,4,4,4,3,3,445,555,33,66,22,566,88,55,44,66,33,55,2,7,9,0,-1,-99,4555,444,33,2,3,4,54,5,4,3,3,4,4,5,65,44,3,4};
int length=sizeof(a)/sizeof(int);
HeapSort(a,length);
for(i=0;i<length;i++)
printf("%dn",a[i]);
getchar();
return 0;
}
