heapsort.h

八种排序算法

//堆排序
//要进行堆排序首先要创建堆，详细算法思想见SelectSort.h
//算法实现
void CreatHeap(DataType a[],int n,int h)
//创建堆
{
	int i,j,flag;
	DataType temp;

	i=h;				//i为要创建堆的二叉树根结点下标
	j=2*i+1;			//j为i的左孩子结点的下标
	temp=a[i];
	flag=0;
	//延左右孩子中值较大者重复向下筛选
	while(j<n&&flag!=1)
	{
		if(j<n-1&&a[j].key<a[j+1].key)	j++;
		
		if(temp.key>a[j].key)			//a[i].key>a[j].key
			flag=1;						//标记结束筛选条件
		else							//否则把a[j]上移
		{
			a[i]=a[j];
			i=j;
			j=2*i+1;
		}
	}
	a[i]=temp;							//把最初的a[i]赋予最后的a[j]

}


void InitCreatHeap(DataType a[],int n)		//初始化最大堆
{
	int i;
	for(i=(n-1)/2;i>=0;i--)
	{
		CreatHeap(a,n,i);
	}
}


void HeapSort(DataType a[],int n)
{
	int i;
	DataType temp;

	InitCreatHeap(a,n);			//init creat 最大堆

	for(i=n-1;i>0;i--)			//当前最大堆个数每次递减1
	{
		
		//把顶堆a[0]元素和当前最大堆的最后一个元素交换
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;


		CreatHeap(a,i,0);		//调整根节点满足最大堆
		
	}
}