heapsort.cpp

从最后一个非叶子结点开始从后往前进行调整

#include <stdio.h>
#define MAXSIZE 20 
typedef struct 
{int elemword[MAXSIZE]; 
int length; 
}SqList;
SqList L;
void InitialSqList(SqList &L)
{
int i;
printf("Please intput ordering Number:");
scanf("%d",&L.length);
printf("Please intput Ordering Number Value:\n");
for(i=1;i<=L.length;i++)
scanf("%d",&L.elemword[i]);
}
void HeapAdjust(SqList &H,int s,int m)
{
int j,i;
i=H.elemword[s];
for(j=2*s;j<=m;j*=2)
{if(j<m&&H.elemword[j]<H.elemword[j+1]) 
++j; 
if(i>=H.elemword[j]) 
break; 
H.elemword[s]=H.elemword[j];
s=j;
}
H.elemword[s]=i; 
}
void HeapSort(SqList &L)
{
int i,t;
for(i=L.length/2;i>0;--i) 
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;--i)
{t=L.elemword[1]; 
L.elemword[1]=L.elemword[i]; 
L.elemword[i]=t;
HeapAdjust(L,1,i-1); 
}
}

void PrintSqList(SqList L)
{
int i;
printf("Ordering Result：\n");
for(i=1;i<=L.length;i++)
printf("%4d",L.elemword[i]);
printf("\n");
}
void main()
{ 
InitialSqList(L); 
HeapSort(L); 
PrintSqList(L); 
}