radixsort.cpp

各种内部排序算法的实现和比较

#include "base.h"

int ord(char c)
{//返回k的映射(个位整数)
   return c-'0';
}

void Distribute(SLCell r[],int i,ArrType &f,ArrType &e)
{//静态键表L的r域中记录已按(keys[0],...,keys[i-1])有序.本算法按
 //第i个关键字keys[i]建立RADIX个子表,使同一子表中记录的keys[i]相同
 //f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录
	int j,p;
	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个子表中
	}
}

int succ(int j)
{//求后继函数
	j=j+1;
	return j;
}

void Collect(SLCell r[],int i,ArrType &f,ArrType &e)
{//本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
 //一个链表,e[0..RADIX-1]为各子表的尾指针.
	int j,t;
	for(j=0;!f[j];j=succ(j))
		;								//找第一个非空子表，succ为求后继函数
	r[0].next=f[j];
	t=e[j];								//r[0].next指向第一个非空子表中第一个结点
	while(j<RADIX-1)
	{
		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(SLList &SLL)
{//L是采用静态链表表示的顺序表.对L作基数排序,使得L成为按关键字
 //自小到大的有序静态链表,L.r[0]为头结点.
	int i;
	ArrType f,e;
	for(i=0;i<SLL.recnum;i++)
		SLL.r[i].next=i+1;
	SLL.r[SLL.recnum].next=0;			//将L改造为静态链表
	for(i=0;i<SLL.keynum;i++)
	{//按最低位优先依次对各关键字进行分配和收集
		Distribute(SLL.r,i,f,e);			//第i趟分配
		Collect(SLL.r,i,f,e);				//第i趟收集
   }
 }