基数排序

[c]代码库

#define MAX_KEY_NUM 8 /*关键码项数最大值*/
#define RADIX 10 /*关键码基数，此时为十进制整数的基数*/
#define MAX_SPACE 1000 /*分配的最大可利用存储空间*/
typedef struct
{
	KeyType keys[MAX_KEY_NUM]; /*关键码字段*/
	InfoType otheritems; /*其它字段*/
	int next; /*指针字段*/
} NodeType; /*表结点类型*/
typedef struct
{
	NodeType r[MAX_SPACE]; /*静态链表，r[0]为头结点*/
	int keynum; /*关键码个数*/
	int length; /*当前表中记录数*/
} L_TBL; /*链表类型*/
typedef int ArrayPtr[radix]; /*数组指针，分别指向各队列*/
void Distribute ( NodeType *s，int i，ArrayPtr *f，ArrayPtr *e )
{ /*静态链表ltbl 的r 域中记录已按(kye[0]，keys[1]，…，keys[i-1])有序)*/
	/*本算法按第i 个关键码keys[i]建立RADIX 个子表，使同一子表中的记录的keys[i]相同*/
	/*f[0…RADIX-1]和e[0…RADIX-1]分别指向各子表的第一个和最后一个记录*/
	for ( j=0; j<RADIX; j++ ) f[j]=0; /* 各子表初始化为空表*/
	for ( p=r[0].next; p; p=r[p].next )
	{
		j=ord ( r[p].keys[i] ); /*ord 将记录中第i 个关键码映射到[0…RADIX-1]*/
		if ( !f[j] ) f[j]=p;
		else r[e[j]].next=p;
		e[j]=p; /* 将p 所指的结点插入到第j 个子表中*/
	}
}
void Collect ( NodeType *r，int i，ArrayPtr f，ArrayPtr e )
{/*本算法按keys[i]自小到大地将f[0…RADIX-1]所指各子表依次链接成一个链表*e[0…RADIX-1]为各子表的尾指针*/
	for ( j=0; !f[j]; j=succ ( j ) ); /*找第一个非空子表，succ 为求后继函数*/
	r[0].next=f[j];
	t=e[j]; /*r[0].next 指向第一个非空子表中第一个结点*/
	while ( j<RADIX )
	{
		for ( j=succ ( j ); j<RADIX-1&&!f[j]; j=succ ( j ) ); /*找下一个非空子表*/
		if ( f[j] ) {r[t].next=f[j]; t=e[j];} /*链接两个非空子表*/
	}
	r[t].next=0; /*t 指向最后一个非空子表中的最后一个结点*/
}
void RadixSort ( L_TBL *ltbl )
{ /*对ltbl 作基数排序，使其成为按关键码升序的静态链表，ltbl->r[0]为头结点*/
	for ( i=0; i<ltbl->length; i++ ) ltbl->r[i].next=i+1;
	ltbl->r[ltbl->length].next=0; /*将ltbl 改为静态链表*/
	for ( i=0; i<ltbl->keynum; i++ ) /*按最低位优先依次对各关键码进行分配和收集*/
	{
		Distribute ( ltbl->r，i，f，e ); /*第i 趟分配*/
		Collect ( ltbl->r，i，f，e ); /*第i 趟收集*/
	}
}