treesort.h

各种排序方法源码

#include<string.h>
#define maxint 0x7fffffff    //整型最大值
//--------------------------------建立初始排序树函数-----------------------------------//
void treejust(node **t,node *d,int i,int num,int &jc,int &bc)
{//以d中数据建立最初的排序树，，除叶子结点外，树的第i层存储在t[i]中
	int p=num,j=i,k;
	if(p%2==1) {p--;bc++;}
    for(k=1;k<=p-1;k+=2)      //处理最后一层叶子结点，存储在d中
	{  
		if(d[k].data>d[k+1].data)    //将较小的结点上虑
		{
			jc++;bc++;        
			t[j][(k+1)/2].data=d[k+1].data;
            strcpy(t[j][(k+1)/2].c,d[k+1].c);
		}
		else
		{
            jc++;
			t[j][(k+1)/2].data=d[k].data;
            strcpy(t[j][(k+1)/2].c,d[k].c);
		}
		bc++;
	}
	if(num%2==1)  //奇数个数据，将上一层最后一个父结点直接赋值为叶子结点
	{
		jc++;bc++;
		t[j][(k+1)/2].data=d[num].data;
		strcpy(t[j][(k+1)/2].c,d[num].c);
		p=p/2+1;
	}
	else p=p/2;
	for(j=i-1;j>=1;--j)  //从t[j+1]层上虑到根结点
	{
		bc++;
		if(p%2==1) {p++;bc++;}
		for(k=1;k<=p-1;k+=2)    //处理第j层
		{
			bc++;
			if(t[j+1][k].data>t[j+1][k+1].data)  //将较小的结点上虑
			{
				jc++;bc++;
				t[j][(k+1)/2].data=t[j+1][k+1].data;
				strcpy(t[j][(k+1)/2].c,t[j+1][k+1].c);
			}
			else
			{
				jc++;
				t[j][(k+1)/2].data=t[j+1][k].data;
				strcpy(t[j][(k+1)/2].c,t[j+1][k].c);
			}
			bc++;
		}
		p=p/2;
	}
}
//------------------------------锦标赛排序函数--------------------------------------------//
void treesort(node *&d,node *r,int num,int &jc,int &bc)
{//将顺序表d中数据按树形选择进行排序
	int i,k,j=num,p;
	node **t;   //树形数组,t[i]对应第树的第i层
	int sum=1,s=1;
	if(num<=1) return;
	for(i=0;sum<num;++i)  //求得树的层数,0号单元未用 
	{
		bc++;
		sum*=2;
	}
	t=(node **)malloc((i+1)*sizeof(node*));
	for(k=i;k>=1;--k)   //为树形数组分配空间，若哪一层是奇数个结点，则补一个结点使成为偶数
	{                   //并使得多分配的结点数值为无穷大
		bc++;
		if(j%2==0)       //树的下一层为偶数个结点
		{
			bc++;
			if((j/2+1)%2==0)   //奇数个结点
			{
				bc++;
				j=j/2+1;
				t[k]=(node *)malloc((j+1)*sizeof(node));
				t[k][j].data=maxint;   //赋结点值为无穷大
			}
			else              //偶数个结点
			{
				j=j/2;
				t[k]=(node *)malloc((j+1)*sizeof(node));
			}
		}
		else            //树的下一层为奇数个结点
		{
			if(((j+1)/2)%2==0)       
			{
				bc++;
				j=(j+1)/2;
               	t[k]=(node *)malloc((j+1)*sizeof(node));
				
			}
			else
			{
				j=(j+1)/2+1;
                t[k]=(node *)malloc((j+1)*sizeof(node));
				t[k][j].data=maxint;
			}
		}
	}
	treejust(t,d,i,num,jc,bc);   //建立初始排序树
	for(j=1;j<=num;++j)    //依次求得最小值
	{
		jc++;
        r[j].data=t[1][1].data;    //将最小的值(树根)移到r[j]中
		strcpy(r[j].c,t[1][1].c);
		s=1;
		for(k=1;k<=i-1;++k)     //沿树根找到删除树根原出处
		{
			bc++;
			if(t[k+1][2*s-1].data==t[1][1].data)
			{s=2*s-1;bc++;}
			else if(t[k+1][2*s].data==t[1][1].data)
			{s*=2;bc++;}
			else break;   //都为无穷，跳出
		}
		if(k==i)   //处理最低层原始数组
		{
			bc++;
			if(d[2*s-1].data==t[1][1].data)
			{
				bc++;
				d[2*s-1].data=maxint;   //将已经删除的元素赋为无穷大
				if(2*s-1!=num)     //初始数据元素为奇数个，将其父结点直接赋值为无穷大
				{      
					bc++;jc++;
					t[k][s].data=d[2*s].data;  //将偶数结点上虑
					strcpy(t[k][s].c,d[2*s].c);
				}
				else t[k][s].data=maxint;
			}
			else if(d[2*s].data==t[1][1].data)
			{
				bc++;jc++;
				d[2*s].data=maxint;
				t[k][s].data=d[2*s-1].data;        //将数奇数结点上虑
				strcpy(t[k][s].c,d[2*s-1].c);
			}
		}
		else         //两个孩子结点都已经为无穷大
		{
			t[k][s].data=maxint;
		}
		for(p=k;p>=2;--p)          //修改已删除结点到根结点路径上的关键字
		{
			bc++;
			if(s%2==1){s++;bc++;}         //奇数改为偶数
			if(t[p][s-1].data>t[p][s].data)   //将较小的结点上虑
			{  
				bc++;jc++;
				t[p-1][s/2].data=t[p][s].data;
				strcpy(t[p-1][s/2].c,t[p][s].c);
			}
			else
			{
				jc++;
				t[p-1][s/2].data=t[p][s-1].data;
				strcpy(t[p-1][s/2].c,t[p][s-1].c);
			}
			s=s/2;
		}
	}
	free(d);  //释放d
	free(t);  //释放t
	d=r;     //修改d指向的空间
}