《计算机应用基础课件1.6排序.ppt》由会员分享，可在线阅读，更多相关《计算机应用基础课件1.6排序.ppt（46页珍藏版）》请在课桌文档上搜索。
1、,第 1 章 数据结构,主要内容1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 排序,10,65,865,卞踩忘票酱馏沪卸诞挞蜜臼罪芽婆澳啤仑戚潭骋家至袱烤牵新扒拒琉刀甥计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,1.6 排序,排序又称分类，是计算机程序设计中一个重要运算，它的功能是将一组任意序列的数据元素，进行按关键字由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。,排序的对象：这些数据元素可以是数值型，也可以为字符型。若为数值型，则按数值大小排列；若为字符型，则按其ASCII码的顺序排列。,排序的依据：在实际应
2、用中，参加排序的数据元素有时不是单个数据项，而是由多个数据项组成的记录。此时排序应按照关键字的大小进行。所谓关键字是指记录中的某个数据项，用它可以标识一个记录。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字；反之，把用以识别若干记录的关键字称为次关键字。,阀蓟鹊氏镣渣拣萝孰辗旋拼驻给夫绸恿锦冰辣嫂抢隶逞俄妨寂洞莫贾租徽计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,排序的稳定性：在待排序的记录中，若存在多个关键在相同 的记录，经过排序后，这些具有相同关键在 的记录之间的相对次序发生变化，则称这种 排序方法是稳定的；否则，是不稳定的。排序的分类：内部排序与外部排序 内部排
3、序:整个排序过程完全在内存中进行.外部排序:由于待排序记录数据量太大,内存无法容纳 全部数据,排序需要借助外部存储设备才能 完成.排序算法评价：算法执行时间(最好、最差及平均情况)、需要附加空间大小,1.6 排序,喀颤淖清跨卿慷哮帚吓绥菩番盔神扶希帜撰白柑终惺泻济然嘱榆闹掀愤骋计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,插入排序的基本思想：,1.6.2 插入排序,插入排序三种方法1.直接排序:认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。2.折半插入排序:折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。
4、待排序元素越多，改进效果越明显。3.希尔排序:将整个无序序列分割成若干个子序列分别进行直接插入排序.,将待排序文件中的记录，逐个按其排序码值的大小插入到已排好序的若干个记录组成的文件中的适当位置，保持新文件有序。,凄悦浩诛坛返稀嚏棘裙滚煮稻仪节吭臼撰氖镑狸氰娃倚窑肠差晦胎跟旁锚计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,1.直接插入排序:思路：认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。具体过程(第i个记录Ri插入到前面i-1个已排好序的记录中)将Ri的排序码与前面已排好序的排序码从右向左依次比较，找到Ri应插入的位置；将该位置以
5、后直到Ri-1各记录顺序后移,空出位置插入Ri。,1.6.2 插入排序,宪依白跪粹姨匠迪旅平爬糜读劳攻框晃肢幸没械章猪佳藻陌撞扑稻哆风扫计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,直接插入排序:,次数i r0 r1 r2 r3 r4 r5 r6 r7 r8(49)39 66 96 76 11 37 50,(39 49)66 96 76 11 37 50,i=2,39,(39 49 66)96 76 11 37 50,i=3,66,(39 49 66 96)76 11 37 50,i=4,96,(39 49 66 76 96)11 37 50,i=5,76,(11 39 49
6、66 76 96)37 50,i=6,11,(11 37 39 49 66 76 96)50,i=7,37,(11 37 39 49 50 66 76 96),i=8,50,对于有n个数据元素的待排序列，插入操作要进行n-1次,忽荤干寒陈育垃只丫敖蛙憎拼彬筹民犬巫唬究酷雀尊翔捣锣越曹懊贰榔哺计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,./*对N个整数进行升序排序*/for(i=1;i=0;k-)/寻找插入位置if(aiak)break;/插入到第k个位置的后面 temp=ai;for(j=i-1;jk;j-)/向后移动 aj+1=aj;aj+1=temp;,箭佛梗锁液媒慨屏棒
7、菩诺舀孕滋绢处球饼赏惑敝讳坦猖晚杉翻农椽斟渤匹计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,./*改进前面的算法*/for(i=1;i=0,tempaj,若降序排序，则：,欺甭咯列碗罐酵泵涪润矢寐洪哈冶奢蜕赋邮堤曳操粟授栈塔壳箍掂弛宜烧计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,1.直接插入排序:时效分析,最好情况:初始排序码已经有序。共比较n-1次，移动0次。,最坏情况:待排序序列完全逆序。比较和移动均为n(n-1)/2次。,平均情况:比较和移动次数均约为n2/4，时间复杂度为O(n2)。,1.6.2 插入排序,该算法适合于n 较小的情况，时间复杂度为O(n
8、2).,汤漾栽吠价目颖郎邦刘酸柜肌疟菲搀灰暇孜齿剩介续弦凭挽盔孩除述阿祸计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。,折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同为O(n2)。,1.6.2 插入排序,遥竞九阻轴豫鞭锗篮甜绢战抄气蚜札陕窥囊胯恨潭浚嚷列黔蚀谣厂贩啸仲计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,3.希尔排序,基本思想：将整个无序序列分割成若干个子序列分别进 行直接插入排序,待整
9、个序列中的记录”基本 有序”时,再对全体记录进行一次直接插入排序。子序列分割：选定两个元素之间距离h，将所有间隔为h的元素 分成一组(将相隔某个增量h的元素构成一个子系列),具体实现:,(1)选择一个增量序列t1，t2，tk,其中ti tj,tk=1。(2)按增量序列个数k，对序列进行k趟排序。(3)每趟排序，根据对应的增量ti，将序列分割成若干长度为m的子序列，分别对各子表直接插入排序。增量ti逐次减小，tk=1时，再对全部元素进行一次直接插入排序即可完成。,1.6.2 插入排序,渡陀匙淘轻曼辕巨慢驮讽宜晋右耪叙案坪叛影椽诵收耳突户垄衣苹府瞬驻计算机应用基础课件1.6 排序计算机应用基础课件
10、1.6 排序,举例:有一个含有14个数的序列,使用希而排序进行升序排序(39,80,76,41,13,29,50,78,30,11,100,7,41,86)取增量：5，3，1,h=5,39 80 76 41 13 29 50 78 30 11 100 7 41 86,(R1,R6,R11)39 29 100,(R2,R7,R12)80 50 7,(R3,R8,R13)76 78 41,(R4,R9,R14)41 30 86,(R5,R10)13 11,则子序列：39，29，100，80，50，7，76，78，41，41，30，86，13，11,R1,R2,R3,R4,R5,R6,R7,R8,R
11、9,R10 R11,R12,R13,R14,役粥仟带匙哩绰祥削瞎荤魁砍坦艰瞒崔丧窍拒读罪请沟氖鹃挎潍过黄狂瓤计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,h=5,39 80 76 41 13 29 50 78 30 11 100 7 41 86,子序列：39，29，100，80，50，7，76，78，41，41，30，86，13，11,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10 R11,R12,R13,R14,29 39 100,7 50 80,41 76 78,30 41 86,11 13,因此第一趟排序结果如下:29 7 41 30 11 39 50 76
12、 41 13 100 80 78 86,对每个序列进行直接插入排序:,匆痔体痘漂厨涡镭治误库琶右雄氟咕瓦违虚年酣付深惧其瘤存杖摆票栽弛计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,h=3,29 7 41 30 11 39 50 76 41 13 100 80 78 86,29 30 50 13 78,7 11 76 100 86,41 39 41 80,分别对以上3个子序列,即29，30，50，13，78，7，11，76，100，86，41，39，41，80进行直接插入排序,13 7 39 29 11 41 30 76 41 50 86 80 78 100,(R1,R4,R7,
13、R10,R13),(R2,R5,R8,R11,R14),(R3,R6,R9,R12),R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14,13 29 30 50 78,7 11 76 86 100,39 41 41 80,第二趟最终结果：,第一趟排序结果,躁俯吐伪贮染眉抬法参目羹吐钡咐义字简裙壮蘸窄第浙酉邦泌簇拼九荚周计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,13 7 39 29 11 41 30 76 41 50 86 80 78 100,h=1 序列基本有序，对其进行直接插入排序,第三趟最终结果：,7 11 13 29 30 3
14、9 41 41 50 76 78 80 86 100,第二趟最终结果：,褥肋桨蠕胺嘻铀肇恳心类冉湘喊尔舒啃屁语抖樟谬赵驻较尉趋竖帆迂陨纽计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,3.希尔排序,特点：每一遍以不同间隔距离插入排序。h较大时移动数据元素是跳跃式进行。子序列每一次比较可能移去多个逆序(直接插入排序每次比较只能移去一个)。效率较高。最后一次排序(h=1)时，已基本有序，不需要多少移动。故其时间复杂度较直接插入排序低。数学难题：如何选取增量序列才能有最好的排序效果，至今未完整解决。但注意：增量序列中除1外没有公因子，且最后一个增量序列必须为1。时效分析:很难。比较次数
15、与移动次数依赖于增量序列的选取，特定情况下可以估计.,1.6.2 插入排序,大襟嘴脉仇欧卡耀览笺饯鼓娩记淤悠唤肮沪庭暴娃瞅赶靖贮购绩竖抗扭拔计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,对待排序记录两两比较排序码，不满足排序顺序则交换。直到任何两个记录排序码满足排序要求。,基本思路,交换排序种类:,冒泡排序快速排序,1.6.3 交换排序,汁炸操崖然矢恢慧捻草慎叮谤壤释摹哺贴窄凌磊菌圈熄疏玩茁绚嘱超滋水计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,1.冒泡排序基本思想：通过相邻元素的交换，逐步将线性表变成有序。基本过程：第一趟冒泡排序：首先第一个元素与第二个元素比
16、较，逆序则 交换；然后第二个元素与第三个元素比较；直到第n-1个元素与第n个元素比较为止。结果（关键字）最大的元素放在最后位置。第二趟冒泡排序：对前面n-1个元素进行相同操作，结果 次大元素放在n-1位置上。第i趟冒泡排序：对前面n-i+1个元素进行相同操作，结 果(n-i+1)中最大元素放在(n-i+1)位置上。,趟数：最多n-1,结束条件：在某一趟排序中没有进行交换元素操作。,1.6.3 交换排序,无伐衣伺拷福频砾兑缩烷扁肋症簿硒缘氟渝讣猜距殿描铆痔须馈韧沙苦溅计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,38,49,76,97,13,97,27,97,30,97,13,7
17、6,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,思想：小的浮起，大的沉底。,疲颇则陶咀哩粉痉蔚燕仿堤屹娱种佳仙厉众低洗闸米沃屋厌润掖荧慕佐褥计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,举例:将数列(8,6,5,7,1)升序排序,初始86571,第一趟65718,第二趟56178,第三趟51678,第四趟15678,初始已排好序(正序最好)，则只需进行一趟排序,比较次数n-1，移动次数为0。逆序(最坏)，则需进行n-1趟排序,比较次数为(1+2+3+n-1)=n(n-1)/2。是稳定的排序,
18、时间复杂度为O(n2),空间复杂度是O(1).,时效分析:,程序代码:,偶纯碧采寄涯懒抛反啮窘船邪角尝耘凹雕摊蹋逞渡证呛咋氨度潭洱膨递交计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,#define N 5int gradeN,temp;for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,读入5个值保存在数组中,16,71,46,90,85,敦憎伙玛野叭孵兽篡沧幂豪敷驳揭侨切联嚏将婿炊款捣吧姆咖逞街推胃亮计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,temp=46,temp=71,temp=1
19、6,16,71,46,90,85,i=0 第1趟,j=0 从头开始比较,j4,条件不成立,j=1,j4,条件成立,90,46,j=2,j4,条件成立,90,71,j=3,j4,90,16,j=4,内层循环终止,90,即：i=0 第1趟 时 grade0 和grade1比较 grade1 和grade2比较 grade2 和grade3比较 grade3 和grade4比较 最大值放到grade4中,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,即，i=0 第1趟 时内存循环for(j=0;jN-
20、1-i;j+)变量j是从0到3的,瀑厌抡致基沃牛彰晤个懊耙柳苇傍秸瞄孰兹咸茂账夹准让生币汲墙阂享铰计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,16,71,46,90,85,i=1 第2趟,j=0 从头开始比较,90,46,90,71,90,16,90,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,内存循环for(j=0;jN-1-i;j+)中 j的取值从0到2 grade0 和grade1比较 grade1 和grade2比较 grade2 和grade3比较找出次大值放到gr
21、ade3中,却宠警揪辨馏林给账霓荒您撂羔饭枢凶血蓝胀拙越乘微忱抢秽捕水减蔗店计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,16,71,46,90,85,i=1 第2趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,宠拆太匿磨墅麓隐舜丘世井内拦豫啪腑估盔稽畜迅蔼蜗痪稿郴寸亏将毯纤计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,16,71,46,85,i=2 第3趟,90,46,90,7
22、1,90,16,90,85,46,85,71,85,16,85,71,71,16,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1=gradej;gradej=temp;,牧卫盅辱攒彪默辞吟众秧棍拔滞潜涸衬瓦饺拈趟兴嚎构削弘疾肉答嘉骗舵计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,16,71,46,85,i=3 第4趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,71,71,16,#define N 5for(i=0;i gradej+1)temp=gradej+1;gradej+1
23、=gradej;gradej=temp;,46,16,46,疚态克采坎云祖殊贯肃蕴辊韦菩常钢户宠痊永翌揩坏汤钝跪廖氧诡纠哉矫计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,2.快速排序,基本思想：通过一趟排序将待排记录分割成独立两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再对前、后两部分待排记录重复上述过程，直到所有子表表长不超过1为止。,优点：通过两个不相邻元素交换，可以一次交换消除多个逆序，加快排序速度。,49 39 66 96 76 11 27 50,27 39 11 49 76 96 66 50,27 39 49 50 66 76 96,1.6.3 交换排序
24、,率精羔遥孟佯滇惰痞茫板关泅隋神由敷盅宋卜俘诉邱澄需户毒绘搁募爱寇计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,2.快速排序,过程:,首先任选一个记录K(通常选第一个记录)作为枢轴(支点)附设两个指针i和j分别指向第一个记录和最后一个记录。(1)指针j向前搜索逐个记录与K比较,直到发现小于K的记录为止，将其与枢轴记录互相交换。(2)指针i向后搜索逐个记录与K比较,直到发现大于K的记录为止，将其与枢轴记录互相交换。(3)重复(1)(2)直至i=j为止。完成一趟排序，完成一次分割(以K为分界线)，对前后两个子表按上述原则再分割，直到所有子表的表长不超过1(为空)为止。,1.6.3
25、交换排序,瞧矢娃畅锥癣闭板谐则祁候鹊货珠功铅巢佛伪蚀橱霉剔坞渺挂茶奠恃静吹计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,49 39 66 96 76 11 27 50,第1次交换(向前,小的与枢轴交换)即27与49交换.,第2次交换:(向后,大的与枢轴交换)即66与49换,第3次交换:11与49换,完成一趟排序:,初始关键字,第4次换:96与49换,27 39 11 49 76 96 66 50,举例:将（49，39，66，96，76,11，27，50）进行一趟快速排序 分析:(取第一个数49为枢轴,即K=49,空处是枢轴为49),硒肋狐扼饮卿淬豫牡睦侮既昧宜桨盏双滤萨乘句恒券
26、掌淡特跑引叁扶淬陪计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,49 39 66 96 76 11 27 50,27 39 11 49 76 96 66 50,一次划分之后,快速排序的全过程,初始关键字,分别进行快速排序,11 27 39,50 66 结束,结束 结束 50 66 76 96,结束,11 27 39 49 50 66 76 96,有序序列,时效分析:平均时间复杂度最佳为O(nlog2n)。最坏情况时间效率为O(n2)。,瓣咙庙劈铃嘎土苛妮当簧效准迸贩形瞅遭彦尔寡拘笺半澜般产兆致装萎铣计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,基本思想：每次从待
27、排序的记录中选出关键字最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序种类:直接选择排序和堆排序,1.直接选择排序(以升序为例)首先从所有n个待排序记录中选择关键字最小的记录，与第1个记录交换(第1遍进行n-1次比较)。再从剩下的 n-1个记录中选出关键字最小的记录，与第2个记录交换(第2遍进行n-2次比较)。重复操作进行n-1遍，直到待排序序列全部有序为止。,1.6.4 选择排序,凿呼菱年冒躁簿图桓罪公拉绽屯妄藩桶琴镰句隙刽碑妮柔友鄂朱画摘证毕计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,1.直接选择排序,正序：移动次数为0逆序：移动次数为3(n-1),执
28、行n(n-1)/2次比较,举例:将（89，21，56，48，85，16，19，47）直接选择排序,原序列 89 21 56 48 85 16 19 47,最后结果 进行n-1=7次选择,1.6.4 选择排序,时效分析:,组宾汰野雍尝右措雪姚脆诊逢冀饭舞峰源池晕唁若喧蚤隘后伏拷拥贴言踪计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,选择法排序 for(i=0;i ak)k=j;if(k!=i)temp=ai;ai=ak;ak=temp;,卓带琐超辛些箔日酱酵狭挫共年卧两茫爹撮珊努勃舒勋胳邹蛤擒附诵拷竟计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,例,初始：49 38
29、 65 97 76 13 27,i=1,13,49,一趟：13 38 65 97 76 49 27,i=2,27,38,六趟：13 27 38 49 65 76 97,从小到大排序,砸钎搬林痞辙虎敌厩躯沛耻料添钞佣戊翻店囱旧蛋狰境恫迭唐瘫聋刃周蒙计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,2.堆排序堆定义：n个元素的序列K1，K2，Kn，当且仅当满足下列关 系时，称为堆。,kik2i kik2i+1,kik2i kik2i+1,小根堆 或,大根堆,堆结构(完全二叉树表示)：将序列对应的一维数组看成一个完全二叉树。,在堆中,堆顶元素必为序列中n个元素的最小值(或最大值)。,小根
30、堆,大根堆,其中:（i=1，2，n/2）,1.6.4 选择排序,目携撒朔赌概播案矣唬罪堑节襟引始妄课甸东拢天巍诡诽臣蝴绍钨小琼静计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,首先包括n个元素的序列建堆,输出堆顶最小值。得到n个元素中最小元素。然后再对剩下n-1个元素重建堆,输出堆顶元素。得到n个元素中次小元素。反复执行(直到剩下子序列为空)，便得到一个有序列。,2.堆排序,排序过程:,两个问题:实现堆排序需解决,(1)如何将n个元素的无序序列建成一个堆。,(2)输出堆顶元素后，调整剩余元素成为一个新堆。,输出堆顶元素后，以堆中最后一个元素代替之。此时根结点左、右子树均为堆，仅需
31、自上而下调整即可。,1.6.4 选择排序,方法：将根结点与左、右子树根结点比较，若不满足堆条件，则较小值与根结点交换。顺序：从完全二叉树最后一个非终端结点(第n/2个元素)开始，直到根结点(第一个元素)为止，对每一个结点，调整建堆。,跳狮视椽勘泣堕吕鞠饲悦遍芥鸵织呸室稠景掇烬渊类慢低扫代宦芋往匈捣计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,举例:一个无序序列(49,39,66,96,76,11,27,50)建小根堆的过程 1.从第一个非叶子结点(序号=n/2=8/2=4,即图中值为96的结点开始筛选,筛选 原则是保证父结点的值要小于或等于叶子接点,第4个结点96被筛选后状态,
32、第3个结点66被筛选后状态,甚驾溯壮饯缠蔓具虹客乃赔瑰胀赖益堰列绢晃萌桐勇峪抹圣膏坛沮葵萄檄计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,目前的堆中,堆顶元素11为最小值,输出后,重新对n-1个元素重新建一个新堆,新堆中的堆顶是剩余的n-1个元素中的最小值,n个元素中的次最小值.,49 被筛选后建成的堆,该处理第1个结点,防畴膨妓迈砖淌恤瑶掷澎陌辗电览吸少栽邯寇系蔷粟螟行靛潘悄续鸭驼鲍计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,举例:输出堆顶元素并建新堆过程,堆,11,11与96交换后情形,输出堆顶元素之后,以堆中最后一个元素替代之,此时根结点的左、右子树均为
33、堆,仅需自上至下进行调整即可。,11,27与96交换后情形,11,调整后新堆,27为新堆中的最小值,耽芦藕慑抢瓶复美未睁袱涟耙屠邯拥肺愤德坑忧荡庸囤卵乓全冤墙场沤孟计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,27,输出27,用96替代,11,96与39换,11,27,96与50换,调整后新堆,27为新堆中的最小值,11,调整后新堆,39为新堆中的最小值,晾典绊菲星膘缘鸿粳渔泼权譬筹号自哲沃此禽籍坛搏访崩扇梨乍苔跌吐瞪计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,继续此过程,调整后新堆,39为新堆中的最小值,11,27,39,11,27,输出堆顶元素（堆顶元素和
34、树中最后一个结点对调）重建堆（因为除了堆顶的根结点，左右子树已经是堆，自上而下进行调整即可）反复执行直到剩下子序列为空（便得到一个有序列）,堆排序的时效分析:最坏情况下，时间复杂度为O(nlog2n)。仅需一个记录大小供交换用的辅助存储空间，适合规模较大的线性表。,澳剥固霖触祝馁峡捞即亮师何眼尾捷氛烁爹多爽孪暑垄否霓靠亨帖丸身样计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,排序小结,捞液零肾欧廊汕疤愉续椭恫题学歼喳盎馅棍钥随硬夹谰贬薄拼损监歧易闰计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,查找与排序补充习题讲解,1.链表适用于_查找.A.顺序 B.二分法 C.
35、顺序,也能二分法 D.随机2.对长度为n的线性表进行顺序查找,在最坏情况下所需要 的比较次数为_.A.log2n B.n/2 C.n D.n+1（05年4月）3.已知一个有序表为(13、18、24、35、47、50、62、83、90、115、134），当使用二分法查找90的元素时，查找 成功的比较次数为_.A.1 B.2 C.3 D.94.在排序算法中，两两比较待排序的记录，当发现不满足 顺序要求时，变更他们的相对位置，这就是_排序。A.希尔排序 B.交换排序 C.插入排序 D.选择排序,ACBB,教烂善更型埂它页灰佰肾离蛆恢景卢担因肠溯娄珐邹读忻美讫骨槽吾崔容计算机应用基础课件1.6 排序计
36、算机应用基础课件1.6 排序,5.设待排序关键码序列为（33、18、9、25、67、82、53、95、12、70），要按关键码值递增的顺序排序，采取以 第一个关键码为分界元素的快速排序法，第一趟排序完 成后关键码33被放到了第_个位置。A.3 B.5 C.7 D.96.希尔排序法属于哪一种类型的排序法_。A.交换类排序法 B.插入类排序法 C.选择类排序法 D.建堆排序法以下各组序列中，属于堆的是_.A.19、34、26、97、56、75 B.97、26、34、75、19、56 C.19、56、26、97、34、75 D.19、75、34、26、97、568.对于长度为n的线性表，在最坏情况下
37、，下列各排序法所对应的比较次数中正确的是_.(05.4月）A.冒泡排序为n/2 B.冒泡排序为n C.快速排序为n D.快速排序为n(n-1)/2,BBAD:8:在最坏情况下,冒泡排序和快速排序的比较次数都是 n(n-1)/2,艾肄础吹涯吨叹絮销牺谁漂鲜刑弧澎猎绸研轨汗帽羞随序辕咱煮沏疫份震计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,查找与排序补充习题讲解,填空题：1.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素做比较，将其放入已排序的正确位置上的方法，称为_.2.对于给定的一组关键字（12、2、16、30、8、28、4、10、20、6、18），按
38、照希尔排序（增量为5）算法进行递增排序，第一趟排序后得到的结果是_.,（12、2、16、30、8、28、4、10、20、6、18）,12 28 18,16 10,2 4,30 20,8 6,对每个系列排序,则最终结果12,2,10,20,6,18,4,16,30,8,28,崖当果澈铁腿膳浆挺嗜撑皂谴棘芍融睫酵叛酿陷龙佑拱炬原孜嗡量牵墅券计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,3.在长度为n的线性表中顺序查找x的元素时,查找成功的平均查找长度为_.4.在具有88个结点的二叉数,其深度至少为_.,3解析:平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度.假设在每个位置查找概率相等,即p1=p2=1/n,若是从表尾向表头方向查找,则每个位置上查找比较次数为:Cn=1,Cn-1=2,C1=n.于是,查找成功的平均查找长度为 ASL=(1/n)(1+2+3+n)=(n+1)/24 分析:性质4:深度=log2n+1=log288+1=6+1=7,浆除彬榷祈墒怔榨之亡赏身贼俺瘴奉盎辱粮葱滇潜泳孟吭惭镐尿没朝哑姬计算机应用基础课件1.6 排序计算机应用基础课件1.6 排序,
