算法22---内部排序--基数排序.ppt

《算法22---内部排序--基数排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章内部排序----基数排序10.6基数排序(RadixSort)问题：1.什么是“多关键字”排序？实现方法？2.单逻辑关键字怎样“按位值”排序？基本思想：借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。2多关键字排序例1：对一副扑克牌该如何排序？若规定花色和面值的顺序关系为：花色：面值：2<3<4<5<6<7<8<9<10

2、职称分＋工龄分）；总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口……等等排序。例3：学生评奖学金如何排序？多关键字排序的实现方法通常有两种：最高位优先法MSD(MostSignificantDigitfirst)最低位优先法LSD(LeastSignificantDigitfirst)10.6基数排序对一副扑克牌的排序若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个

3、箱中的牌按面值进行插入排序（或其它稳定算法）。LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。用哪种方法更快些？单逻辑关键字“按位值”排序设n个记录的序列为：{V0,V1,…,Vn-1}，可以把每个记录Vi的单关键码Ki看成是一个d元组（Ki1,Ki2,…,Kid），则其中的每一个分量Kij(1jd)也可看成是一个关键字。注1：Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元组；注2：每个分量Kij(1jd)有radix种取值，则称radix为基数。思路

4、：讨论：是借用MSD方式来排序呢，还是借用LSD方式？例：初始关键字序列T=（32,19,27,32*,13，30），请分别用MSD和LSD进行排序，并讨论其优缺点。法1（MSD）：原始序列：32,19,27,32*,13，30先按高位Ki1排序：（19,13）,27,（32,32*，30）再按低位Ki2排序：13,19，27,30,32,32*法2（LSD）：原始序列：32,19,27,32*,13，30先按低位Ki2排序：30,32,32*,13,27,19再按高位Ki1排序：13,19,27,30,32,32*MSD存在递归

5、效率受影响LSD只需进行线性扫描用链队列来实现基数排序—链式基数排序实现思路：针对d元组中的每一位分量，把原始链表中的所有记录,按Kij的取值,让j=d,d-1,…,1，①先“分配”到radix个链队列中去；②然后再按各链队列的顺序，依次把记录从链队列中“收集”起来；③分别用这种“分配”、“收集”的运算逐趟进行排序；④在最后一趟“分配”、“收集”完成后，所有记录就按其关键码的值从小到大排好序了。实现以下关键字序列的链式基数排序：T=（278，109，063，930，589，184，505，269，008，083）例27806393

6、0589109184505269008083第一趟分配e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]184083589505063269278930008f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]原始序列链表：r[0]→（从最低位i=3开始排序，f[]是队首指针，e[]为队尾指针）第一趟收集930063083184505278008109589269r[0]→109e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]06327826

7、9083184505109930589008f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第二趟分配（按次低位i=2）269589063505109184930008278083930063083184505278008109589269第一趟收集的结果：第二趟收集r[0]→r[0]→e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]083008930589184109269505063278f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[

8、9]第三趟分配（按最高位i=1）r[0]→排序结束！269930184008083589109063278505269589063505109184930008278083r[0]→第二趟收集的结果：第三趟收集基数排序算法分析假设有n个记录,每个记