大家帮我看看这个c语言程序,关于堆排序的

2025-05-21 17:27:25
推荐回答(1个)
回答(1):

#include
#define N 100
int b[N];//用b[]存放剔出的最大值。
void max_heapify(int *a,int i,int n)//从某结点开始往下进行“堆化简”。
{
 int l=2*i+1;
 int r=2*i+2;
 int largest=0;
 if(l<=n&&a[l]>a[i])
 largest=l;
 else largest=i;
 if(r<=n&&a[r]>a[largest])
  largest=r;
 if(largest!=i)
 {
  int tmp=a[i];
 a[i]=a[largest];
 a[largest]=tmp;
max_heapify(a,largest,n);
 }
}
void build_maxheap(int *a,int n)//创建最大堆。
{
 int i;
 for(i=n/2-1;i>=0;i--)
  max_heapify(a,i,2*i+2);
}
void heapsort(int *a,int n)//堆排序。

 build_maxheap(a,n);
  int i,j=0;
 for(i=n;i>=1;i--)
 {
  b[j++]=a[0];
  int tmp=a[0];
  a[0]=a[i];
  a[i]=tmp;
 n=n-1;
 max_heapify(a,0,n);
}
}
int main()
{
 int a[]={3,-5,6,2,87,54,23,65,11,98};
 int i;
 for(i=0;i<10;i++)
  printf("%d ",a[i]);
 heapsort(a,10);
 printf("\n");
 for(i=9;i>=0;i--)
  printf("%d ",b[i]);
 return 0;
}