我正在根据 CLRS 在 C 中实现堆排序算法。但是我无法获得排序的输出。你能看看我的代码有什么问题吗?功能maxheap
和buildmaxheap
工作。我无法弄清楚代码有什么问题。
该代码应该对数组元素进行堆排序。heapsort()
我觉得函数中存在错误,因为maxheap
andbuildmaxheap
工作得很好。
我得到的最终输出是
1 1 1 1 2 1 2 2 1 1
但预期的输出应该是
1 2 3 4 7 8 9 10 14 16
编码:
#include<stdlib.h>
#include<stdio.h>
#define maxn 11
int n=10;
int parent(int i)
{
return i/2;
}
int left(int i)
{
return 2*i+0;
}
int right(int i)
{
return 2*i+1+0;
}
void max_heap(int x[],int i,int heapsize)
{
int largest;
int l=left(i);
int r=right(i);
if (l<=heapsize && x[l]>x[i]){
largest=l;
}
else
{
largest=i;
}
if (r<=heapsize && x[r]>x[largest]){
largest=r;
}
if (largest!=i)
{
int s=x[i];x[i]=x[largest];x[largest]=s;
max_heap(x,largest,heapsize);
}
}
void buildmaxheap(int x[],int heapsize)
{
int i;
for(i=5;i>=1;i--)
max_heap(x,i,heapsize);
}
void heapsort(int x[])
{
buildmaxheap(x,10);
int i,t,heapsize=10;
for(i=10;i>=2;i--)
{
int s=x[i];x[1]=x[i];x[i]=s;
heapsize--;
/*
printf("%d",heapsize);
*/
max_heap(x,i,heapsize);
}
for(i=1;i<=10;i++)
printf("%d\t",x[i]);
}
int main()
{
int x[maxn],i;
x[1]=16;
x[2]=4;
x[3]=10;
x[4]=14;
x[5]=7;
x[6]=9;
x[7]=3;
x[8]=2;
x[9]=8;
x[10]=1;
heapsort(x);
/*
for(i=1;i<=10;i++)
printf("%d\t",x[i]);
*/
}