《数据结构（C语言描述）（第2版）》教学课件6-15分配排序2

1、2016数据结构Data structure讲授：丁慧分配排序常州信息职业技术学院11分配排序扑克牌是多关键字的，有花色和点数两个关键字，花色取值只有4种，而点数则有13种；三、基数排序基数排序是箱排序的改进和推广。1多关键字排序方法（1）单关键字和多关键字扑克牌有两个关键字：点数和花色。多关键字中的每个关键字的取值范围一般不同，单关键字中的每位一般取值范围相同。三位十进制整数是单关键字的，每位数码的取值范围都是0到9。12分配排序（2）基数设单关键字的每个分量kj的取值范围均是：C0kjCr-1（0jd），可能的取值个数r称为基数。基数的选择和关键字的分解与关键字的类型有关：若关键字是十进制

2、整数，则按个、十等位进行分解，基数r=10，C0=0，C9=9，d为最长整数的位数；若关键字是小写的英文字符串，则r=26，C0= a，C25= z，d为字符串的最大长度。三、基数排序1多关键字排序方法13分配排序（3）多关键字排序方法高位优先法：先按最高位关键字K0对记录进行排序，将文件分成若干堆，每堆中的记录都具有相同的K0值，再对每堆按关键字K1对记录进行排序，如此重复，直到对每堆按关键字Kd-1对记录进行排序，最后将各堆按次序叠在一起成为一个有序文件。低位优先法：先按最低位关键字Kd-1对记录进行排序，再按关键字Kd-2对记录进行排序，如此重复，最后按关键字K1对记录进行排序，得到一个

3、有序文件。三、基数排序1多关键字排序方法 例如：扑克牌先按花色关键字进行排序，花色的顺序为梅花、方块、红桃、黑桃，将扑克牌按花色分成4堆，再对每一堆按面值关键字进行排序，最后将各堆依次叠放在一起得到有序的一副扑克牌，此方法就是高位优先法。另外，扑克牌先按面值关键字进行排序，再按花色关键字进行排序，得到有序的一副扑克牌，此方法就是低位优先法。14分配排序三、基数排序2基数排序基本思路基数排序就是用低位优先法对单关键字（或多关键字）排序的一种方法按低位优先法对关键字进行箱排序，通过“分配”和“收集”实现每趟排序。在每趟箱排序中，所需的箱子数就是基数r，这就是“基数排序”名称的由来15分配排序三、基

4、数排序3基数排序实例 36 5 16 98 95 47 32 36 48第一次装箱按关键字第一个分量（个位）将其装箱。 32 5 95 36 16 36 47 98 48第二次装箱按关键字第二个分量（十位）将其装箱。 5 16 32 36 36 47 48 95 98B0B3B4B5B6B7B8B9B1B2B0B3B4B5B6B7B8B9B1B2361636 59598484732361636 59598484732164、基数排序算法分配排序（1）数据描述#define d 4 /不妨设关键字位数d=4#define r 10/基数r为10typedef RecType DataType/队

5、列中元素的类型DataType设为RecType（2）装箱算法void Distribute(SeqList R,LinkQueue B,int j)/按关键字的第j个分量进行装箱 int i,k,t; for(i=1;i=n;i+)/依次扫描Ri，将其装箱 k=Ri.key; for(t=1;tj;t+) k=k/10;/使Ri.key的第j位成为k的最低位 k=k%10; /取关键字的第j位数字k EnQueue(&Bk,Ri); /将Ri装入箱子Bk三、链表的插入17void RadixSort(SeqList R)/对R1.n进行基数排序，Ri.key为非负整数，且位数不超过dLink

6、Queue Br; /10个箱子，每个都是链队列int i;for(i=0;ir;i+)InitQueue(&Bi); /箱子置空for(i= 1;i=d;i+) /从低位到高位做d趟箱排序Distribute(R,B,i); /第i趟装箱Collect(R,B); /第i趟收集分配排序（3）收集算法void Collect(SeqList R,LinkQueue B)/依次将各非空箱子中的记录收集起来 int i=1,j;/收集时从R1开始存放 for(j=0;jr;j+) while(!QueueEmpty(&Bj)DeQueue(&Bj,&Ri+); /将箱子Bj中的记录放入Ri（4）排序算法4、基数排序算法三、链表的插入18分配排序（1）时间性能 基数排序由于装箱和收集的时间复杂度是线性的，即O(n)，而记录关键字的位数d与n无关，所以基数排序的时间复杂度是线性的