欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构堆排序

程序员文章站 2022-06-04 09:15:17
...

堆排序:将无序序列建成一个堆,得到关键字最小(或最大)的记录;输出堆顶的最小(大)值后,使剩余的n-1个元素重又建成一个堆,则可得到n个元素的次小值;重复执行,得到一个有序序列

数据结构堆排序

堆排序程序:

#include<stdio.h>  
#define SIZE 200  
typedef struct{  
int key;  
int next;  
}SLNOde;  
typedef struct{  
SLNOde r[SIZE];  
int length;  
}Sqlist;  
void Heapadjust(Sqlist &H,int s,int m)  
{  
SLNOde rc;  
int j;  
rc=H.r[s];  
for(j=2*s;j<=m;j*=2)  
{  
if(j<m&&H.r[j].key<H.r[j+1].key)  
++j;  
if(rc.key>H.r[j].key) break;  
H.r[s].key=H.r[j].key;  
s=j;  
}  
H.r[s]=rc;  
}  
void Heapsort(Sqlist &H)  
{  
int i,t;  
for(i=H.length/2;i>0;--i)  
Heapadjust(H,i,H.length);  
for(i=H.length;i>1;--i)  
{  
t=H.r[i].key;  
H.r[i].key=H.r[1].key;  
H.r[1].key=t;  
Heapadjust(H,1,i-1);  
}  
}  
void main()  
{  
int i;  
Sqlist H;  
printf("请输入待排序的总长度:\n");  
scanf("%d",&H.length);  
printf("请输入%d个数:\n",H.length);  
for(i=1;i<=H.length;i++)  
{  
scanf("%d",&H.r[i].key);  
}  
Heapsort(H);  
printf("输出堆排序后的序列:\n");  
for(i=1;i<=H.length;i++)  
{  
printf(" %d",H.r[i].key);  
}  
printf("\n");  
}