《F基数排序》PPT课件

《《F基数排序》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章内部排序￡10.1概述￡10.2插入排序￡10.2.1直接插入排序￡10.2.2其他插入排序￡10.2.3希尔排序￡10.3快速排序￡10.4选择排序￡10.4.1简单选择排序￡10.4.2树形选择排序￡10.4.3堆排序￡10.5归并排序￡10.6基数排序￡10.6.1多关键字的排序￡10.6.2链式基数排序￡10.7各种内部排序方法的比较讨论1￡10.6基数排序基数排序（RadixSorting）是一种借助多关键字排序的思想对单逻辑关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。2￡10.6.1多关键字的排序（1）定义假设有n个记录的序列{R1,R2,…,

2、Rn}（10－4），则称序列（10－4）对关键字有序是指：对于序列中任意两个记录Ri和Rj(1≤i

3、子序列对Kd-1进行排序，最后将所有子序列依次联接在一起成为一个有序序列。2．特点：按MSD进行排序时，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序。4（2）多关键字排序的实现②最低位优先LSD（LeastSignigicantDigitfirst）1．算法实现：从最次位关键字Kd-1起进行排序。然后再对高一位的关键字Kd-2进行排序，依次重复，直至对K0进行排序后便成为一个有序序列。2．特点：a.按LSD进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki(0≤i≤d－2)进行排序时，只能用稳定的排序方法。b.按LSD进行排序时，在一定的条件下

4、（即对前一个关键字Ki(0≤i≤d-2)的不同值，后一个关键字Ki+1均取相同值），可通过若干次“分配”和“收集”来实现排序。5（3）例子例如，已知扑克牌中52张牌面的次序关系为：♣2<♣3<…<♣A<♦2<♦3<…<♦A<♥2<♥3<…<♥A<♠2<♠3<…<♠A每一张牌有两个“关键字”：花色(♣<♦<♥<♠)和面值(2<3<…

5、3”在“2”之上，“4”在“3”之上，……，最上面的是4张“A”），然后将这付牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌按自小至大的次序合在一起（♣在最下面，♠在最上面）。6LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组：(Ki1,Ki2,...,Kid)如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3,K2,K1的顺序对所有对象排序。7￡10.6.2链式基数排序（1）定义有的逻辑关键字可以看成由若干个关键字复合而成的，且

6、每个关键字Kj都在相同的范围内，则按LSD进行排序时，只要从最低数位关键字起，按关键字的不同值将序列中记录“分配”到PADIX个队列中后再“收集”之，如此重复d次。按这种方法实现的排序称之为基数排序。其中“基”指的是RADIX的取值范围。链式基数排序：用链表作存储结构的基数排序。例如，若关键字是数值，且其值都在0≤K≤999范围内，则可把每一个十进制数字看成一个关键字，即可认为K由3个关键字(K0,K1,K2)组成，其中K0是百位数，K1是十位数，K2是个位数，对每一个关键字0≤Ki≤9（i＝0,1,2），“基”为10。8（3）例子例如，图10.13(a)所示；第一趟分配对最低

7、位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至10个链队列中去，每个队列中的记录关键字的个位数相等，如图10.13(b)所示，其中f[i]和e[i]分别为第i个队列的头指针和尾指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列中的记录链成一个链表，如图10.13(c)所示；第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图10.13(d)~(g)所示。至此排序完毕。(a)初始