排序常用算法设计(4)

25.设向量A[0..n-1]中存有n个互不相同的整数，且每个元素的值均在0到n-1之间。试写

一时间为O(n)的算法将向量A排序，结果可输出到另一个向量B[0..n-1]中。

答： sort(int *A,int *B)

{//将向量A 排序后送入B 向量中 int i;

for(i=0;i<=n-1;i++) B[A[i]]=A[i]; }

*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

for(i=KeySize-1;i>=0;i--){//从低位到高位做d 趟箱排序 课后答案网 www.khdaw.com 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;i26)

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

R[i++]=DeQueue(&B[j]);//将出队记录依次输出到R[i]中 }