第10章排序4归并与基数排序.ppt

第10章 排序,数据结构讲义,-归并与基数排序,SunL,莫源哄源蔡摇怠釉播慌翱斡纫榜农澡鞋拣拧窝祭绰嚣战映迭硼颈脚擎胎数第10章排序4-归并与基数排序第10章排序4-归并与基数排序,10.4 归并排序,归并将两个或两个以上的有序表组合成一个新的有序表，叫2-路归并排序设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。两两合并，得到n/2个长度为2或1的有序子序列。再两两合并，如此重复，直至得到一个长度为n的有序序列为止。,篇发摔哎洪翅溉歪倾掷狰裹苇漠坤瞎虱镶西瑞珐髓芜主甚怠沉避业怪膨煞第10章排序4-归并与基数排序第10章排序4-归并与基数排序,3,顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,例子：合并两个有序表,钻皑去锗传雕雇釜敦难与毒朝延胜伎滤硒婶毁滞狱凡琅爱励精境抒资概皑第10章排序4-归并与基数排序第10章排序4-归并与基数排序,4,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,7,项块袒潞货湃哟傣紊乓膳至匙基燥控骂纺羡隋谁伤迄妓千剃盐燎姚爽孜咎第10章排序4-归并与基数排序第10章排序4-归并与基数排序,5,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,您乍辨喘晚严托委侯撅促妄块腻种捅伪遮锥鲤兆堡生柿谎寻兑谨耕斯概繁第10章排序4-归并与基数排序第10章排序4-归并与基数排序,6,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,侈椭漂叮姥佑沏饺幢律陶岸癣浚瓢日莉铸俯犀卷屋伸拘裙单甄卵尚驼苇梅第10章排序4-归并与基数排序第10章排序4-归并与基数排序,7,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,涌碘温涪坷出厦扦属兰爸赊郎戒镜镜揭尉兽魏箔寿试毯葬域筒缚涛豢跋时第10章排序4-归并与基数排序第10章排序4-归并与基数排序,8,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,烛坪群俊诞辊裕醉抬相较茂忌劝旧赫梦伸兹瘦剪拓志类纳萨它盐壳直实摄第10章排序4-归并与基数排序第10章排序4-归并与基数排序,9,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,余郎辣庸蜡臼昔羹冰束欣倚僧林梦砖梗毯狱豢怕脑惹臀耕典陪釉绪瞎尉西第10章排序4-归并与基数排序第10章排序4-归并与基数排序,10,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,痘峰辐肠世克芯佣砾疽胶庞蛋慢发嵌琴靠羹蓟药驳际托爸秧址酋瓦娶芦虞第10章排序4-归并与基数排序第10章排序4-归并与基数排序,11,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,委掖罩叭骚史缚羔龙众堕毫拔窃考戌盖掳且扑派肤橇饲馒且豆谬友柑姿绷第10章排序4-归并与基数排序第10章排序4-归并与基数排序,12,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,忽半谣歹垦叉悄芜喜程袒鳃胀害将搂里蛇减牌嗅弟锋垦斡熟恐牲姬移膝苹第10章排序4-归并与基数排序第10章排序4-归并与基数排序,13,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,猖借酮紧赦散蝶纬茶茧吝孙忿竟碑砷瘩浅儡屋逢夺遮蚜歼饥完雅幌屁惟研第10章排序4-归并与基数排序第10章排序4-归并与基数排序,14,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,豺约空鲜综寝蘑宰选帜汹翱俺憎册营辙圈逃昼郁暴凡蛹屈虹堤颂炎翰黍窘第10章排序4-归并与基数排序第10章排序4-归并与基数排序,15,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。,蜗甜狂蛹贝螟气碉稼姜廉滞织脯洪尝腻坚陇渔锄跳骤喻辽婴藕役欧臃社肮第10章排序4-归并与基数排序第10章排序4-归并与基数排序,16,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。,97,次鲤人竞藤拔沥拇杭损鹰酶意兜遁沉帐形渐键操鉴耗废瓦桌膊晶庄主籍川第10章排序4-归并与基数排序第10章排序4-归并与基数排序,初始关键字：49 38 65 97 76 13 27,一趟归并后：38 49 65 97 13 76 27,二趟归并后：38 49 65 97 13 27 76,三趟归并后：13 27 38 49 65 76 97,例子：归并排序,霓讫福业奏霞驼淄倪梦舒荤崇貌撑琐梅邻汛汇需玖困绞锻垒受篱快蕴培蒂第10章排序4-归并与基数排序第10章排序4-归并与基数排序,算法评价,时间复杂度：T(n)=O(nlogn)空间复杂度：S(n)=O(n)它是一个稳定的排序方法。,薛绽撮窘厦画憨敝癣瘟民妆芜批揪鱼揣己轴薯璃逊源其硼邀弊笼宠扑谷瘴第10章排序4-归并与基数排序第10章排序4-归并与基数排序,10.5 基数排序,多关键字排序,例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”,彬邢的始筷琐绝健捆百证厚艳耿柬番辱加猴检鞋后障克迈蓖视绳鳃释递子第10章排序4-归并与基数排序第10章排序4-归并与基数排序,最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。,多关键字排序方法,钦悔软拓痛橡夏岳宏魄武搂稻跃娥石碘慌冯艳端退烷阜笨嘎匙象扯陆由栗第10章排序4-归并与基数排序第10章排序4-归并与基数排序,MSD与LSD不同特点,按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。,秘安祥钳均郧板褐错姥瞒室衫反荡牵德慰纺砧横泉耍致谩救浊爸障剖桥悲第10章排序4-归并与基数排序第10章排序4-归并与基数排序,链式基数排序,基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。链式基数排序：用链表作存储结构的基数排序。,戚台骋堤嘱嚎注矫赤伙山仓郧稽加五鳖营伯缎锋啦纪莹荧复底焊飘多拱等第10章排序4-归并与基数排序第10章排序4-归并与基数排序,例,基数排序的演示,嫩击沂弘呵括掖虐捡胺椒者铀衣聪浊狠医橙阉妹梧泞替皇讹芥坦僳捌酋髓第10章排序4-归并与基数排序第10章排序4-归并与基数排序,聋卸蕉掺爸嘻鹿掉瞳策疆秤遮韧可易恕拐赶括竞嘘昼先铆释选两庸诲荣秘第10章排序4-归并与基数排序第10章排序4-归并与基数排序,滩惶弊朔听户季票谐赘纹袜蛆所丰麻系畴吕况氯务搪种爽郧榷丫临萤渝玻第10章排序4-归并与基数排序第10章排序4-归并与基数排序,链式基数排序步骤,设置10个队列，fi和ei分别为第i个队列的头指针和尾指针。第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同。第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表。重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列。,狄话炊机拈属贼故牡车秸撬妻坯治海驱膘峰诌懈四张结渝叮厨池疹忍四驻第10章排序4-归并与基数排序第10章排序4-归并与基数排序,时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)、T(n)=O(d(n+rd)其中：n记录数，d关键字数，rd关键字取值范围(如十进制为10)。空间复杂度：S(n)=2rd个队列指针+n个指针域空间。,算法评价,囊华龟涛楔侠婶侄脂恭违嫡块津陆板炬讲瞅谨郎仍料嗽赊甸谬禾垮掏溜毙第10章排序4-归并与基数排序第10章排序4-归并与基数排序,平均时间 最差 最佳 辅助空间 稳定性直接插入 O(n2)O(n2)O(n)O(1)稳定起泡排序 O(n2)O(n2)O(n)O(1)稳定直接选择 O(n2)O(n2)O(n2)O(1)不稳定希尔排序 O(n1.5)O(1)不稳定快速排序 O(nlog2n)O(n2)同平均 O(log2n)不稳定堆排序 O(nlog2n)同平均 同平均 O(1)不稳定归并排序 O(nlog2n)同平均 同平均 O(n)稳定基数排序 O(d(n+r)同平均 同平均 O(n+r)稳定,排序算法小结,钵瞩脐旦峡闪临吊畴轨斗古抿狭厄米廓寐抨醉膜桩仅标琼寇鹊巾凶泪阻征第10章排序4-归并与基数排序第10章排序4-归并与基数排序,作业,若一组记录的关键码为（46,79,56,38,40,84），写出二路归并排序和链式基数排序一趟排序的结果。,倔贿左夸疫宏颊奄撅态爷扁讲酷行夫仕挽徒恐溶评兜好生茬术怀沿茧赔用第10章排序4-归并与基数排序第10章排序4-归并与基数排序,