duipaixu.cpp

通过建立大顶堆 建立堆排序 以从小到大的顺序输出结果

#include"iostream"
#include"stdio.h"
#include"cstdlib"


#define error 0
#define ok 1

using namespace std;


int j;


int MAX_HEAPIFY(int str[],int i,int heapsize)//维护堆
{
	int l=2*i;
	int r=2*i+1;
	int largest;
	if((l<=heapsize)&&(str[l]>str[i]))
		 largest=l;
	else  largest=i;
	if((r<=heapsize)&&(str[r]>str[largest]))
		largest=r;
	if(largest!=i) 
	{
		int q=str[i];
		str[i]=str[largest];
		str[largest]=q;
	    MAX_HEAPIFY(str,largest,heapsize);
	}
	return ok;
}


int BUILD_MAX_HEAP(int str[],int heapsize)//建堆
{
	for(int i=(int)(heapsize/2);i>=1;i--)
		MAX_HEAPIFY(str,i,heapsize);
	return ok;
}

int HEAPIFYSORT(int str[],int heapsize)//堆排序
{
	BUILD_MAX_HEAP(str,heapsize);
	j=1;
	for(int i=heapsize;i>=1;i--)
	{
		cout<<"第"<<j<<"次堆排序的堆顶元数是"<<str[1]<<endl;
		int p=str[1];
		str[1]=str[i];
		str[i]=p;
		j++;
		MAX_HEAPIFY(str,1,--heapsize);
	}
	return ok;
}


int main()
{
	int max,*str;
	cout<<"请输入需要排序的元素数"<<endl;
	cin>>max;
	str=(int *)malloc((max+1)*sizeof(int));
	cout<<"请输入需要排序元素"<<endl;
	for(int i=1;i<=max;i++)
		cin>>str[i];

	HEAPIFYSORT(str,max);
	cout<<"堆排序的结果是";
	for(int i=1;i<=max;i++)
		cout<<str[i]<<' ';
	return 0;
}