the improvement of heapsort.cpp

完成堆排序的改进算法

#include <iostream.h>
#include <math.h>
void main()
{int number;
 cout<<"请输入要排序的数组元素的个数:";
 cin>>number;
 int *data=new int[number+1];           //运用数组指针
 void input(int *,int );                //输入函数声明
 void optimalheapsort(int *,int );      //堆排序的改进函数声明
 void output(int *,int );               //输出函数声明
 input(data,number);
 optimalheapsort(data,number);
 output(data,number);
 delete data;                           //回收数组指针
}


void input(int *A,int n)                 //输入函数定义
{cout<<"请输入这"<<n<<"个元素:"<<endl;
 for (int i=1;i<=n;i++)
 	 cin>>A[i];
 cout<<endl;   
}


void optimalheapsort(int *A,int n)        //堆排序改进过程
{
 void buildheap(int *,int);
 void heapfify(int *,int,int,int);
 void rebuildheap(int *,int,int,int,int);
 buildheap(A,n);                           //调用建堆过程
 for (int j=n;j>=3;j--)
 {int temp=A[1];             
  int h=int (log(j-1)/log(2));             //h为树高，强制转化为整型
  int i=1;
  rebuildheap(A,n,i,(j-1),h);
  A[j]=temp;
 }
 int t=A[1];
 A[1]=A[2];
 A[2]=t;
}


void heapfify(int *B,int m,int x,int y)     //将数组B[x]-B[y]建成堆
{if ((2*x+1<=m) && ((B[2*x]>B[x]) || (B[2*x+1]>B[x])))
                                 //两个儿子有比自身大时取其大者
{int k=2*x;
 if (B[2*x+1]>B[2*x])  
	 k=2*x+1;
 int t=B[x];
 B[x]=B[k];
 B[k]=t;
 heapfify(B,m,k,y);
}
else if ((2*x==m) && (B[2*x]>B[x])) 
                                //只有一个儿子且比自身大时取其儿子
{int k=2*x;
 int t=B[x];
 B[x]=B[k];
 B[k]=t;
 heapfify(B,m,k,y);
}
return;
}


void buildheap(int *B,int m)                 //将数组B[1]-B[m]建成堆
{for (int i=m/2;i>=1;i--)
      heapfify(B,m,i,m);
}


void rebuildheap(int *B,int m,int x,int y,int h1)  
                                             //重整数组B[x]-B[y]为堆
{
	if (h1==1)   {B[x]=B[y+1];               //当高度为1时整堆
              heapfify(B,y,x,y);}
else  {int count=1;
       while (count++<=h1/2)                 //左右儿子作一次比较，
		        //大者上升一层的过程只进行到当前堆的第h/2层的某结点处
	   {int k=2*x;
	    if (B[2*x+1]>B[2*x])
			k=2*x+1;
		B[x]=B[k];
		x=k;
	   }
	   if (B[y+1]>=B[x/2])     //B[y+1]在当前子堆中上升到某一合理位置
	   {B[x]=B[y+1];
	    while (B[x]>B[x/2]) 
		{int t=B[x];
		 B[x]=B[x/2];
		 B[x/2]=t;
		 x=x/2;
		}
	   }
	   else                     //递归地重新堆化当前子堆
	   {h1=h1-h1/2;
	    rebuildheap(B,m,x,y,h1);
	   }
}
}


void output(int *A,int n)         //输出函数定义
{cout<<"排完序后的数组为:"<<endl;
 for (int i=1;i<=n;i++)
	 cout<<A[i]<<",";
 cout<<endl;
}