设计一个将一组英文单词按字典序排列的基数排序算法。设单词均由小写字母或空格构成，最长的单词有n个字母
简单说下思路吧。先有26个指针数组，分别对应单词的第一位的a-z，这个指针指向另一个指针数组，对应单词的第二位字母（这层的数组最多可能有26个）。以此类推，直到最后直接指向单词。
/********************************************************
*函数名称：GetNumInPos
*参数说明：num 一个整形数据
pos 表示要获得的整形的第pos位数据
说明： 找到num的从低到高的第pos位的数据
********************************************************/
int GetNumInPos(int num,int pos)
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
/********************************************************
*函数名称：RadixSort
*参数说明：pDataArray 无序数组；
iDataNum为无序数据个数
说明： 基数排序
********************************************************/
#define RADIX_10 10 //整形排序
#define KEYNUM_31 10 //关键字个数，这里为整形位数
void RadixSort(int* pDataArray, int iDataNum)
{
int *radixArrays[RADIX_10]; //分别为0~9的序列空间
for (int i = 0; i < 10; i++)
{
radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
radixArrays[i][0] = 0; //index为0处记录这组数据的个数
}
for (int pos = 1; pos <= KEYNUM_31; pos++) //从个位开始到31位
{
for (int i = 0; i < iDataNum; i++) //分配过程
{
int num = GetNumInPos(pDataArray[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = pDataArray[i];
}
for (int i = 0, j =0; i < RADIX_10; i++) //收集
{
for (int k = 1; k <= radixArrays[i][0]; k++)
pDataArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0; //复位
}
}
}
直接调用就行了
26.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。
答：
#define KeySize 10 //设关键字位数d=10
#define Radix 27 //基数rd为27
typedef RecType DataType;//将队列中结点数据类型改为RecType类型
typedef struct node{
char key[KeySize]; //关键字域
OtherInfoType info; //其它信息域，
}RecType; //记录结点类型
typedef RecType seqlist[n+1];
void RadixSort(seqlist R)
{
LinkQueue B[Radix];
int i;
for(i=0;i InitQueue(&B[i]);
for(i=KeySize-1;i>=0;i--){//从低位到高位做d趟箱排序
Distribute(R,B,i);//第KeySize-i趟分配
Collect(R,B);//第KeySize-i趟收集
}
}
void Distribute(seqlist R,LinkQueue B[], int j)
{//按关键字的第j个分量进行分配，初始时箱子为空
int i;
j=KeySize-j; // 确定关键字从低位起的位置
for(i=0;i if (R[i].key[j]-'A'>26)
EnQueue(&B[0],R[i]);//将第j位关键字位空格的记录入第0个队列
else EnQueue(&B[0],R[R[i].key[j]-'A'+1]);
}
void Collect(seqlist R,LinkQueue B[])
{
//依次将各非空箱子中的记录收集起来，本过程结束，各箱子都变空
int i,j;
for (j=0;j<Radix;j++)
while(!QueueEmpty(&B[j]))
R[i++]=DeQueue(&B[j]);//将出队记录依次输出到R[i]中
}