l9_7.cpp

《数据结构（C++描述）》-李根强-源代码

//堆排序
#include<iostream.h>
typedef int ElemType;
const int n=10;
ElemType a[n]={2,6,4,8,10,7,1,5,3,9};
void creatheap(ElemType R[],int i,int n)
{ int j;ElemType t;
 t=R[i];j=2*i;
 while(j<n)
 { if((j<n)&&(R[j]<R[j+1]))
   j++;
   if(t<R[j])
   { R[i]=R[j];
      i=j;
	  j=2*i;
   }
	else j=n;
	R[i]=t;
   }
}

void heapsort(ElemType R[],int n)
{ ElemType t;
  for(int i=n/2;i>=0;i--)
	  creatheap(R,i,n);
  for(i=n-1;i>=0;i--)
  {t=R[0];
   R[0]=R[i];
   R[i]=t;
   creatheap(R,0,i-1);
  }
}

void print(ElemType r[n])
{ int i;
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
void main()
{ cout<<endl<<"排序前的结果为:"<<endl;
 print(a);
 heapsort(a,n);
 cout<<endl<<"排序后的结果为:"<<endl;
print(a);
}