爱华网1.堆排序是一种树型选择排序，它的特点是：在排序过程中，将R[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在联系，在当前无序区中选择关键字最大（或最小）的记录。
2.堆排序只需要一个记录大小的辅助空间。实现堆排序需要解决两个问题：
一、如何将一个无序序列建成一个初始堆。
二、如何在输出堆顶元素后，调用剩余元素使之成为一个新的堆。
3.所谓筛选就是将以结点i为根结点的子树调整为一个堆。筛选算法的前提是结点i的左右子树必须已是堆。
4.显然只有一个结点的树是堆。根据完全二叉树的性质可知，具有n个结点的完全二叉树第n/2个结点之后的结点均是叶子结点，因此这些结点为根的子树都已是堆，我们只需要将非叶子结点作为根的子树调用成堆即可。即筛选须从第n/2个元素开始，逐层向上倒退，直至根结点。
4.初始堆建立以后，就可以进行排序了。
5.堆是一种顺序表示的具有堆序性的完全二叉树。
堆的定义:
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素.
堆排序算法的过程如下:1)得到当前序列的最小(大)的元素2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面 3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.重复上面的过程,直到序列调整完毕为止.
自己实现如下：
#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;
}
