堆排序.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵
void Heapify(SeqList R,int low,int high);
void BuildHeap(SeqList R);

void main()
{
	void HeapSort(SeqList R);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	HeapSort(R);
	printf("排序后：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

void HeapSort(SeqList R)
{	//对R[1..n]进行堆排序，不妨用R[0]做暂存单元
	int i;
	BuildHeap(R);						//将R[1..n]建成初始堆
	for(i=n;i>1;i--) {					//对当前无序区R[1..i]进行堆排序，共做n-1趟
		R[0]=R[1];R[1]=R[i];R[i]=R[0];	//将堆顶和堆中最后一个记录交换
		Heapify(R,1,i-1);				//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
	}
}

void Heapify(SeqList R,int low,int high)
{	//将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质
	int large;		//large指向调整结点的左、右孩子结点中关键字较大者
	RecType temp=R[low];					//暂存调整结点
	for(large=2*low;large<=high;large*=2){	//R[low]是当前调整结点
	//若large>high，则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子
		if(large<high && R[large].key<R[large+1].key)
			large++;						//若R[low]的右孩子存在且关键字大于左兄弟，
		//则令large指向它。现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者
		if(temp.key>=R[large].key)			//temp始终对应R[low]
			break;					//当前调整结点不小于其孩子结点的关键字，结束调整
		R[low]=R[large];					//相当于交换了R[low]和R[large]
		low=large;				//令low指向新的调整结点，相当于temp已筛下到large的位置
	}
	R[low]=temp;							//将被调整结点放入最终的位置上
}

void BuildHeap(SeqList R)
{	//将初始文件R[1..n]构造成大根堆
	int i;
	for(i=n/2;i>0;i--)
		Heapify(R,i,n);						//将R[i..n]调整为堆
}