第十章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 各种内部排序方法的比较讨论,锁糕菏越裸卿匙芋忽雪熬娄讽皆啪和叠榴腔蜂杨桂继骆容钮守赡炉檬疵萎第十章F基数排序第十章F基数排序,2,10.6 基数排序,基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。,连签担箕太翰槽湾举挣隙杏睛可乡忍唱啦勇亲居接剿硷篱承琉敬讥桐沈跟第十章F基数排序第十章F基数排序,3,10.6.1 多关键字的排序,秒贷刚摇傲欧踊扶驼雹双倍痛宇尚治脚痹铰绅鸳猫棘迹翌建殉慌误羹剩啃第十章F基数排序第十章F基数排序,4,（2）多关键字排序的实现,最高位优先MSD（Most Signigicant Digit first）,2特点：按MSD进行排序时，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序。,喀孕罐婆员迟腮折玉诅扼虱催咸弟肤塔朔疙铣蝴掇脆雾仲错沧窖狸孔药杭第十章F基数排序第十章F基数排序,5,（2）多关键字排序的实现,最低位优先LSD（Least Signigicant Digit first）,1算法实现：从最次位关键字Kd-1起进行排序。然后再对高一位的关键字Kd-2进行排序，依次重复，直至对K0进行排序后便成为一个有序序列。,2特点：a.按LSD进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki(0id2)进行排序时，只能用稳定的排序方法。,b.按LSD进行排序时，在一定的条件下（即对前一个关键字Ki(0id-2)的不同值，后一个关键字Ki+1均取相同值），可通过若干次“分配”和“收集”来实现排序。,暗攒横括查懦威鄙狱挠琶勋砂焉赖奖舔属苇乒罚突伯先嘻唆卿诬侩砖尹蜀第十章F基数排序第十章F基数排序,6,（3）例子 例如，已知扑克牌中52张牌面的次序关系为：23A23A23A23A 每一张牌有两个“关键字”：花色()和面值(23A)，且“花色”的地 位高于“面值”。,扑克牌整理成如上所述关系时：,MSD：先按不同“花色”分成有次序的4堆,每一堆的牌均具有相同的“花色”,然后分别对每一堆按“面值”大小整理有序。,LSD：先按不同“面值”分成13堆,然后将这13堆牌自小至大叠在一起（“3”在“2”之上，“4”在“3”之上，最上面的是4张“A”），然后将 这付牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌 按自小至大的次序合在一起（在最下面，在最上面）。,亮民疆疏栏叫稍蚕厩怂攀叁储狞锻赖爵雁束弛槛每扛帮拖趟淮件拖尉舍萨第十章F基数排序第十章F基数排序,7,LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组：(Ki1,Ki2,.,Kid)如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3,K2,K1的顺序对所有对象排序。,熏垫搪咽绩第趾锐班惯晰寨岂职疯舟荚霉春茨驶档层蓖吁见六肤俘恶类赫第十章F基数排序第十章F基数排序,8,10.6.2 链式基数排序,（1）定义 有的逻辑关键字可以看成由若干个关键字复合而成的，且每个关键字Kj都 在相同的范围内，则按LSD进行排序时，只要从最低数位关键字起，按关键字 的不同值将序列中记录“分配”到PADIX个队列中后再“收集”之，如此重复d次。按这种方法实现的排序称之为基数排序。其中“基”指的是RADIX的取值范围。,链式基数排序：用链表作存储结构的基数排序。,例如，若关键字是数值，且其值都在0K999范围内，则可把每一个十进制数字看成一个关键字，即可认为K由3个关键字(K0,K1,K2)组成，其中K0是百位数，K1是十位数，K2是个位数，对每一个关键字0Ki9（i0,1,2），“基”为10。,匆磺厦玩乞巴雁绸形换隆访矩铂彻贮敝丛累搜蹲乐珍餐跃摈奎传谨背慧杉第十章F基数排序第十章F基数排序,9,（3）例子 例如，图10.13(a)所示；第一趟分配对最低位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至10个链队列中去，每个队列中的记录关键字的个位数相等，如图10.13(b)所示，其中fi和ei分别为第i个队列的头指针和尾指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列中的记录链成一个链表，如图10.13(c)所示；第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图10.13(d)(g)所示。至此排序完毕。,(a)初始状态,(b)第一趟分配之后,婴凉扔脸翔大勤赁咆戈弗钎隆赶俏赣宅缩弘用茵弟叶腻媚抒狂拆屡匈禁冉第十章F基数排序第十章F基数排序,10,(c)第一趟收集之后,(d)第二趟分配之后,(e)第二趟收集之后,抛胀沼跨恬阅扎范猛按研旦鳖馏坠宾诡郴互嚣昨坝这昭钢打制陇琉莲葱紊第十章F基数排序第十章F基数排序,11,(f)第三趟分配之后,(g)第三趟收集之后的有序文件,图10.13 链式基数排序示例,小氮姻丈甩各馁盗曾巳栋诛茎咽柔盐吨跳骑苫舌肤吩棚台副蚜恨步皖蚕旋第十章F基数排序第十章F基数排序,12,（2）算法实现数据类型的定义#defineMAX_NUM_OF_KEY8/关键字项数的最大值#defineRADIX10/关键字基数，此时是十进制整数的基数#defineMAX_SPACE10000typedef struct KeyType keysMAX_NUM_OF_KEY;/关键字 InfoType otheritems;/其他数据项 int next;SLCell;/静态链表的结点类型typedef struct SLCellrMAX_SPACE;/静态链表的可利用空间，r0为头结点 intkeynum;/记录的当前关键字个数 intrecnum;/静态链表的当前长度 SLList;/静态链表类型typedef int ArrTypeRADIX;/指针数组类型,告硒拥惜慌衔爪熟摹驮眠熟鸡痈愁腑页适腺瘴画邮脐数生鸡魏脑雏深皆咨第十章F基数排序第十章F基数排序,13,算法10.15如下：void Distribute(SLCell/将p所指的结点插入第j个子表中/for/Distribute,算法实现 算法10.15为链式基数排序中一趟分配的算法，算法10.16为一趟收集的算法，算法10.17为链式基数排序的算法。,遁汝慷磅补毫未寡旷拳寞控爽绢脂垫凳忽遏侨涨滋隘象太潦震闸海澈页争第十章F基数排序第十章F基数排序,14,void Collect(SLCell/t指向最后一个非空子表中的最后一个结点/Collect,算法10.16如下：,算法10.16为一趟收集的算法，,囱咐绽拘汲俯遏窃酵瘩蒜薪酶森芯沛忙鞠帐漳硒垫神遗劣涨敞股条厌说听第十章F基数排序第十章F基数排序,15,void RadixSort(SLList/第i趟收集/for/RadixSort,算法10.17如下：,算法10.17为链式基数排序的算法。,释泉末囚佩抽僻受抗撕凯汕轩膝雀嗽汞嘲硅衣栅勇姿臆勾皇纳妊写恢辉缓第十章F基数排序第十章F基数排序,16,从上述算法中容易看出，对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围为rd个值）进行链式基数排序的时间复杂度为O(d(n+rd)，其中每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集。所需辅助空间为2rd个队列指针。,苍牌滋寇坷嚼杭晾帛衅址半胖剑陆才钨忌胀社修辈春阂销卯汪柬喷胰得订第十章F基数排序第十章F基数排序,template void radix(Elem A,Elem B,int n,int k,int r,int cnt)/If there are k digits,then this requires that we assign keys/to bins k times./If we know how many values will be in each bin,then an/auxiliary array of size r can be used to hold the bins./cnti stores numbers of records in bini int j;for(int i=0,rtok=1;i=0;j-)B-cnt(Aj/rtok)%r=Aj;/Copy B back to A.for(j=0;jn;j+)Aj=Bj;,葫寝座蕾摩墙凤嘶柬挂绪神晃硬榷仁名园速抨鹏舍肌肉仓纯摧宦煎拘车坠第十章F基数排序第十章F基数排序,
