堆排序（Heap Sort）具体步骤为
- 将无序序列建成大顶堆（小顶堆）：从最后一个非叶子节点开始通过堆调整HeapAdjust()变成小顶堆或大顶堆
- 将顶部元素与堆尾数组交换，此是末尾元素就是最大值，顶部元素不满足堆，故要将顶部元素在剩余的i-1个元素中调整为堆
- 反复第2步。直至所有顶点被输出，序列变成从小到大的有序序列
C语言实现（编译器Dev-c++5.4.0，源代码后缀.cpp）
原创文章，转载请注明来自钢铁侠Mac博客http://www.cnblogs.com/gangtiexia
#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
#define OK 1
#define TRUE 1
#define MAXSIZE 6
typedef int Status;
typedef int KeyType;
typedef char InfoType; typedef struct{
KeyType score;
InfoType name[];
}RedType; typedef struct{
RedType r[MAXSIZE+];
int length;
}SqList; Status initSqList(SqList &l){
l.length=MAXSIZE;
for(int i=;i<=l.length;i++){
printf("请输入第%d个同学的姓名：",i);
scanf("%s",l.r[i].name);
printf("请输入第%d个同学的分数：",i);
scanf("%d",&(l.r[i].score));
}
printf("初始化完毕");
}
/*
Name: 堆调整
Copyright: http://www.cnblogs.com/gangtiexia
Author: 钢铁侠
Date: 2015-12-12 21:05:20
Description: 参数1为要调整的无序序列，参数2为要调整的数据的位置，参数3为要调整的序列的长度
*/ Status HeapAdjust(SqList &l,int m,int n){
RedType rc=l.r[m];//rc为要调整的数据
int j;
for(j=*m;j<=n;j=j*){ //接着调整互换下来的l.r[j],l.r[j]也要和他的孩子们满足堆的要求
if(j<n&&l.r[j].score<l.r[j+].score) j++;
if(l.r[j].score<rc.score) break; //此时要调整的数据l.rc满足堆的要求，故此数据不进行调整,调整下一个数据。
l.r[m]=l.r[j];
m=j;
} //for循环完毕，m最终定位到rc需要放置的位置
l.r[m]=rc;
}
/*
Name: 创建大顶堆+堆排序
Copyright: http://www.cnblogs.com/gangtiexia
Author: 钢铁侠
Date: 2015-12-12 21:05:14
Description: 创建堆的过程实质就是堆调整的过程，堆排序实质就是反复将堆的顶部元素移到末尾的过程
*/ Status HeapSort(SqList &l){
int i;
for(i=l.length/;i>=;i--){ //从最后一个非叶子节点开始调整每一个子树
HeapAdjust(l,i,l.length);
}
for(i=l.length;i>;i--)
{
RedType temp=l.r[];
l.r[]=l.r[i];
l.r[i]=temp;
HeapAdjust(l,,i-);
}
} Status Traverse(SqList &l){
for(int i=;i<=l.length;i++){
printf("\n第%d位同学为%s,分数为%d",i,l.r[i].name,l.r[i].score);
}
}
int main(){
SqList L;
initSqList(L);
HeapSort(L);
Traverse(L);
return ;
}