radixsort.h

八种排序算法

//基数排序
//算法思想:设待排序的数据元素关键字是.位d进制整数(不足m位的关键字在高位补0)，设置d个桶，令其编号分别为0,1,2……,d-1。
//首先按关键字最低位的数值依次把各数据元素放到相应的桶中,然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各
//桶中的数据元素，这样就形成了数据元素集合的一个新的排列,我们称这样的一次排序过程为一次基数排序;再对一次基数排序得到的数据
//元素序列按关键字次低位的数值依次把各数据元素放到相应的桶中然后按照桶号从小到大和进入同种数据元素的先后次序收集分配
//在各 桶中的数据元素;这样的过程重复进行,当完成了第m次基数排序后，就得到了排好序的数据元素序列
//
//算法实现如下(注包含LinQueue.h为链式队列类代码):
#include "LLinQueue.h"
void RadixSort(DataType a[],int n,int m,int d)
//对数据元素a[0]……a[n-1]进行关键吗为m位d进制整型数据的基数排序
//桶采用链式队列结构
{
	int i,j,k,power=1;
	LinQueue<DataType> *tub=new LinQueue <DataType> [d];
	//进行m次排序
	for(i=0;i<m;i++)
	{
		if(i==0)	power=1;
		else power=power*d;
		
		//将数据元素按关键码第k位的大小放到相应的队列中
		for(j=0;j<n;j++)
		{
			k=a[j].key/power-(a[j].key/(power*d))*d;
			tub[k].Append(a[j]);
		}
		//顺序回收各队列中的数据元素
		for(j=0,k=0;j<d;j++)
		{
			while (tub[j].NotEmpty())
			{
				a[k++]=tub[j].Delete();
			}
		}
	}
}