sort.cpp

这是一个用堆排序实现的排序算法

#include <iostream.h>
const int N=11;
class sort
{
public:
void setnumber();           //输入关键字
void putnumber();           //输出关键字
void heapsort();            //堆排序
void built_heap();          //建立一个大顶堆
private:
int num[N];
int heap_size;
void heapify(int i);
};
int main()
{
sort a;
a.setnumber();
a.built_heap();
a.heapsort();
a.putnumber();

return 0;
}
void sort::setnumber()
{
int i;
cout<<"Please input "<<N-1<<" integers:\n";    //提示输入
for(i=1;i<N;i++)
{
cin>>num[i];
}
}
void sort::putnumber()                   //输出
{
int i;
for(i=1;i<N;i++)
{
cout<<num[i]<<" ";
}
cout<<endl;
}
void sort::heapify(int i)
{
int largest=i;
if(2*i<=heap_size&&num[i]<num[2*i]) //将左子的值暂时定为largest
   {
   largest=2*i;
   }
else
   {
   largest=i;
   }
if(2*i+1<=heap_size&&num[largest]<num[2*i+1]) //将右子的值暂时定为largest
   {
   largest=2*i+1;
   }
if(largest!=i)
   {
   num[0]=num[i];
   num[i]=num[largest];
   num[largest]=num[0];
   heapify(largest);
   }
}
void sort::built_heap()
{
int i;
heap_size=N-1;
for(i=heap_size/2;i>0;i--)               //从最后一个非叶子结点开始
{
heapify(i);
}
}
void sort::heapsort()
{
int i;
for(i=heap_size;i>=2;i--)
{
num[0]=num[1];   //交换num[1] 和 num[heap_size]
num[1]=num[i];
num[i]=num[0];
heap_size--;
heapify(1);
}
}