heapsort.cpp

堆排序算法C++源码

#include<iostream.h>
#include<string.h>
//////////////////////////////////////////////////////////
void DeleteMax(int *H,int curloc,int n);
void FixHeap(int *H,int curloc,int k,int n);
void Construct(int *H,int curloc,int n);
void HeapSort(int *H,int n,int *E);
//////////////////////////////////////////////////////////
//恢复堆（大堆）
//数组H中存放了n个任意的整数元素
//参数r(curloc)指示当前空位（根节点），
void FixHeap(int *H,int curloc,int k,int n)
{
	int i=curloc;//用于递归时使用，指示当前被移走了的节点的位置
	int maxchild;//左右儿子中较大者
	int flag;//标记较大者，=0表示左儿子，=1表示右儿子
	
	if(2*curloc>n)
	{//当前空位处为叶节点
		H[curloc]=k;
		return;
	}
	//找出左右儿子较大者赋给maxchild并用i记下其位置
	else if(2*curloc+1>n)
	{//无右儿子
		maxchild=H[2*i];
		flag=0;
	}
	else
	{
		if(H[2*i]>=H[2*i+1])
		{//左儿子较大
			maxchild=H[2*i];
			//i=2*i;//空位可能会变成当前值（与k比较）
			flag=0;
		}
		else
		{//右儿子较大
			maxchild=H[2*i+1];
			//i=2*i+1;//空位可能会变成当前值（与k比较）
			flag=1;
		}
	}


	if(maxchild>k)
	{//空位向下移动一个位置
		H[curloc]=maxchild;
		FixHeap(H,2*i+flag,k,n);
	}
	else
	{
		H[curloc]=k;
		return;
	}
}





//构造一个大堆
void Construct(int *H,int curloc,int n)
{
	int k;
	if(2*curloc>n)
	{//该节点是叶子节点
		return;
	}

	else
	{
		Construct(H,2*curloc,n);//构造左子树
		if(2*curloc+1<=n)//若右儿子存在
			Construct(H,2*curloc+1,n);
		k=H[curloc];
		FixHeap(H,curloc,k,n);
	}
}






void HeapSort(int *H,int n,int*E)
{
	Construct(H,1,n);
	for(int i=n;i>0;i--)
	{
		int curMax=H[1];
		E[i]=curMax;
		DeleteMax(H,1,i);
	}
}

void DeleteMax(int *H,int curloc,int n)
{
	int k=H[n];//将H最下层的最后一个节点中的元素复制到k中
	n=n-1;//删除最后一个元素
	FixHeap(H,curloc,k,n);
}


int main()
{
	int *H;
	int *E;
	int *HH;
	int n;
	int i;
	cout<<"input the number of element:";
	cin>>n;
	H=new int[n+1];
	HH=new int[n+1];
	E=new int[n+1];
	cout<<"input "<<n<<" elements to sort\n";
	
	for(i=1;i<=n;i++)
		cin>>H[i];
	
	

	cout<<"before sort"<<endl;
	for(i=1;i<=n;i++)
		cout<<H[i]<<" ";
	cout<<endl;

	for(i=1;i<=n;i++)
		HH[i]=H[i];	
	

	Construct(HH,1,n);
	cout<<"after construct initial heap"<<endl;
	for(i=1;i<=n;i++)
		cout<<HH[i]<<" ";
	cout<<endl;

	HeapSort(H,n,E);
	cout<<"atfer HeapSort"<<endl;
	for(i=1;i<=n;i++)
		cout<<E[i]<<" ";
	cout<<endl;
	cout<<"hello\n";
	return 0;
}