radix.h

各种排序方法源码

#include<string.h>
//--------------------------关键字映射函数------------------------------------//
int ord(int p,int i,node *d)
{//将d[p]中第i个关键字映射到[0...9]
	int sum=1,k,s;
	for(k=0;k<i;++k)
		sum*=10;
	if(d[p].data<sum)
		return(0);
	else 
	{
		s=d[p].data%(sum*10);
		return(s/sum);
	}
}
//-----------------------------基数排序分配函数----------------------------------//
void distribute(int *r,int i,int *f,int *e,node *d)
{//按第i个关键字建立RADIX各个子表，使同一子表中记录的第i个关键字相同
	int j,p,tag=1;
	for(j=0;j<10;++j)  //各个子表初始化为空表
	{
		f[j]=0;
	}
	for(p=r[0];p;p=r[p])
	{
		j=ord(p,i,d);    //ord将记录中第i个关键字映射到[0...9]
		if(tag<j) tag=j;
		if(!f[j]) f[j]=p;
		else r[e[j]]=p;
		e[j]=p;     //将p所指结点插入到第j个子表中
	}
	r[e[tag]]=0;
}
//-----------------------------基数排序收集函数----------------------------------//
void collect(int *r,int i,int *f,int *e)
{//按第i个关键字自小至大地将f[0...9]所指各个子表依次链接成一个链表
	int j,t;
	for(j=0;!f[j];++j);  //找到第一个非空子表
	r[0]=f[j];     //r[0]指向第一个非空子表中第一个结点
	t=e[j++];
	while(j<10)
	{
		for(;j<9&&!f[j];++j);  //找下一个非空子表
		if(f[j])   //链接两个非空子表
		{
			r[t]=f[j];
			t=e[j++];
		}
		else j++;
	}
	r[t]=0;   //t指向最后一个非空子表中的最后一个结点
}
//-------------------------------------基数排序函数-------------------------------------//
void radixsort(node *d,int num,int *r,int max)
{//d是顺序表，对d作基数排序，其顺序号存储于r数组中，r[0]为头结点
	int *f,*e;
	int i,n=0;
	while(max>0)   //求得所有数据中最大值对应位数
	{
      max/=10;
	  n++;
	}
	f=(int*)malloc(10*sizeof(int));//f[0...9]指向各个子表的第一个记录
	e=(int*)malloc(10*sizeof(int));//e[0...9]指向各个子表的第一个记录
	for(i=0;i<num;++i)   //将r改为d的静态指针
	{
		r[i]=i+1;
	}
    r[i]=0;
	for(i=0;i<n;++i)  //按最低位优先依次对各个关键字进行分配和收集
	{
		distribute(r,i,f,e,d);  //第i趟分配
		collect(r,i,f,e);       //第i趟收集
	}
	free(f);      //空间释放
	free(e);      //空间释放
}