数据结构全套配套课件C语言描述第2版李学刚教学课件6-15分配排序2.pptx

《数据结构全套配套课件C语言描述第2版李学刚教学课件6-15分配排序2.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、关键字Kd-1对记录进行排序，再按关键字Kd-2对记录进行排序，如此重复，最后按关键字K1对记录进行排序，得到一个有序文件。三、基数排序1．多关键字排序方法例如：扑克牌先按花色关键字进行排序，花色的顺序为梅花、方块、红桃、黑桃，将扑克牌按花色分成4堆，再对每一堆按面值关键字进行排序，最后将各堆依次叠放在一起得到有序的一副扑克牌，此方法就是高位优先法。另外，扑克牌先按面值关键字进行排序，再按花色关键字进行排序，得到有序的一副扑克牌，此方法就是低位优先法。14分配排序三、基数排序2．基数排序基本思路基数排序就是用低位优先法对单关键字（或多关键字）排序的

4、一种方法按低位优先法对关键字进行箱排序，通过“分配”和“收集”实现每趟排序。在每趟箱排序中，所需的箱子数就是基数r，这就是“基数排序”名称的由来15分配排序三、基数排序3．基数排序实例36516989547323648第一次装箱按关键字第一个分量（个位）将其装箱。32595361636479848第二次装箱按关键字第二个分量（十位）将其装箱。51632363647489598B[0]B[3]B[4]B[5]B[6]B[7]B[8]B[9]B[1]B[2]B[0]B[3]B[4]B[5]B[6]B[7]B[8]B[9]B[1]B[2]36163659

5、59848473236163659598484732164、基数排序算法分配排序（1）数据描述#defined4//不妨设关键字位数d=4#definer10//基数r为10typedefRecTypeDataType//队列中元素的类型DataType设为RecType（2）装箱算法voidDistribute(SeqListR,LinkQueueB[],intj){//按关键字的第j个分量进行装箱inti,k,t;for(i=1;i<=n;i++){//依次扫描R[i]，将其装箱k=R[i].key;for(t=1;t

6、;//使R[i].key的第j位成为k的最低位k=k%10;//取关键字的第j位数字kEnQueue(&B[k],R[i]);//将R[i]装入箱子B[k]}}三、链表的插入17voidRadixSort(SeqListR){//对R[1...n]进行基数排序，R[i].key为非负整数，且位数不超过dLinkQueueB[r];//10个箱子，每个都是链队列inti;for(i=0;i

7、第i趟装箱Collect(R,B);//第i趟收集}}分配排序（3）收集算法voidCollect(SeqListR,LinkQueueB[]){//依次将各非空箱子中的记录收集起来inti=1,j;//收集时从R[1]开始存放for(j=0;j

8、以基数排序的时间复杂度是线性的，即O(n)。（2）空间性能5、算法分析基数排序是稳定的排序方法。（3）稳定性基数排序共需r