数据结构堆排序
程序员文章站
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");
}