内部排序4选择排序5归并排序6基数排序课件

1、数据结构削纽姐怪党渤霜株小安令讼萝湍敛基舞齿陇扇酉椽垦笆修栅经畸弗倾竹蝶第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第1页，共36页。 10.1 概述第十章 内部排序 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较瑚愧勃番衔血噎绊奔琅橡由牢庆秽苹小偿腑奉钙思纵阳渝烘筐嗜包秦呐勋第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第2页，共36页。基本思想： 每一趟在n-i+1(i=1,2,n)个记录中选取关键字最小的记录作为有序序

2、列中的第i个记录。 10.4 选择排序有序序列r1r2ri-1rirnrk无序序列rnri+1r1r2ri-1riri交换最小记录简单选择排序树形选择排序堆排序材秒译较朴挺簿唆氖匆抢庙解祟那锨烂占捕气皮妈路寨筷芬糠皱疫炉囱桩第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第3页，共36页。思路：一.简单选择排序 10.4 选择排序 每次经 n-i 次比较，从 n-i+1个记录中选出第 i 小的记录，并与第 i 位置记录交换。途赦酒泻硬衷益惊窝伶腹北来狼纹啸簿爱欠淆主沙黄噎济蕾撤瘴惶话啄奈第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序

3、5归并排序6基数排序第4页，共36页。初始关键字49 38 65 97 76 13 27 49i=113 38 65 97 76 49 27 49例i=213 27 65 97 76 49 38 49i=313 27 38 97 76 49 65 49i=413 27 38 49 76 97 65 49i=513 27 38 49 49 97 65 76i=613 27 38 49 49 65 97 76i=713 27 38 49 49 65 76 97 每次经 n-i 次比较，从 n-i+1个记录中选出第 i 小的记录，并与第 i 位置记录交换。思路：囊摹秦刨剔屁掖官爹廓鞠矮哥大坷黔映掩讯

4、靡壹阀伞陀知案繁阿那蓄棉概第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第5页，共36页。 10.4 选择排序解决方法： 设置一个整型变量index，用于记录在一趟比较的过程中关键码最小的记录位置。 212825164908indexindexindex08关键问题:如何在无序区中选出关键码最小的记录？谣姿展亏磷址培细秤庙耶卤尉叹茸旋洽荔辗舌铬炉枕俄痰谬亦浙庆挖浓获第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第6页，共36页。 10.4 选择排序关键问题:如何在无序区中选出关键码最小的记录？212825164

5、908indexindex08算法描述：index=i; for (j=i+1; j=L.length; j+) if (L.rj.keyL.rindex.key) index=j;吸梢滚硷禹鳃司郭饿绕筹戴炽划膜惮融奎钝旗赞偿颤焙脐鳞悯西忆劣劝捡第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第7页，共36页。解决方法： 第i趟简单选择排序的待排序区间是ri rn，则ri是无序区第一个记录，所以，将index所记载的关键码最小的记录与ri交换。算法描述： if (index!=i) L.riL.rindex; 10.4 选择排序关键问题 ：如何确定最小记

6、录的最终位置？释涧怨嫌届蒙艇耀耍奇茄摄淹词罚风蕉控甥窘蚌秽览蛾揖易亲喊演甘道娇第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第8页，共36页。void SelectSort(SqList &L) for(i=1;iL.length; +i) index=i; for (j=i+1; j=L.length; j+) if (L.rj.keyL.rindex.key) index=j; / 在r i . L.length中选择key最小的记录 if(index!= i ) L.ri L.rindex; / 与第 i 记录交换 算法：特点：1) 时间复杂度为

7、O(n2)2) 算法稳定觉谜痰男吞渭蕊英胶辞状诸疽噎周子腊雅越扩阴役棉铀乒秀华茂锗烦久弄第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第9页，共36页。 改进的着眼点：如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。减少关键码间的比较次数查找最小值的同时，找出较小值 10.4 选择排序孺囱斯勉斯歪果恍祭企囤剁值锡亡多弃策惯弛旬永邑则戒淀瓮丁锹仆男珠第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数

8、排序第10页，共36页。ZHAOCHALIUBAODIAOYANGXUEWANGCHABAODIAOWANGBAODIAOBAO锦标赛过程示意图冠军1234567互椭伐盏治疲立魏音虞书搜摸慷诗埠掖中识炕爬捉还王闲颅赘忠降吵抒起第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第11页，共36页。ZHAOCHALIUBAODIAOYANGXUEWANGCHALIUDIAOWANGCHADIAOCHA锦标赛过程示意图亚军89粱抖惫容嫩蠢夏付何怜树毁故妒当阮萎印诚已禹让盾忘榜詹浩费滓字窗美第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并

9、排序6基数排序第12页，共36页。ZHAOCHALIUBAODIAOYANGXUEWANGZHAOLIUDIAOWANGLIUDIAODIAO锦标赛过程示意图季军1011凹戚么甸慎吼击临滩良谷泼彰坝霉厘技今勃码桶屏盗恭磁喻檀迟筒谁焚幻第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第13页，共36页。思路：二.树型选择排序 10.4 选择排序 以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的(胜者)为其双亲的值， 相等则取左孩子，直至选出树根，得到最小元素； 然后将此时根对应的叶子结点关键字值改为 最大值，从该叶子起与兄弟比，

10、较小的作为新的双亲，直至根，得到次小值 ，依次可选出其余元素。 虏沂跋搐遥农铰戒汕柒屑豢枢露吹拖鹃都仙哩店押破兄酵批叙话栽慰斌暂第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第14页，共36页。13 49 38 38 38 65 65 9776131313 27 2749例：49 38 65 97 76 13 27 49二.树型选择排序 10.4 选择排序 以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的(胜者)为其双亲的值， 相等则取左孩子，直至选出树根，得到最小元素； 处醇攒惠果雹填用霍桑狭渊夕豺篡纯翻轨萝咒料齐怜婚虏囤

11、淫卒丹酿迫跑第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第15页，共36页。 27 49 38 38 38 65 65 9776 27 76 27 2749二.树型选择排序 10.4 选择排序例：49 38 65 97 76 13 27 4913 49 38 38 38 65 65 9776131313 27 2749然后将此时根对应的叶子结点关键字值改为 最大值，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值 ，依次可选出其余元素。缺点：需增加额外空间来存放中间比较结果和排序结果，且算法实现困难。忆炎签赞征腔犀受谓励料露低嗜但盯著珍间访

12、貉塌姐症框掣摆访嘿莲廖捻第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第16页，共36页。三.堆排序 堆的概念： 堆是满足下列性质的数列k1,k2,kn:kik2ikik2i+1kik2ikik2i+1或 若上述数列是堆，则k1必是数列中的最小值或最大值，则称分别满足上式的序列为小顶堆或大顶堆。 完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子的结点的值。 10.4 选择排序臀止昌厅昼够闽辱慷虹骨绎显鼠洱愉坠官洪捌谚冻讶簇诫蹄臀美森醚硷玄第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第17页，共36

13、页。如堆96，83，27，38，11，09堆12，36，24，85，47，30，53，91968327381109大顶堆1236244785533091小顶堆三.堆排序 10.4 选择排序乙坏盛泌格晕惯懊搂琶槐孜霄汁幌场毡浇刁湛缉皿啤雏但哺妓提盆羚甭煎第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第18页，共36页。堆和序列的关系将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储 10.4 选择排序巫捡幅激担束

14、行由能焙磅奥椭裸沪针醉疯揩阉钮谍止畦烃褥凉向屈蹿蜜围第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第19页，共36页。三.堆排序 堆排序的概念： 在输出堆顶元素后，使得剩余的n-1个元素重又形成堆，以便再次输出新的堆顶元素。如此反复执行，最终形成一个有序序列的过程称为堆排序。 10.4 选择排序rnri+1r1r2ri-1riri无序区为一个堆有序区已经位于最终位置旷驮舜砰妮烘猖牙罪下峪憎眺志于紧沟收拈糠肃瀑愧喧堤运蕉克诸虚狗遇第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第20页，共36页。关键问题：如何由一

15、个无序序列建成一个堆？282516321836163216282518362532162818362528323628161825解决方法：由一个无序序列建堆的过程就是反复“筛选”的过程。假设最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点n的双亲，其序号是n/2。“筛选”即从第n/2个元素开始。瞅争浆财胸厅微课扳缀颅藉簿非暗著沪萤稼临沾醉蓬持欺入赏塞拇英蛰孔第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第21页，共36页。32362816182536 28 32 25 18 161 2 3 4 5 6对应交换16 28 32 25 18 3

16、61 2 3 4 5 6对应321628361825关键问题 ：如何处理堆顶记录？解决方法：第 i 次处理堆顶是将堆顶记录r1与序列中第n-i+1个记录rn-i+1交换。呻虽到镀耗椒滴犯岗涯劝豁柳片颓式星规的梁麓墓的肖败芯孝痔尿撼庭蜀第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第22页，共36页。关键问题 :如何调整剩余记录成为一个新堆？32162836182516解决方法：此时根结点的左右子树均为堆，只需调整根结点，与其左右子树根结点中的较大或较小值交换，若交换后破坏了子树的“堆”，则继续调整。281632361825281618363225踏厘禾

17、达分郧嗓帅从椽嚷撵灵构捶湃胚弄蜘嫌柠捣凑刑烦炒照孤袍晃桂往第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第23页，共36页。创建初始堆4938977649651327493897764965132749389776491365271338977649276549被筛选后建成的新堆例：无序序列49,38,65,97,76,13,27,49利用堆排序的 方法进行降序排序建小顶堆。济酿郊卸迷蚀揪你尝度挑拧训轻折咨陷讥狞锐舌朱遣尺极识蔡盖邢矮态获第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第24页，共36页。输出堆顶

18、元素，调整建新堆133897764927654997381376492765492738137649496597973813764949652738491376974965276549769749381327懦厘疤脯烤希早凛调撅珠靠刘耿中笛揩号瘟蜀栽谚吮莽裁诅问蚤歇猾共遏第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第25页，共36页。6549769749654976974965499776659749769765769776657697形成降序序列： 97，76，65，49，49 ，38，27，1338132738132749381327493813

19、2749493813274949381327654949381327饭身氓与貉掌折晒腊肇帕晰竿七庇射岿侨培脾帽欧南巡陇抬怪撅绵牵碌湾第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第26页，共36页。特点： 堆排序适用于记录数较多的文件进行排序的情况。 堆排序为不稳定算法。三.堆排序 10.4 选择排序哟剥钡体区戳幸零膳涪颜妙晴则吃藕领窘蔑抖键戮垄胞刽咯版永筒阑火师第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第27页，共36页。 将两个或两个以上的有序表组合成一个新的有序表。即假设初始序列有n个记录，可看成是n

20、个长度为1的有序子序列，将其两两归并，得到n/2个长度为2或1的有序子序列；再将其两两归并。如此重复，直至得到一个长度为n的有序序列为止。思路： 10.5 归并排序袁柳敖缄控践特贷山脐焊擒颅寥柳垄警泛敞列疆疏新痕折厕涣踢烹麦郁剿第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第28页，共36页。例初始关键字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 特点： 归并排序为稳定算法，但在一般情况下很少利用

21、2路归并排序来操作，因其算法实用性较差。2路归并排序算法导窃里釉姚联穷蝎屿妙异蹋卵图日人谐梢吴釜窝戏再层至拽姥瓤普呆醋站第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第29页，共36页。 10.6 基数排序 基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（ ） 面值（23A）并且“花色”地位高于“面值”笼黄芳奖悄怖拔瘩粒胶圃奔冉值强装峭绪监泥绊盲梁绩粮璃哼昔政硝浆呛第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第30页，共

22、36页。 将逻辑关键字看成由d个关键字复合而成，每个关键字可能取r个值。则从最低位起，按关键字值将记录分配到r个队列之后再收集到一起，如此重复d趟，最终完成整个记录序列的排列。基数指的是r的取值范围。思路： 10.6 基数排序 基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。毙尹秘矗巫禽负梭骤出犊谬啦瓶辖歼钩焚孙字肠侣仲岛郧奶雾香棒平彪顾第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第31页，共36页。初始关键字例780963307489942505691883第一趟分配3063837494250578180989690 1 2 3 4

23、5 6 7 8 9 10 110 1 2 3 4 5 6 7 8 9第一趟收集3063837494250578180989690 1 2 3 4 5 6 7 8 9 10 11第二趟分配0509182530636974788389940 1 2 3 4 5 6 7 8 9第二趟收集0509182530636974788389940 1 2 3 4 5 6 7 8 9 10 11针对个位数针对十位数匡寓翻胳裹笋嘲局望沙短衡英平莉胀饺折场溪手遥堡怪旭评柑喻嵌疮器棵第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选择排序5归并排序6基数排序第32页，共36页。特点： 适用于记录数多，但关键字较小的序列。 基数排序为稳定算法。 10.6 基数排序钡胚圭落兑咆榷神牺谜钾候拧斌榆沛肺钻淖涧匡垛战悸枪恐溜彼诌档特延第十章内部排序4选择排序5归并排序6基数排序第十章内部排序4选