null8.6 基数排序8.6 基数排序 8.6.1 基数排序的基本思想
基数排序是一种基于多关键字的排序
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。
1. 多关键字排序
【举例】 将表8-1所示的学生成绩单按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成绩的高低等级排序。
nullnull排序结果如表8-2所示。null 与前面几节所讲述的排序不同，在这个排序中，每个学生
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
最终的位置由两个关键字决定。第1关键字为数学成绩k1，第二个关键字为英语成绩k2，则排序后每一个学生成绩记录的位置由关键字k1 k2决定，我们将它称之为复合关键字，即多关键字排序是按照复合关键字的大小排序。
现在我们讨论一下多关键字排序的方法。下面我们以学生成绩单为例，给出通常采用的两种方法。第一种方法是先按数学等级由高到低将学生记录分成A、B、C、D、E五个子序列，然后再分别对每个子序列按英语成绩由高到低排序，这样就会得到一个优先按数学等级排序，在数学等级相同的情况下，再按英语等级排序；第二种方法是先将学生记录按英语等级由高到低分成A、B、C、D、E 五个组：null表 8-3null 然后按从左向右，从上向下的顺序将它们收集起来得到关键字序列：
AA，EA，AB，BB，CB，DB，BC，CD
再按数学成绩由高到低分成A、B、C、D、E五个组：
表 8-4null 再按由高到低的顺序将它们收集起来，得到关键字序列：
AA，AB，BB，BC，CB，CD，DB，EA
可以看出，这个关键字序列已经是有序的了。
在上述两种基于多关键字的排序方法中，第一种方法是先按高位关键字进行排序，被称之为“最高位优先”法，简称MSD法；第二种方法是先按低位关键字排序，被称之为“最低位优先”法，简称为LSD。从上面的例子可以看出：在MSD法中，先按高位关键字将待排序数据分成子序列，然后再对各子序列按下一个关键字排序；而使用LSD法进行排序时，对每个关键字都是将整个序列按关键字分组，然后按顺序收集，显然LSD法，操作比较简单。
null 2. 基数排序
基数排序是借助于多关键字排序思想进行排序的一种排序方法。该方法将排序关键字K看作是由多个关键字组成的组合关键字，即K=k1k2…kd。每个关键字ki表示关键字的一位，其中k1为最高位，kd为最低位，d为关键字的位数。例如，对于关键字序列（101，203 567，231，478，352），可以将每个关键K看成由三个单关键字组成，即K= k1k2k3，每个关键字的取值范围为0≤ki≤9，所以每个关键字可取值的数目为10，通常将关键字取值的数目称为基数，用符号r表示，在这个例子中r=10。对于关键字序列（AB,BD,ED）可以将每个关键字看成是由二个单字母关键字组成的复合关键字，并且每个关键字的取值范围为“A~Z”，所以关键字的基数r=26。null 我们在这里讲述的基数排序是指用多关键字的LSD方法排序，即对待排序的记录序列按照复合关键字从低位到高位的顺序交替地进行“分组”、“收集”，最终得到有序的记录序列。在此我们将一次“分组”、“收集”称为一趟。对于由 d位关键字组成的复合关键字，需要经过d趟的“分配”与“收集”。
null 在基数排序的“分配”与“收集”操作过程中，为了避免数据元素的大量移动，通常采用链式存储结构存储待排序的记录序列，若假设记录的关键字为int类型，则链表的结点类型可以定义如下：
typedef struct node
{ int key;
anytype data;
int *next;
}List_Node;
null 8.6.3 链式基数排序算法
基数排序的基本操作是按关键字位进行“分配”和“收集”。
初始化操作
在基数排序中，假设待排序的 记录序列是以单链表的形式给出，10个队列的存储结构也是单链表形式，其好处是：在进行“分配”操作时，按
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
将每个结点插入到相应的队列中，在进行“收集”操作时，将非空的队列依次首尾相连，这样做即节省存储空间又操作方便。所以初始化操作主要是将10个队列置空：
null for（j=0;j
key%n/m // “分离”
if(f[k]==NULL) f[k]=p; //入队
else t[k]->next=p;
t[k]=p;null p=p->next; //从单链表中获取下一个结点
}
m=m*10; n=n*10;
“收集”操作
“收集”操作实际上就是将非空队列首尾相接。具体操作可以这样实现：
h=NULL; p=NULL;
for(j=0;jnext=f[j];p=t[j];}
}
null下面是基数排序的完整算法。
【算法8-12】
List_Node *radixsort( List_Node *h,int d,int r)
{ n=10; m=1;
for(i=1; i<=d;i++) //共“分配”、“收集”d次
{ for(j=0;j<=9;j++) //初始化队列
{ f[j]=NULL;t[j]=NULL;}
p=h;
null while(p) {
k=p->key%n/m // “分离”
if(f[k]==NULL) f[k]=p; //入队
else t[k]->next=p;
t[k]=p;
p=p->next; //从单链表中获取下一个结点
}
m=m*10; n=n*10;
h=NULL; p=NULL; //“收集”
null for(j=0;jnext=f[j];p=t[j];}
}
}
return(h);
}
null 从基数排序的算法中可以看到：。基数排序适用于待排序的记录数目较多，但其关键字位数较少，且关键字每一位的基数相同的情况。若待排序记录的关键字有d位就需要进行d次“分配”与“收集”，即共执行d趟，因此，若d值较大，基数排序的时间效率就会随之降低。基数排序是一种稳定的排序方法。
浙公网安备 33021202002483