heapsort.h

各种排序方法源码

#include<string.h>
//----------------------------调大顶堆函数-------------------------------------------//
void heapadjust(node *d,int s,int m,int &jc,int &bc)
{//已知d[s...m]中记录的关键字除之d[s]外均满足堆的定义，本函数调整d[s]的关键字，使成为一个大顶堆
	node p;
	int j;
	p.data=d[s].data;
    strcpy(p.c,d[s].c);
	jc++;
	for(j=2*s;j<=m;j*=2)   //沿关键字较大的孩子结点向下筛选
	{
		bc++;
		if(j<m&&(d[j].data<d[j+1].data)) {j++;bc++;}  //j为关键字较大记录的下标
		if(p.data>=d[j].data) {bc++;break;}     //p应插入在位置s上
		d[s].data=d[j].data;
        strcpy(d[s].c,d[j].c);
		jc++;
		s=j;
	}
    d[s].data=p.data;       //插入
	strcpy(d[s].c,p.c);
	jc++;
}
//-------------------------------堆排序函数-----------------------------------------//
void heapsort(node *d,int num,int &jc,int &bc)
{//对顺序表d进行堆排序
	int i;
	node p;
	for(i=num/2;i>0;--i)    //把d建成大顶堆
	{
		bc++;
		heapadjust(d,i,num,jc,bc);
	}
	for(i=num;i>1;--i)
	{
		jc+=3;bc++;
		p.data=d[1].data;    //将堆顶记录和当前未经排序的1从i到的子列的最后一个记录交换
		strcpy(p.c,d[1].c);
		d[1].data=d[i].data;
        strcpy(d[1].c,d[i].c);
		d[i].data=p.data;
		strcpy(d[i].c,p.c);
		heapadjust(d,1,i-1,jc,bc);   //把d[1.....i-1]重新调整为大顶堆
	}
}