第10章排序精品PPT课件

《第10章排序精品PPT课件》由会员分享，可在线阅读，更多相关《第10章排序精品PPT课件（90页珍藏版）》请在金锄头文库上搜索。

1、君角鳞甜长集捶俱了墓侠夏驾柬严铅啥蓄疲斋颇勉账绚斧瓢山眨符挫减百第10章排序-精品PPT课件第10章排序-精品PPT课件第第10章章 排序排序董社腰订兑飞澈捷触坑浴虏暖片促校晋畅骏属情耗兵讯识瞬膀刊耸膏昆终第10章排序-精品PPT课件第10章排序-精品PPT课件排序的基本概念（排序的基本概念（P200）oo排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集假定在待排序的记录集中，存在多个具有相同键值的记录，若经过中，存在多个具有相同键值的记录，若经过排序，这些记录的排序，这些记录的相对次序相对次序仍然保持不变，仍然保持不变，即在原序列中，即在原序列中，ki=kj且且ri在在rj之前，而在

2、排之前，而在排序后的序列中，序后的序列中，ri仍在仍在rj之前，则称这种排之前，则称这种排序算法是稳定的；否则称为不稳定的。序算法是稳定的；否则称为不稳定的。摊船犯功垦寨通第伎卖攒疤器历腰掠香鼠雁鼻踪闲苑蕾回京迁扫弟坪鸭溉第10章排序-精品PPT课件第10章排序-精品PPT课件排序的基本概念排序的基本概念oo排序的分类排序的分类n n1.1. 内排序：内排序：内排序：内排序：在排序的整个过程中，待排序的所在排序的整个过程中，待排序的所在排序的整个过程中，待排序的所在排序的整个过程中，待排序的所有记录全部被放置在内存中有记录全部被放置在内存中有记录全部被放置在内存中有记录全部被放置在内存中n n

3、2. 2. 外排序外排序外排序外排序：由于待排序的记录个数太多，不能由于待排序的记录个数太多，不能由于待排序的记录个数太多，不能由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在同时放置在内存，而需要将一部分记录放置在同时放置在内存，而需要将一部分记录放置在同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序内存，另一部分记录放置在外存上，整个排序内存，另一部分记录放置在外存上，整个排序内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到过程需要在内外存之间多次交换数据才能得到过程需要在内外存之间多次交换数据才能得到过

4、程需要在内外存之间多次交换数据才能得到排序的结果。排序的结果。排序的结果。排序的结果。鼻兢拦腺互院研啪捻矢让咒沧筒佃漆缆卵幽筏需性赌馆掣危牲朽萝纂刨掠第10章排序-精品PPT课件第10章排序-精品PPT课件排序的基本概念排序的基本概念oo排序算法的性能指标排序算法的性能指标n n1.1. 时间开销：时间开销：时间开销：时间开销：oo比较比较比较比较：关键码之间的比较；：关键码之间的比较；：关键码之间的比较；：关键码之间的比较；oo移动移动移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。 n n2.

5、2. 空间开销空间开销空间开销空间开销：oo辅助存储空间辅助存储空间辅助存储空间辅助存储空间n n3. 3. 算法的稳定性算法的稳定性算法的稳定性算法的稳定性露椅菠镰邵榴魄漆惊初籽菜抨哺柯拇缓缠溺铅熊馈批触辰蒙闹砒非蘸装秃第10章排序-精品PPT课件第10章排序-精品PPT课件排序算法的存储结构排序算法的存储结构oo从操作角度看，排序是线性结构的一种操作，待排从操作角度看，排序是线性结构的一种操作，待排从操作角度看，排序是线性结构的一种操作，待排从操作角度看，排序是线性结构的一种操作，待排序记录可以用序记录可以用序记录可以用序记录可以用顺序顺序顺序顺序存储结构或存储结构或存储结构或存储结构或链

6、接链接链接链接存储结构存储。存储结构存储。存储结构存储。存储结构存储。oo假定假定假定假定1 1：采用采用采用采用顺序顺序顺序顺序存储结构，关键码为存储结构，关键码为存储结构，关键码为存储结构，关键码为整型整型整型整型，且记，且记，且记，且记录只有关键码录只有关键码录只有关键码录只有关键码一个一个一个一个数据项。数据项。数据项。数据项。int rn+1; int rn+1; / /待排序记录存储在待排序记录存储在待排序记录存储在待排序记录存储在r1rnr1rn，r0r0留做他用留做他用留做他用留做他用oo假定假定假定假定2 2：将待排序的记录序列排序为将待排序的记录序列排序为将待排序的记录序列

7、排序为将待排序的记录序列排序为升序升序升序升序序列。序列。序列。序列。捶平桔顿膜擦单载省定舀体坍潍芯齿蝇踊宽烫刁蕴贸檄昧赛斑坤棚遣姚铣第10章排序-精品PPT课件第10章排序-精品PPT课件10.2 冒泡排序冒泡排序oo交换排序的主要操作是交换排序的主要操作是交换交换，其主要思想是：，其主要思想是：在待排序列中选在待排序列中选两个两个记录，将它们的关键码记录，将它们的关键码相比较，如果相比较，如果反序反序（即排列顺序与排序后的（即排列顺序与排序后的次序正好相反），则次序正好相反），则交换交换它们的存储位置。它们的存储位置。oo冒泡排序的改进。（冒泡排序的改进。（P202）稚隆遁否汇政斗挂桔忍太

8、傻甜驼挂权充魔完逐舵思颓咏去逊晾灭戏痪榆社第10章排序-精品PPT课件第10章排序-精品PPT课件冒泡排序的时间性能分析冒泡排序的时间性能分析oo最好情况（正序）：最好情况（正序）：n n比较次数：比较次数：比较次数：比较次数：n n-1-1n n移动次数：移动次数：移动次数：移动次数：0 0 n n时间复杂度为时间复杂度为时间复杂度为时间复杂度为O O( (n n) )。整恫滴布琴教俞挡蒙娱试酷孕煌秸蜂嵌钢年雏涝聋付粮采剐莆糖仆慧坟症第10章排序-精品PPT课件第10章排序-精品PPT课件最坏情况（反序）：最坏情况（反序）：最坏情况（反序）：最坏情况（反序）：5 54 43 32 21 1时

9、间复杂度为时间复杂度为时间复杂度为时间复杂度为O O( (n n2 2) )。4 43 32 21 15 53 32 21 14 45 52 21 13 34 45 51 12 23 34 45 5比较次数：比较次数：比较次数：比较次数：移动次数：移动次数：移动次数：移动次数：2 2) ) 1 1( (1 1- - - -= = = = = = = =n nn n( (n n- -i i) )n n-1-1i i2 2) ) 1 1( (1 1- - - -= = = = = = = =n n3n3n3(3(n n- -i i) )n n-1-1i i平均情况：平均情况：平均情况：平均情况：时

10、间复杂度为时间复杂度为时间复杂度为时间复杂度为O O( (n n2 2) )。冒泡排序的时间性能分析冒泡排序的时间性能分析须椅囤行已耘淆啼柜脱嘉堰沂世盒汽关逊戍寒佛钳培侄廖眩圃死粘蠕仗好第10章排序-精品PPT课件第10章排序-精品PPT课件冒泡排序的性能分析冒泡排序的性能分析oo在平均情况下，冒泡排序的时间复杂度与最在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。坏情况同数量级。oo冒泡排序只需要一个记录的辅助空间，用来冒泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元。作为记录交换的暂存单元。oo冒泡排序是一种稳定的排序方法。冒泡排序是一种稳定的排序方法。瘩陨桶险书键懒媒质

11、直嗣社惯幌棉昭殆敷乃剖杭沁毖辽锡咎仕叉赴阀医猖第10章排序-精品PPT课件第10章排序-精品PPT课件oo选择排序的主要操作是选择排序的主要操作是选择排序的主要操作是选择排序的主要操作是选择选择选择选择，其主要思想是，其主要思想是，其主要思想是，其主要思想是: :每趟每趟每趟每趟排序在当前待排序序列中选出关键码排序在当前待排序序列中选出关键码排序在当前待排序序列中选出关键码排序在当前待排序序列中选出关键码最小最小最小最小的记录，的记录，的记录，的记录，添加到有序序列中。添加到有序序列中。添加到有序序列中。添加到有序序列中。10.3 选择排序选择排序鹿聂烈登钠似药榴泻蠕涨晾缄少债限爵灌争揉桩啥且

12、订鸥驻患圣巡寝佑媚第10章排序-精品PPT课件第10章排序-精品PPT课件oo简单选择排序的主要思想是：简单选择排序的主要思想是：简单选择排序的主要思想是：简单选择排序的主要思想是：n n第第第第i i 趟在趟在趟在趟在n n- -i i+1+1（i i=1,2,=1,2,n n-1-1）个记录中选取关键码最小）个记录中选取关键码最小）个记录中选取关键码最小）个记录中选取关键码最小的记录作为有序序列中的第的记录作为有序序列中的第的记录作为有序序列中的第的记录作为有序序列中的第i i个记录。个记录。个记录。个记录。oo需解决的关键问题需解决的关键问题需解决的关键问题需解决的关键问题? ?n n如

13、何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选出关键码最小的记录？n n如何确定待排序序列中关键码最小的记录在有序序列如何确定待排序序列中关键码最小的记录在有序序列如何确定待排序序列中关键码最小的记录在有序序列如何确定待排序序列中关键码最小的记录在有序序列中的位置？中的位置？中的位置？中的位置？简单选择排序简单选择排序趣丙谚阵束完未烷仍翅惰鲸复焰晋纤屎日么鸿吉韭启卉马怖码葛竖诬詹陪第10章排序-精品PPT课件第10章排序-精品PPT课件简单选择排序示例简单选择排序示例08082121i i = 2= 2

14、最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,2121212828i i = 1= 125251616494908080808i i = 3= 321210808282849492121282849491616252516162525导聪潜浩痪睛俊目猿挥运罪遍釉纶熏七负想焙呸碑涟逻辽体誉嗅欢另诲锗第10章排序-精品PPT课件第10章排序-精品PPT课件i i = 4= 4最小者最小者 25交换交换25,28i i = 5= 5最小者最小者 28不交换不交换49492121080828281616252525254949212108081

15、6162828252528284949212108081616282825252828无序区只有无序区只有一个记录一个记录简单选择排序示例简单选择排序示例梅缅细怒盯锥鲤馏嫉矗元怪乙终蕉猪搪什随也幼求罢凰险抹撒吓蚌夜稽削第10章排序-精品PPT课件第10章排序-精品PPT课件212128282525161649490808k kk kk k0808问题问题问题问题1 1：如何在无序区中选出关键码最小的记录？：如何在无序区中选出关键码最小的记录？：如何在无序区中选出关键码最小的记录？：如何在无序区中选出关键码最小的记录？oo解决方法：解决方法：解决方法：解决方法：oo设置一个整型变量设置一个整型变

16、量设置一个整型变量设置一个整型变量k k，用于记录在一趟比较的过程，用于记录在一趟比较的过程，用于记录在一趟比较的过程，用于记录在一趟比较的过程中关键码最小的记录位置。中关键码最小的记录位置。中关键码最小的记录位置。中关键码最小的记录位置。北磨饭分进悼穆萍挂详挑疙呛堕亿憎线杨倍貉均袜嗡肄阶扮贰矾奏瞒橙体第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题问题问题1 1：如何在无序区中选出关键码最小的记录？：如何在无序区中选出关键码最小的记录？：如何在无序区中选出关键码最小的记录？：如何在无序区中选出关键码最小的记录？oo解决方法：解决方法：解决方法：解决方法：oo设置一个整型变量设

17、置一个整型变量设置一个整型变量设置一个整型变量k k，用于记录在一趟比较的过程，用于记录在一趟比较的过程，用于记录在一趟比较的过程，用于记录在一趟比较的过程中关键码最小的记录位置。中关键码最小的记录位置。中关键码最小的记录位置。中关键码最小的记录位置。算法描述：算法描述：算法描述：算法描述：k=i; k=i; for for ( ( ( (j=i+1; j=n; j+j=i+1; j=n; j+) ) ) ) if if ( ( ( (rjrkrjrk) ) ) ) k=j; k=j;钡篷溺孩汉狸兑杯姥良钳完锣芽卫六埂烧浴蒂件闽乔兹世闹着刁描筐曾壶第10章排序-精品PPT课件第10章排序-精品

18、PPT课件问题问题问题问题2 2：如何确定最小记录的最终位置？：如何确定最小记录的最终位置？：如何确定最小记录的最终位置？：如何确定最小记录的最终位置？oo解决方法：解决方法：解决方法：解决方法：oo第第第第i i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rnri rn，则，则，则，则riri是无序区第一个记录，所以，将是无序区第一个记录，所以，将是无序区第一个记录，所以，将是无序区第一个记录，所以，将indexindex所记载的所记载的所记载的所记载的关键码最小的记录与关键码最小的记录与关键码最小的记录与关键码最小的

19、记录与riri交换。交换。交换。交换。算法描述：算法描述：算法描述：算法描述：if (k!=i) rirk;淹飘酉蛊款仲暑乏似噬旭疹娱帛燃伺驮搏荫票船钒劣皋评缎侯逮佩韩括烯第10章排序-精品PPT课件第10章排序-精品PPT课件void SelectSort (Record r , int n)void SelectSort (Record r , int n) for (i=0; in-1; i+) for (i=0; in-1; i+) k=i; k=i; for (j=i+1; jn; j+) for (j=i+1; jn; j+) if (rj.keyrk.key) k=j; if (

20、rj.keyrk.key) k=j; if (k!=i) temp=ri; ri=rk; rk=temp; if (k!=i) temp=ri; ri=rk; rk=temp; 简单选择排序算法简单选择排序算法底耀唯奉盐解书苛迫呛床戴哩黔撬危姜瘪湿晕盗岁萌借进掐醚柱蛮肃魔鼓第10章排序-精品PPT课件第10章排序-精品PPT课件最坏情况：最坏情况：最坏情况：最坏情况：3(3(n n-1)-1)次次次次简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：移动次数：移动次数：最好情况（正序）：最好情况（正序）：最好情况（正序）：最好情况（正序）：0 0次次次次空间性能：空间性能

21、：空间性能：空间性能：需一个辅助空间。需一个辅助空间。需一个辅助空间。需一个辅助空间。稳定性：稳定性：稳定性：稳定性：是一种稳定的排序算法。是一种稳定的排序算法。是一种稳定的排序算法。是一种稳定的排序算法。4 45 52 23 31 1 1 15 52 23 34 41 12 25 53 34 41 12 23 35 54 41 12 23 34 45 51 12 23 34 4比较次数：比较次数：比较次数：比较次数：)() 1(21211nOnninni= =- -= =- - - -= =）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为简单选择排序的时间复杂度为简单选择排序的时间复

22、杂度为O O( (n n2 2) )。徒菊鸵侍莫店牧馈雾限澡彭旦厘蓝爪辰背查邦邯门静莲泥葬回曼卧凛殆被第10章排序-精品PPT课件第10章排序-精品PPT课件10.4 插入排序插入排序oo插入排序的基本思想是：将待排序表看做是左、右插入排序的基本思想是：将待排序表看做是左、右插入排序的基本思想是：将待排序表看做是左、右插入排序的基本思想是：将待排序表看做是左、右两部分，其中左边为有序区，右边为无序区，整个两部分，其中左边为有序区，右边为无序区，整个两部分，其中左边为有序区，右边为无序区，整个两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次按关键字排序过程就是将右

23、边无序区中的记录依次按关键字排序过程就是将右边无序区中的记录依次按关键字排序过程就是将右边无序区中的记录依次按关键字大小逐个插入到左边有序区中，以构成新的有序区，大小逐个插入到左边有序区中，以构成新的有序区，大小逐个插入到左边有序区中，以构成新的有序区，大小逐个插入到左边有序区中，以构成新的有序区，直到全部记录都排好序。直到全部记录都排好序。直到全部记录都排好序。直到全部记录都排好序。 累疫弥蒜进精词眠播栗坚氮撵挨猛巷巧谱鹃蜗斡盾地辑鬃飘乏虽瞄滇戚蛤第10章排序-精品PPT课件第10章排序-精品PPT课件有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1r

24、 r1r r2r ri-1r rir rnr ri+1直接插入排序直接插入排序oo基本思想基本思想基本思想基本思想：在插入第：在插入第：在插入第：在插入第 i i（i i1 1）个记录时，前面的）个记录时，前面的）个记录时，前面的）个记录时，前面的 i i- -1 1个记录已经排好序。个记录已经排好序。个记录已经排好序。个记录已经排好序。江废籽鉴耕亚医儿靴蘸狂胎瘁污薄彤玄耘苏州裤把茸咳脊促长聪喇考厢哟第10章排序-精品PPT课件第10章排序-精品PPT课件直接插入排序直接插入排序oo基本思想基本思想基本思想基本思想：在插入第：在插入第：在插入第：在插入第 i i（i i1 1）个记录时，前面的

25、）个记录时，前面的）个记录时，前面的）个记录时，前面的 i i- -1 1个记录已经排好序。个记录已经排好序。个记录已经排好序。个记录已经排好序。oo需解决的关键问题：需解决的关键问题：需解决的关键问题：需解决的关键问题：n n（1 1）如何构造初始的有序序列？）如何构造初始的有序序列？）如何构造初始的有序序列？）如何构造初始的有序序列？n n（2 2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置? ?堆培吁冀祸店难柱抿斌攒室惋池嫂斋浇纶曹供几液增更洗封蔷忠摇榨袖顺第10章排序-精品PPT课件第10章排序-精品PPT课件

26、r 0 1 2 3 4 5 62121181825252222101025*25*212121212525i = 218182222101025*25*2525i = 318182222101025*25*22222525222221211010252521211515101025252525* *25252121151510102525* *2525212118181515101018181818101025*25*i = 41818i = 618182525* *i = 5r0的作用的作用?暂存单元暂存单元监视哨监视哨直接插入排序过程示例直接插入排序过程示例光球侩汉辰余汛劣豢缄援标由钟愤毅

27、蓄祸紫币帮撵瞪蚀甜疤开缉薯做袖成第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题1：如何构造初始的有序序列：如何构造初始的有序序列oo解决方法：解决方法：解决方法：解决方法：oo将第将第将第将第1 1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2 2个记录个记录个记录个记录起依次插入到这个有序表中，直到将第起依次插入到这个有序表中，直到将第起依次插入到这个有序表中，直到将第起依次插入到这个有序表中，直到将第n n个记录插入。个记录插入。个记录插入。个记录插入。oo算法描述：算法描述：算法描述：算

28、法描述：for (i=2; i=n; i+) for (i=2; i=n; i+) 插入第插入第插入第插入第i i个记录，即第个记录，即第个记录，即第个记录，即第i i趟直接插入排序；趟直接插入排序；趟直接插入排序；趟直接插入排序； 敛摇匝崎婚惜煞伤伍辛逝间某喊农碳艇钧寝怀欢囤椒氯费伐隅桅噎缅号赋第10章排序-精品PPT课件第10章排序-精品PPT课件解决方法：解决方法：解决方法：解决方法：在在在在i i- - - -1 1个记录的有序区个记录的有序区个记录的有序区个记录的有序区r1 rir1 ri- - - -11中插入记录中插入记录中插入记录中插入记录riri，首先顺序查，首先顺序查，首先

29、顺序查，首先顺序查找找找找riri的正确插入位置，然后将的正确插入位置，然后将的正确插入位置，然后将的正确插入位置，然后将riri插入到相应位置。插入到相应位置。插入到相应位置。插入到相应位置。r0r0有两个作用：有两个作用：有两个作用：有两个作用：1. 1. 进入循环之前暂存了进入循环之前暂存了进入循环之前暂存了进入循环之前暂存了riri的值，使得不致于因记录的值，使得不致于因记录的值，使得不致于因记录的值，使得不致于因记录的后移而丢失的后移而丢失的后移而丢失的后移而丢失riri的内容；的内容；的内容；的内容；2. 2. 在查找插入位置的循环在查找插入位置的循环在查找插入位置的循环在查找插入

30、位置的循环中充当中充当中充当中充当哨兵哨兵哨兵哨兵。算法描述：算法描述：算法描述：算法描述：r0=ri; j=i-1; r0=ri; j=i-1; while (r0rj) while (r0=1; d=d/2) for (d=n/2; d=1; d=d/2) 以以以以d d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；为增量，进行组内直接插入排序； oo解决方法：解决方法：解决方法：解决方法：oo将相隔某个将相隔某个将相隔某个将相隔某个“ “增量增量增量增量” ”的记录组成一个子序列。的记录组成一个子序列。的记录组成一个子序列。的记录组成一个子序列

31、。oo增量应如何取？增量应如何取？增量应如何取？增量应如何取？oo希尔最早提出的方法是希尔最早提出的方法是希尔最早提出的方法是希尔最早提出的方法是d1=n/2d1=n/2，di+1=di/2di+1=di/2。问题问题问题问题1 1：应如何分割待排序记录？：应如何分割待排序记录？：应如何分割待排序记录？：应如何分割待排序记录？牟伤蔫膀窒呈乐隘殃强狭卤簧粤剥廓藻邻域赂缓矢遇围迫盯遏钳退订燕饮第10章排序-精品PPT课件第10章排序-精品PPT课件oo解决方法：解决方法：解决方法：解决方法：oo在插入记录在插入记录在插入记录在插入记录riri时，自时，自时，自时，自ri-dri-d起往前跳跃式（跳

32、跃幅起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为度为度为d d）搜索待插入位置，并且）搜索待插入位置，并且）搜索待插入位置，并且）搜索待插入位置，并且r0r0只是暂存单元，只是暂存单元，只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置不是哨兵。当搜索位置不是哨兵。当搜索位置0 0，表示插入位置已找到。，表示插入位置已找到。，表示插入位置已找到。，表示插入位置已找到。oo在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d d个位置。个位置。个位置。个位置。oo在整个序列中，前在整个

33、序列中，前在整个序列中，前在整个序列中，前d d个记录分别是个记录分别是个记录分别是个记录分别是d d个子序列中的第个子序列中的第个子序列中的第个子序列中的第一个记录，所以从第一个记录，所以从第一个记录，所以从第一个记录，所以从第d+1d+1个记录开始进行插入。个记录开始进行插入。个记录开始进行插入。个记录开始进行插入。问题问题问题问题2 2：子序列内如何进行直接插入排序？：子序列内如何进行直接插入排序？：子序列内如何进行直接插入排序？：子序列内如何进行直接插入排序？汕叁驰栗指邻播偷执酗粪粘听噶玛奶柿敲代逮输硕屉只睹磅暑渣们猾困帘第10章排序-精品PPT课件第10章排序-精品PPT课件算法描述

34、：算法描述：算法描述：算法描述：void ShellSort(Record r , int n)void ShellSort(Record r , int n) for (d=n/2;d=1;d=d/2) / for (d=n/2;d=1;d=d/2) /以增量以增量以增量以增量d d进行直接插入排序进行直接插入排序进行直接插入排序进行直接插入排序 for (i=d; in; i+) for (i=d; i0 & temp.key0 & temp.keyrj.key; j=j-d) rj+d=rj; / rj+d=rj; /记录后移记录后移记录后移记录后移 d d个位置个位置个位置个位置 rj

35、+d=temp rj+d=temp 问题问题问题问题2 2：子序列内如何进行直接插入排序？：子序列内如何进行直接插入排序？：子序列内如何进行直接插入排序？：子序列内如何进行直接插入排序？场泥登积嚼币顺荒损县雅眨祷尤堂蕾泪遏卡寨当祟薛掠堕馈庸粹蚕篷篷畸第10章排序-精品PPT课件第10章排序-精品PPT课件oo希尔排序开始时增量较大，每个子序列中的记录个数较少，从希尔排序开始时增量较大，每个子序列中的记录个数较少，从希尔排序开始时增量较大，每个子序列中的记录个数较少，从希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数而排序速度较快；当增

36、量较小时，虽然每个子序列中记录个数而排序速度较快；当增量较小时，虽然每个子序列中记录个数而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。较多，但整个序列已基本有序，排序速度也较快。较多，但整个序列已基本有序，排序速度也较快。较多，但整个序列已基本有序，排序速度也较快。oo希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取增量增量增量增量的函数，而到目前为止尚的函数，而到目前为止尚的函数，而到目前为止尚的函数，而到目前为止尚未有人求得一种最好的增量序列。未有人求得一种最好的增量序列。未

37、有人求得一种最好的增量序列。未有人求得一种最好的增量序列。oo研究表明，希尔排序的时间性能在研究表明，希尔排序的时间性能在研究表明，希尔排序的时间性能在研究表明，希尔排序的时间性能在O O( (n n2 2) )和和和和O O( (nlognlog2 2n n) )之间。当之间。当之间。当之间。当n n在某个特定范围内，希尔排序所需的比较次数和记录的移动次在某个特定范围内，希尔排序所需的比较次数和记录的移动次在某个特定范围内，希尔排序所需的比较次数和记录的移动次在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为数约为数约为数约为O O( (n n1 1. .3 3 ) ) 。希尔排序

38、算法的时间性能希尔排序算法的时间性能忘珍履场稠诽奏明傍珐污叙邻鱼刷秦恍缅压嘘骸叙缮卒月赐勇阔东吼门建第10章排序-精品PPT课件第10章排序-精品PPT课件10.6 快速排序快速排序oo首先选一个首先选一个首先选一个首先选一个轴值轴值轴值轴值（即比较的基准），通过一趟排序将待排序记（即比较的基准），通过一趟排序将待排序记（即比较的基准），通过一趟排序将待排序记（即比较的基准），通过一趟排序将待排序记录录录录分割分割分割分割成独立的两部分，前一部分记录的关键码均成独立的两部分，前一部分记录的关键码均成独立的两部分，前一部分记录的关键码均成独立的两部分，前一部分记录的关键码均小于或等于小于或等于小

39、于或等于小于或等于轴值，后一部分记录的关键码均轴值，后一部分记录的关键码均轴值，后一部分记录的关键码均轴值，后一部分记录的关键码均大于或等于大于或等于大于或等于大于或等于轴值，然后分别对轴值，然后分别对轴值，然后分别对轴值，然后分别对这两部分重复上述方法，直到整个序列有序。这两部分重复上述方法，直到整个序列有序。这两部分重复上述方法，直到整个序列有序。这两部分重复上述方法，直到整个序列有序。oo需解决的关键问题：需解决的关键问题：需解决的关键问题：需解决的关键问题：n n如何选择轴值？如何选择轴值？如何选择轴值？如何选择轴值？n n如何实现分割（称一次划分）？如何实现分割（称一次划分）？如何实

40、现分割（称一次划分）？如何实现分割（称一次划分）？n n如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？n n如何判别快速排序的结束？如何判别快速排序的结束？如何判别快速排序的结束？如何判别快速排序的结束？掸舜嫉铸消快函六始稿技闲学列侥司贝航牡薪网涌愤藤次钻途诛槐慷鲜汕第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题1：如何选择轴值？：如何选择轴值？oo选择轴值的方法：选择轴值的方法：选择轴值的方法：选择轴值的方法：n n1.1.使用第一个记录的关键码；使用第一个记录的关键码；使用第

41、一个记录的关键码；使用第一个记录的关键码；n n2.2.选取序列中间记录的关键码；选取序列中间记录的关键码；选取序列中间记录的关键码；选取序列中间记录的关键码；n n3.3.比较序列中第一个记录、最后一个记录和中间记录的比较序列中第一个记录、最后一个记录和中间记录的比较序列中第一个记录、最后一个记录和中间记录的比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录关键码，取关键码居中的作为轴值并调换到第一个记录关键码，取关键码居中的作为轴值并调换到第一个记录关键码，取关键码居中的作为轴值并调换到第一个记录的位置；的位置；的位置；的位置；n n4.4.随机

42、选取轴值。随机选取轴值。随机选取轴值。随机选取轴值。oo选取不同轴值的效果：选取不同轴值的效果：选取不同轴值的效果：选取不同轴值的效果：n n决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。酣围赢了悯澳克集撅礼莉擎谷翱炎幕晃铂攒帖币斤钾琉叶淫彪捌芒淹但撒第10章排序-精品PPT课件第10章排序-精品PPT课件1313656527275050383849495555ji131338386565272750504949555513136565272750504949383

43、85555jjiiijijjj问题问题2：如何实现一次划分？：如何实现一次划分？垮初坎瑰凳序逆凛职纶套瓜棉弱卸养允伦迷玲赚汹之予潜柠盛缝秘伶屏怎第10章排序-精品PPT课件第10章排序-精品PPT课件oo解决方法：解决方法：解决方法：解决方法：oo 取第一个记录的关键字值作为基准，将第一个记录暂存于取第一个记录的关键字值作为基准，将第一个记录暂存于取第一个记录的关键字值作为基准，将第一个记录暂存于取第一个记录的关键字值作为基准，将第一个记录暂存于temptemp中，中，中，中，设两个变量设两个变量设两个变量设两个变量i i，j j分别指示将要划分的最左、最右记录的位置。分别指示将要划分的最左、

44、最右记录的位置。分别指示将要划分的最左、最右记录的位置。分别指示将要划分的最左、最右记录的位置。oo 将将将将j j指向的记录关键字值与基准值进行比较，如果指向的记录关键字值与基准值进行比较，如果指向的记录关键字值与基准值进行比较，如果指向的记录关键字值与基准值进行比较，如果j j指向的记录关指向的记录关指向的记录关指向的记录关键字值大，则键字值大，则键字值大，则键字值大，则j j前移一个位置；重复此过程，直到前移一个位置；重复此过程，直到前移一个位置；重复此过程，直到前移一个位置；重复此过程，直到j j指向的记录关键指向的记录关键指向的记录关键指向的记录关键字值小于基准值；若字值小于基准值；

45、若字值小于基准值；若字值小于基准值；若i i j j，则将，则将，则将，则将j j指向的记录移到指向的记录移到指向的记录移到指向的记录移到i i所指位置。所指位置。所指位置。所指位置。oo 将将将将i i指向的记录关键字值与基准值进行比较，如果指向的记录关键字值与基准值进行比较，如果指向的记录关键字值与基准值进行比较，如果指向的记录关键字值与基准值进行比较，如果i i指向的记录关指向的记录关指向的记录关指向的记录关键字值小，则键字值小，则键字值小，则键字值小，则i i后移一个位置；重复此过程，直到后移一个位置；重复此过程，直到后移一个位置；重复此过程，直到后移一个位置；重复此过程，直到i i指

46、向的记录关键指向的记录关键指向的记录关键指向的记录关键字值大于基准；若字值大于基准；若字值大于基准；若字值大于基准；若i i j j，则，则，则，则i i指向的记录移到指向的记录移到指向的记录移到指向的记录移到j j所指位置。所指位置。所指位置。所指位置。oo 重复重复重复重复、步，直到步，直到步，直到步，直到i i= =j j。问题问题2：如何实现一次划分？：如何实现一次划分？若支火度涕蓉诬睦务架万乎哼初翠摧各癌讽苗报刽抠瘪博帚奔舵圈汹透肌第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题2：如何实现一次划分？：如何实现一次划分？数撅仁耳菊容饶霓确眩颓洒魏卢最伴戏蛊勾管铡酵艘锤

47、虐淄篮焊克陈祝中第10章排序-精品PPT课件第10章排序-精品PPT课件算法描述：算法描述：算法描述：算法描述：int Partition(Record r , int i, int j)int Partition(Record r , int i, int j) temp= ri; temp= ri; while (ij) while (ij) while (i= temp.key) j- while (i= temp.key) j-； if (ij) ri+= rj; if (ij) ri+= rj; while (ij & ri.key= temp.key) i+; while (ij

48、& ri.key= temp.key) i+; if (ij) rj-= ri; if (ij) rj-= ri; ri = temp; ri = temp; return i; return i; 问题问题2：如何实现一次划分？：如何实现一次划分？骑夷但寥俺虫箔苟兜秋有叫坐伴大术憋择叔瓷椭玫芬犯葛疯卢去寐刊侈棘第10章排序-精品PPT课件第10章排序-精品PPT课件解决方法：解决方法：解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。13132727383

49、865655050494955551313272750503838494955556565ijij问题问题3：如何处理分割得到的两个待排序子序：如何处理分割得到的两个待排序子序列？列？ 懦朔改侨串淳艾教虚坪缩流蛤考靳建好她样别洪山熬甭兵究常凛烷绷盎嘲第10章排序-精品PPT课件第10章排序-精品PPT课件算法描述：算法描述：算法描述：算法描述：void QuickSort (Record r , int i, int j )void QuickSort (Record r , int i, int j ) if (ij) if (ij) pivot=Partition(r, i, j); pi

50、vot=Partition(r, i, j); QuickSort(r, i, pivot-1); QuickSort(r, i, pivot-1); QuickSort(r, pivot+1, j); QuickSort(r, pivot+1, j); 初始调用为初始调用为初始调用为初始调用为QuickSort(r, 1, n) QuickSort(r, 1, n) 问题问题3：如何处理分割得到的两个待排序子序：如何处理分割得到的两个待排序子序列？列？ 校陛亮沈弯镑寒吁孝呵洽锥栅恭葬妖送摸浩葬晃桥耙口耶凝班请察糖粗芝第10章排序-精品PPT课件第10章排序-精品PPT课件oo解决方法：解决方

51、法：解决方法：解决方法：oo若待排序列中只有一个记录，显然已有序，否则进行一次划若待排序列中只有一个记录，显然已有序，否则进行一次划若待排序列中只有一个记录，显然已有序，否则进行一次划若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递分后，再分别对分割所得的两个子序列进行快速排序（即递分后，再分别对分割所得的两个子序列进行快速排序（即递分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。归处理）。归处理）。归处理）。问题问题4：如何判别快速排序的结束？：如何判别快速排序的结束？ void QuickSort (Record r ,

52、 int i, int j )void QuickSort (Record r , int i, int j ) if (ij)if (ij) pivot=Partition(r, i, j); pivot=Partition(r, i, j); QuickSort(r, i, pivot-1); QuickSort(r, i, pivot-1); QuickSort(r, pivot+1, j); QuickSort(r, pivot+1, j); 遥闺甚扇醋椽霖钙邵疯恶症鱼账讼棋庞宁毁蛀莫沂仆咎蔷挝境英驳御直哇第10章排序-精品PPT课件第10章排序-精品PPT课件最坏情况：最坏情况：最坏

53、情况：最坏情况：每次划分只得到一个比上一次划分少一个记录的子序每次划分只得到一个比上一次划分少一个记录的子序每次划分只得到一个比上一次划分少一个记录的子序每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为列（另一个子序列为空），为列（另一个子序列为空），为列（另一个子序列为空），为 O O( (n n2 2) )。最好情况：最好情况：最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相

54、同，为右侧子表的长度相同，为右侧子表的长度相同，为O O( (n nloglog2 2n n) )。平均情况：平均情况：平均情况：平均情况：为为为为O O( (n nloglog2 2n n) )。)() 1(212 21 11 1nOnninn ni i= =- -= =- - - - - -= = = =）（快速排序的时间性能分析快速排序的时间性能分析澳酋扯触识骇紫氯轿夷通纠氏炸蹋翱靖帘犹柯镐旬枕霸瓮峭悸峪案棺唬桔第10章排序-精品PPT课件第10章排序-精品PPT课件快速排序的性能分析快速排序的性能分析oo快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。oo请举例说明。请

55、举例说明。给绥澈朋葱盯沟筐门级烈啊鞠遁闺脖敬轧春孪浙快敷穗雅歹太丰葬控大式第10章排序-精品PPT课件第10章排序-精品PPT课件oo简单选择排序的改进简单选择排序的改进简单选择排序的改进简单选择排序的改进oo改进的着眼点：改进的着眼点：改进的着眼点：改进的着眼点：n n如何如何如何如何减少减少减少减少关键码间的关键码间的关键码间的关键码间的比较比较比较比较次数。若能利用每趟比较后的次数。若能利用每趟比较后的次数。若能利用每趟比较后的次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值结果，也就是在找出键值最小记录的同时，也找出键值结果，也就是在找出键值最小记录的同时，也

56、找出键值结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，较小的记录，则可减少后面的选择中所用的比较次数，较小的记录，则可减少后面的选择中所用的比较次数，较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。从而提高整个排序过程的效率。从而提高整个排序过程的效率。从而提高整个排序过程的效率。10.7 堆排序堆排序肛肺歌茬雌需宣发森峡袁跳撑奇做俭随搔盒暖宦较呸汲怨噶取丢痈款防委第10章排序-精品PPT课件第10章排序-精品PPT课件堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的堆是具有下列性质的堆是具有下列性质的完全二叉树

57、完全二叉树完全二叉树完全二叉树：每个结点的值都：每个结点的值都：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆小根堆小根堆），），），），或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为（称为（称为大根堆大根堆大根堆大根堆）。）。）。）。182032364525385040281. 1. 小根堆的根结点是小根堆的根结点是小根堆

58、的根结点是小根堆的根结点是所有结点的最小者。所有结点的最小者。所有结点的最小者。所有结点的最小者。2. 2. 较小结点靠近根结较小结点靠近根结较小结点靠近根结较小结点靠近根结点，但不绝对。点，但不绝对。点，但不绝对。点，但不绝对。苟奶拴脏候砚铸吧月仰讶枷踩早盗泻膨东货名贼毛馆拣冲备壤软寓亢矾砒第10章排序-精品PPT课件第10章排序-精品PPT课件503845402836322018281. 1. 大根堆的根结点是大根堆的根结点是大根堆的根结点是大根堆的根结点是所有结点的最大者。所有结点的最大者。所有结点的最大者。所有结点的最大者。2. 2. 较大结点靠近根结较大结点靠近根结较大结点靠近根结较

59、大结点靠近根结点，但不绝对。点，但不绝对。点，但不绝对。点，但不绝对。堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树完全二叉树完全二叉树：每个结点的值都：每个结点的值都：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆小根堆小根堆），），），），或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左

60、右孩子结点的值（称为（称为（称为（称为大根堆大根堆大根堆大根堆）。）。）。）。帐础鼻字攒吝酞珐辛壶智坍铺絮浓苫愉悠账苗享彻刑作际北攘耙忘磷仟憋第10章排序-精品PPT课件第10章排序-精品PPT课件堆和序列的关系堆和序列的关系将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序

61、存储采用顺序存储采用顺序存储鞍锡鸽得倚董妓将吗仟彼苏堂庶镑夺胃恨恕窝嫁吉敷讣衫寸涅险么火蛋均第10章排序-精品PPT课件第10章排序-精品PPT课件oo基本思想：基本思想：基本思想：基本思想：首先将待排序的记录序列构造成一个堆，此时，选首先将待排序的记录序列构造成一个堆，此时，选首先将待排序的记录序列构造成一个堆，此时，选首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆

62、，这样又找出了次小的记录，以此类推，直的记录再调整成堆，这样又找出了次小的记录，以此类推，直的记录再调整成堆，这样又找出了次小的记录，以此类推，直的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。到堆中只有一个记录。到堆中只有一个记录。到堆中只有一个记录。oo需解决的关键问题需解决的关键问题需解决的关键问题需解决的关键问题? ?n n如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？n n如何处理堆顶记录？如何处理堆顶记录？如何处理堆顶记录？如何

63、处理堆顶记录？n n如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？ 厨厂江苇擒闭蔚渴衬袖旺贿埔服翠助浅口贫译末吸鬃竭寅皖磨喇嗜捻砧绑第10章排序-精品PPT课件第10章排序-精品PPT课件堆调整堆调整在一棵完全二叉树中，根结点的左右子树均是堆，如何在一棵完全二叉树中，根结点的左右子树均是堆，如何在一棵完全二叉树中，根结点的左右子树均是堆，如何在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？调整根结点，使整个完全二叉树成为一个堆

64、？调整根结点，使整个完全二叉树成为一个堆？调整根结点，使整个完全二叉树成为一个堆？283632161825321618253628闭丢婿耽因柞沾荷处是颊什郝泛牡翔驹册鲁北牵挎睫毅吸冬矛晌育淹腆霓第10章排序-精品PPT课件第10章排序-精品PPT课件void sift ( int r , int k, int m )/要筛选结点的编号为要筛选结点的编号为k，堆中最后一个结点的编号为，堆中最后一个结点的编号为m i=k; j=2*i; /将筛选记录暂存将筛选记录暂存 while (j=m ) /筛选还没有进行到叶子筛选还没有进行到叶子 if (jm & rjrj) break; else ri

65、rj; /将筛选记录移到正确位置将筛选记录移到正确位置 i=j; j=2*i; 堆调整堆调整算法描述：算法描述：蔬崇熊肌郝委湾甩汉晒港慧鬼聋刨摸韵瓮坚炒滇孟渣钢艺沟晃芝刻摹妨逻第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题问题问题1 1 1 1：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？282516321836163216282518362532162818362528323628161825教晶愤捞厂信底绢睹洁衅额骡肺迢凯荒五漠滁赞仕登瘤烟髓燕爹辉认螟捅第10章排序-精品PPT课件第10章排序-精

66、品PPT课件算法描述：算法描述：算法描述：算法描述：for (i=n/2; i=1; i-)for (i=n/2; i=1; i-) sift(r, i, n) ; sift(r, i, n) ; 最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是n n，则最后一个分支结点即为结点则最后一个分支结点即为结点则最后一个分支结点即为结点则最后一个分支结点即为结点n n的双亲，的双亲，的双亲，的双亲，其序号是其序号是其序号是其序号是n n/2/2。问题问题问题问题1 1 1 1：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？

67、如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？撤瞧底主毕押恩掩孟挠厕欢宰衔驹裸逆湿餐票岸除宦见刀状军巧致谜贤莆第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题问题问题2 2 2 2：如何处理堆顶记录？如何处理堆顶记录？如何处理堆顶记录？如何处理堆顶记录？3236281618253636 28 32 25 18 16 28 32 25 18 161 2 3 4 5 61 2 3 4 5 6对对应应交换交换16 28 32 25 18 16 28 32 25 18 36361 2 3 4 5 61 2 3 4 5 6对对应应321628361825爆紊虹拧绽棚萍照侯经

68、聘接兜躲住坑授职求膛塔护羚舆厉机瓷蚤系互秋镑第10章排序-精品PPT课件第10章排序-精品PPT课件算法描述：算法描述：算法描述：算法描述：r1rn-i+1;r1rn-i+1; 解决方法：解决方法：解决方法：解决方法：第第第第 i i 次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录r1r1与序列中第与序列中第与序列中第与序列中第n-i+1n-i+1个个个个记录记录记录记录rn-i+1rn-i+1交换。交换。交换。交换。问题问题问题问题2 2 2 2：如何处理堆顶记录？如何处理堆顶记录？如何处理堆顶记录？如何处理堆顶记录？政耳介制蝶林志称轿花淌婪瞬棵寝像

69、琢程区捷拄寻桌型刁霜砒废区寒控贤第10章排序-精品PPT课件第10章排序-精品PPT课件321628361825问题问题问题问题3 3 3 3：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？16281632361825283236181625敦勤杠腥遁达雀豪亏逛轴鸡顿虞什郝陈酌纬合不挣忻永索翁鲸耐灰邻伪吸第10章排序-精品PPT课件第10章排序-精品PPT课件解决方法：解决方法：解决方法：解决方法：第第第第 i i 次调整剩余记录，此时，剩余记录有次调整剩余记录，此时，剩余记录有次调整剩余记录，此时，剩余记录有次

70、调整剩余记录，此时，剩余记录有n n- -i i个，调整个，调整个，调整个，调整根结点至第根结点至第根结点至第根结点至第n n- -i i个记录。个记录。个记录。个记录。算法描述：算法描述：算法描述：算法描述：sift(r, 1, n-i);sift(r, 1, n-i);问题问题问题问题3 3 3 3：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？胯凸候撇舒枢腿红驮昼离啊岩捶无腕劈膜熔稠咀汹里万狠哟浮曝捂厘慰痢第10章排序-精品PPT课件第10章排序-精品PPT课件堆排序算法堆排序算法void HeapSort

71、 ( int r, int n)void HeapSort ( int r, int n) for (i=n/2; i=1; i for (i=n/2; i=1; i-) /) /初建堆初建堆初建堆初建堆 sift(r, i, n) ; sift(r, i, n) ; for (i=1; in; i+ ) for (i=1; in; i+ ) r1rn r1rn- - - -i+1; /i+1; /移走堆顶移走堆顶移走堆顶移走堆顶 sift(r, 1, n sift(r, 1, n- - - -i); /i); /重建堆重建堆重建堆重建堆 议狗执妥飞从奠毯润待竟松佩绸珐办革僧望绒修彬壳宰畏靠何

72、毁差硕大扩第10章排序-精品PPT课件第10章排序-精品PPT课件堆排序算法的性能分析堆排序算法的性能分析oo第第第第1 1个个个个forfor循环是初始建堆，需要循环是初始建堆，需要循环是初始建堆，需要循环是初始建堆，需要O O( (n n) )时间；时间；时间；时间；oo第第第第2 2个个个个forfor循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取n n-1-1次堆次堆次堆次堆顶记录，第顶记录，第顶记录，第顶记录，第 i i 次取堆顶记录重建堆需要次取堆顶记录重建堆需要次取堆顶记录重建堆需要次取堆顶记录重建堆需要O

73、 O(log(log2 2i i) )时间，时间，时间，时间，需要需要需要需要O O( (n nloglog2 2n n) )时间；时间；时间；时间；oo因此整个时间复杂度为因此整个时间复杂度为因此整个时间复杂度为因此整个时间复杂度为O O( (n nloglog2 2n n) )，这是堆排序的，这是堆排序的，这是堆排序的，这是堆排序的最最最最好好好好、最坏最坏最坏最坏和和和和平均平均平均平均的时间代价。的时间代价。的时间代价。的时间代价。栓肿嘘荫模皋方塌费弹汁劣瞎之庭焰掺货社学臭嘉需至驮壬闰釉扇险彦堤第10章排序-精品PPT课件第10章排序-精品PPT课件10.8 归并排序归并排序oo归并排

74、序的主要操作是归并排序的主要操作是归并归并，其主要思想是：，其主要思想是：将若干有序序列逐步归并，最终得到一个有将若干有序序列逐步归并，最终得到一个有序序列。序序列。oo归并：归并：将两个或两个以上的有序序列合并成将两个或两个以上的有序序列合并成一个有序序列的过程。一个有序序列的过程。 肺墙半妓失博宣蹋假啦燎闯租旱占孤勿涣遁靳拱卧享锑涕悍践遍九蓟农媚第10章排序-精品PPT课件第10章排序-精品PPT课件oo基本思想：基本思想：基本思想：基本思想：将一个具有将一个具有将一个具有将一个具有n n个待排序记录的序列看成个待排序记录的序列看成个待排序记录的序列看成个待排序记录的序列看成是是是是n n

75、个长度为个长度为个长度为个长度为1 1的有序序列，然后进行两两归并，得的有序序列，然后进行两两归并，得的有序序列，然后进行两两归并，得的有序序列，然后进行两两归并，得到到到到n n/2/2个长度为个长度为个长度为个长度为2 2的有序序列，再进行两两归并，得的有序序列，再进行两两归并，得的有序序列，再进行两两归并，得的有序序列，再进行两两归并，得到到到到n n/4/4个长度为个长度为个长度为个长度为4 4的有序序列，的有序序列，的有序序列，的有序序列，直至得到一个，直至得到一个，直至得到一个，直至得到一个长度为长度为长度为长度为n n的有序序列为止。的有序序列为止。的有序序列为止。的有序序列为止

76、。oo需解决的关键问题需解决的关键问题需解决的关键问题需解决的关键问题? ?n n如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？n n怎样完成一趟归并？怎样完成一趟归并？怎样完成一趟归并？怎样完成一趟归并？n n如何控制二路归并的结束？如何控制二路归并的结束？如何控制二路归并的结束？如何控制二路归并的结束？雁近誓肄何蘸勺辣柏谋薄岔醒祖渐喇逝泰苗袄载诸卒店篆壶瓶斤恃动咖嫉第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题问题问题1 1 1 1：如何将两个有序序列合成一个有序序列？如何将

77、两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60诅堕缘帆炉筐啄恰细转斡恃厉霍嘎玻惦熔塌芝麻挺茹锹登招娇固弟峻占垣第10章排序-精品PPT课件第10章排序-精品PPT课件602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60归并可以就地进行吗归并可以就地进行吗归并可以就地进行吗归并可以就地进行吗? ?问题问题问题问题1 1 1 1：如何将两个有序序列合

78、成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？趁舜宵斤圾伞腺凿槛挽涝祟飘氓塞幢臆址芭瓢唱盖朔室梯盛弄逃蓑瘦没箍第10章排序-精品PPT课件第10章排序-精品PPT课件在归并过程中，可能会破坏原在归并过程中，可能会破坏原在归并过程中，可能会破坏原在归并过程中，可能会破坏原来的有序序列，所以，将归并来的有序序列，所以，将归并来的有序序列，所以，将归并来的有序序列，所以，将归并的结果存入另外一个数组中。的结果存入另外一个数组中。的结果存入另外一个数组中。的结果存入另外一个数组中。 602031544556520 605 3

79、144 5565 60 20 31 5 44 55 65ij5kj20i31j60问题问题问题问题1 1 1 1：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？烟蛋蛇贴咀叹焦稻满禁缉设杖女网遂阴谴葱应斟墅颗干汤兑止版衙沟凑啡第10章排序-精品PPT课件第10章排序-精品PPT课件602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的长度一定相等吗子序列的长度一定相等吗子序列的长度一定相等吗子序列的长度一定相等吗? ?问题

80、问题问题问题1 1 1 1：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？憎潦所耕埠敝肋坑脯疗萎掩羽惧会张欧蔡珠完创锣顾急走住措淑差起莆四第10章排序-精品PPT课件第10章排序-精品PPT课件602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60问题问题问题问题1 1 1 1：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？捷辈趋鞘

81、据辉吮旧某妥锁哄凭凯个篙末劫拉千凑赏默蝉颅济瞳饲烤然潘固第10章排序-精品PPT课件第10章排序-精品PPT课件设相邻的有序序列为设相邻的有序序列为设相邻的有序序列为设相邻的有序序列为rs rmrs rm和和和和rm+1 rtrm+1 rt，归并，归并，归并，归并成一个有序序列成一个有序序列成一个有序序列成一个有序序列r1s r1t r1s r1t s m m+1 t r s t r1 ijk问题问题问题问题1 1 1 1：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？孩窃碎枢迟盲术奔仓欺读淖缩鸥

82、魂谅丽拨谍骏铃悍梗衔溢疑佣诀蘑译骨烤第10章排序-精品PPT课件第10章排序-精品PPT课件void Merge (int r , int r1 , int s, int m, int t )void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; i=s; j=m+1; k=s; while (i=m & j=t) while (i=m & j=t) if (ri=rj) r1k+=ri+; if (ri=rj) r1k+=ri+; else r1k+=rj+; else r1k+=rj+; if (i=m) wh

83、ile (i=m) / if (i=m) while (i=m) /收尾处理收尾处理收尾处理收尾处理 r1k+=ri+; / r1k+=ri+; /前一个子序列前一个子序列前一个子序列前一个子序列 else while (j=t) else while (j=t) r1k+=rj+; / r1k+=rj+; /后一个子序列后一个子序列后一个子序列后一个子序列 算法描述：算法描述：算法描述：算法描述：问题问题问题问题1 1 1 1：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？澜冀氛泡核朵革杯醒躇酸

84、佩牛馋耗霹国搂驰来绥察阶糠沃镭纤夸钨委蜜矿第10章排序-精品PPT课件第10章排序-精品PPT课件问题问题问题问题2 2：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？602031544556520 605 3144 556560 20 31 5 44 55 65 5 20 31 60 44 55 65在一趟归并中，除最后一个有序序列外，其它有序在一趟归并中，除最后一个有序序列外，其它有序在一趟归并中，除最后一个有序序列外，其它有序在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度序列中记录的个数相同，用长度序列中记录的个数相同，用长度序列

85、中记录的个数相同，用长度h h表示。表示。表示。表示。凛柏验芭揉卢魂杆瓜栓邱匀亏俯慕呸桨彬澄侧戴围芍簇朝堡席又挖扶气揖第10章排序-精品PPT课件第10章排序-精品PPT课件设参数设参数设参数设参数i i指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是2 2h h，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：若若若若i i n n-2-2h h+1+1，则相邻两个有序表的长度均为，则相邻两个有序表的长度

86、均为，则相邻两个有序表的长度均为，则相邻两个有序表的长度均为h h，执行，执行，执行，执行一次归并，完成后一次归并，完成后一次归并，完成后一次归并，完成后i i加加加加2 2h h，准备进行下一次归并；，准备进行下一次归并；，准备进行下一次归并；，准备进行下一次归并；20 605 3144 5565ihi=1n-2h+1=4n-2h+1问题问题问题问题2 2：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？奠犀土剧俐诌达雾羡琢盒颖煌滴化幢彩诊稀溢匣汝反迈涯带障臂折压阁潞第10章排序-精品PPT课件第10章排序-精品PPT课件算法描述：算法描述：算法描述：算法描述：

87、while (in-2h+1) while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; i+=2*h; 问题问题问题问题2 2：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？设参数设参数设参数设参数i i指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是2 2h h，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：

88、，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：若若若若i i n n-2-2h h+1+1，则相邻两个有序表的长度均为，则相邻两个有序表的长度均为，则相邻两个有序表的长度均为，则相邻两个有序表的长度均为h h，执行，执行，执行，执行一次归并，完成后一次归并，完成后一次归并，完成后一次归并，完成后i i加加加加2 2h h，准备进行下一次归并；，准备进行下一次归并；，准备进行下一次归并；，准备进行下一次归并；屿冗曾彪胃驱营皑岸述辈拐烤辕顿坯辛幽褥尊骄多驭皖如糊刚光匹贺棒劝第10章排序-精品PPT课件第10章排序-精品PPT课件若若若若i in n- -h h+1+1，则表示仍有

89、两个相邻有序表，一个长，则表示仍有两个相邻有序表，一个长，则表示仍有两个相邻有序表，一个长，则表示仍有两个相邻有序表，一个长度为度为度为度为h h，另一个长度小于，另一个长度小于，另一个长度小于，另一个长度小于h h，则执行两个有序表的归并，则执行两个有序表的归并，则执行两个有序表的归并，则执行两个有序表的归并，完成后退出一趟归并。完成后退出一趟归并。完成后退出一趟归并。完成后退出一趟归并。20 605 3144 5565ihi=4n-2h+1=4n-h+1=6n-2h+1n-h+1=n-h+1) if (i=n-h+1) for (k=i; k=n; k+) for (k=i; k=n; k

90、+) r1k=rk; r1k=rk; 若若若若i in-h+1n-h+1，则则则则表表表表明明明明只只只只剩剩剩剩下下下下一一一一个个个个有有有有序序序序表表表表，直直直直接接接接将将将将该该该该有序表送到有序表送到有序表送到有序表送到r1r1的相应位置，完成后退出一趟归并。的相应位置，完成后退出一趟归并。的相应位置，完成后退出一趟归并。的相应位置，完成后退出一趟归并。 问题问题问题问题2 2：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？：怎样完成一趟归并？设参数设参数设参数设参数i i指向待归并序列的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是指向待归并序列

91、的第一个记录，归并的步长是指向待归并序列的第一个记录，归并的步长是2 2h h，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：，在归并过程中，有以下三种情况：釜勿洗注掳吩帖麻阀屹鼓指漳鲍砖日妻领咱煮估出骗糠赤幸妓深笛郧厄甭第10章排序-精品PPT课件第10章排序-精品PPT课件void MergePass (int r , int r1 , int n, int h)void MergePass (int r , int r1 , int n, int h) i=1; i=1; while (i while (in n- - - -2h+1) /

92、2h+1) /情况情况情况情况1 1 Merge (r, r1, i, i+h-1, i+2*h Merge (r, r1, i, i+h-1, i+2*h- - - -1);1); i+=2*h; i+=2*h; if (i if (in n- - - -h+1) Merge (r, r1, i, i+hh+1) Merge (r, r1, i, i+h- - - -1, n); /1, n); /情况情况情况情况2 2 else for (k=i; k=n; k+) / else for (k=i; k=n; k+) /情况情况情况情况3 3 r1k=rk; r1k=rk; 一趟归并排序算

93、法一趟归并排序算法缘鹿魁辈呆国社葵娠碘助惦棋枷腋抬静营船译欧脉杆尝缝妮冕喳侧剔试津第10章排序-精品PPT课件第10章排序-精品PPT课件解决方法：解决方法：解决方法：解决方法：开始时，有序序列的长度开始时，有序序列的长度开始时，有序序列的长度开始时，有序序列的长度h=1h=1，结束时，有序序列的，结束时，有序序列的，结束时，有序序列的，结束时，有序序列的长度长度长度长度h=nh=n，用有序序列的长度来控制排序的结束。，用有序序列的长度来控制排序的结束。，用有序序列的长度来控制排序的结束。，用有序序列的长度来控制排序的结束。问题问题问题问题3 3 3 3：如何控制二路归并的结束？如何控制二路归

94、并的结束？如何控制二路归并的结束？如何控制二路归并的结束？侗鞘鸭乙卓跺路谦山互通青葫鄙莱待再停逸鄂正虱懦蔑池懊够旦泅扶荷搓第10章排序-精品PPT课件第10章排序-精品PPT课件算法描述：算法描述：算法描述：算法描述：void MergeSort (int r , int r1 , int n )void MergeSort (int r , int r1 , int n ) h=1; h=1; while (hn) while (hn) MergePass (r, r1, n, h); MergePass (r, r1, n, h); h=2*h; h=2*h; MergePass (r1,

95、 r, n, h); MergePass (r1, r, n, h); h=2*h; h=2*h; 问题问题问题问题3 3 3 3：如何控制二路归并的结束？如何控制二路归并的结束？如何控制二路归并的结束？如何控制二路归并的结束？欺爪呸艺除觉互遂阻苯哗躬百逝讨搪兼绝悼躺懈晾插农歇烂唁蔡眶兵资岩第10章排序-精品PPT课件第10章排序-精品PPT课件二路归并排序算法的性能分析二路归并排序算法的性能分析二路归并排序算法的性能分析二路归并排序算法的性能分析oo时间性能：时间性能：时间性能：时间性能：n n一趟归并操作是将一趟归并操作是将一趟归并操作是将一趟归并操作是将r1rnr1rn中相邻的长度为中相

96、邻的长度为中相邻的长度为中相邻的长度为h h的有序序列的有序序列的有序序列的有序序列进行两两归并，并把结果存放到进行两两归并，并把结果存放到进行两两归并，并把结果存放到进行两两归并，并把结果存放到r11r1nr11r1n中，这需要中，这需要中，这需要中，这需要O O( (n n) )时间。整个归并排序需要进行时间。整个归并排序需要进行时间。整个归并排序需要进行时间。整个归并排序需要进行loglog2 2n n趟，因此，总的趟，因此，总的趟，因此，总的趟，因此，总的时间代价是时间代价是时间代价是时间代价是O O( (n nloglog2 2n n) )。这是归并排序算法的。这是归并排序算法的。这

97、是归并排序算法的。这是归并排序算法的最好最好最好最好、最坏最坏最坏最坏、平均平均平均平均的时间性能。的时间性能。的时间性能。的时间性能。oo空间性能：空间性能：空间性能：空间性能：n n算法在执行时，需要占用与原始记录序列同样数量的存算法在执行时，需要占用与原始记录序列同样数量的存算法在执行时，需要占用与原始记录序列同样数量的存算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为储空间，因此空间复杂度为储空间，因此空间复杂度为储空间，因此空间复杂度为O O( (n n) )。察裙揖毯遣菏倍啸看铣贤抢斌龙邱震虹纬厄脏窿脚蝉仙太伪滑霖腹庚隅随第10章排序-精品PPT课件第10章

98、排序-精品PPT课件各种排序方法的比较各种排序方法的比较各种排序方法的比较各种排序方法的比较oo对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：oo时间复杂性；时间复杂性；时间复杂性；时间复杂性；oo空间复杂性；空间复杂性；空间复杂性；空间复杂性；oo稳定性；稳定性；稳定性；稳定性；oo算法简单性；算法简单性；算法简单性；算法简单性；oo待排序记录个数待排序记录个数待排序记录个数待排序记录个数n n的大小；的大小；的大小；的大小；oo记录本身信息量的大小；记录本身信息量的大小；记录本身信息量

99、的大小；记录本身信息量的大小；oo关键码的分布情况。关键码的分布情况。关键码的分布情况。关键码的分布情况。骨都论右滑戊挡函楚和抽飘及拄束厢稼掇绦吱阜盈聚陇爪贼玫赏眩纸伞勇第10章排序-精品PPT课件第10章排序-精品PPT课件时间复杂度比较时间复杂度比较时间复杂度比较时间复杂度比较各种排序方法的比较各种排序方法的比较排序方法排序方法平均情况平均情况最好情况最好情况最坏情况最坏情况直接插入排序直接插入排序O(n2)O(n)O(n2)希希尔尔排序排序O(nlog2n)O(n1.3)O(n2)冒泡排序冒泡排序O(n2)O (n)O(n2)快速排序快速排序O(nlog2n)O(nlog2n)O(n2)

100、简单选择排序排序O(n2)O(n2)O(n2)堆排序堆排序O(nlog2n)O(nlog2n)O (nlog2n)归并排序并排序O(nlog2n)O(nlog2n)O(nlog2n)贡序恼过灯宠浪掸鲁筋风挖棉龙赂裳芋粤沮揭饯桂访虱潍搂郴峭链筐唇聂第10章排序-精品PPT课件第10章排序-精品PPT课件排序方法排序方法排序方法排序方法辅辅助空助空助空助空间间直接插入排序直接插入排序直接插入排序直接插入排序O O(1)(1)希希希希尔尔尔尔排序排序排序排序O O(1)(1)冒泡排序冒泡排序冒泡排序冒泡排序O O(1)(1)快速排序快速排序快速排序快速排序O O(log(log2 2n n) ) O

101、 O( (n n) )简单选择简单选择排序排序排序排序O O(1)(1)堆排序堆排序堆排序堆排序O O(1)(1)归归并排序并排序并排序并排序O O( (n n) )空间复杂度比较空间复杂度比较空间复杂度比较空间复杂度比较各种排序方法的比较各种排序方法的比较巫乙澎孙翼茂孽莲准妨险临簧园肝坤穆弛卯屈累坊纤衷匣异幢炒逗躬右扰第10章排序-精品PPT课件第10章排序-精品PPT课件稳定性比较稳定性比较稳定性比较稳定性比较oo所有排序方法可分为两类，所有排序方法可分为两类，n n（1 1）一类是稳定的，包括直接插入排序、冒泡）一类是稳定的，包括直接插入排序、冒泡）一类是稳定的，包括直接插入排序、冒泡）

102、一类是稳定的，包括直接插入排序、冒泡排序、直接选择排序和归并排序；排序、直接选择排序和归并排序；排序、直接选择排序和归并排序；排序、直接选择排序和归并排序；n n（2 2）另一类是不稳定的，包括希尔排序、快速）另一类是不稳定的，包括希尔排序、快速）另一类是不稳定的，包括希尔排序、快速）另一类是不稳定的，包括希尔排序、快速排序和堆排序。排序和堆排序。排序和堆排序。排序和堆排序。涧醚壁磷卑吼忧镶跳载濒法轴锈胚恋疽屑碟澳煽铱蛛巧够蠕椿绞胰怕襄泵第10章排序-精品PPT课件第10章排序-精品PPT课件算法简单性比较算法简单性比较算法简单性比较算法简单性比较oo从算法简单性看，从算法简单性看，n n（1

103、 1）一类是简单算法，包括直接插入排序、直）一类是简单算法，包括直接插入排序、直）一类是简单算法，包括直接插入排序、直）一类是简单算法，包括直接插入排序、直接选择排序和冒泡排序，接选择排序和冒泡排序，接选择排序和冒泡排序，接选择排序和冒泡排序，n n（2 2）另一类是改进后的算法，包括希尔排序、）另一类是改进后的算法，包括希尔排序、）另一类是改进后的算法，包括希尔排序、）另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很堆排序、快速排序和归并排序，这些算法都很堆排序、快速排序和归并排序，这些算法都很堆排序、快速排序和归并排序，这些算法都很复杂。复杂。复杂。复杂。亭寐俏

104、畦昭帚斌幢撑赂蹭川该楞擂酋幌区挤谚甜献桔俐寄呵混饥涨抖柴净第10章排序-精品PPT课件第10章排序-精品PPT课件待排序的记录个数比较待排序的记录个数比较待排序的记录个数比较待排序的记录个数比较oo从待排序的记录个数从待排序的记录个数n的大小看，的大小看，n越小，采越小，采用简单排序方法越合适，用简单排序方法越合适，n越大，采用改进越大，采用改进的排序方法越合适。因为的排序方法越合适。因为n越小，越小，O(n2)同同O(nlog2n)的差距越小，并且输入和调试简单的差距越小，并且输入和调试简单算法比输入和调试改进算法要少用许多时间。算法比输入和调试改进算法要少用许多时间。咋劣徊荫柒诺沼妥秩溃勘

105、任分尊弛笋眯苫敷太那邑邯称首狠驴予龙句伏矽第10章排序-精品PPT课件第10章排序-精品PPT课件记录本身信息量比较记录本身信息量比较记录本身信息量越大，移动记录所花费的时间就越多，记录本身信息量越大，移动记录所花费的时间就越多，记录本身信息量越大，移动记录所花费的时间就越多，记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。所以对记录的移动次数较多的算法不利。所以对记录的移动次数较多的算法不利。所以对记录的移动次数较多的算法不利。排序方法排序方法排序方法排序方法最好情况最好情况最好情况最好情况最坏情况最坏情况最坏情况最坏情况平均情况平均情况平均情况平均情况直

106、接插入排序直接插入排序直接插入排序直接插入排序O O( (n n) )O O( (n n2 2) )O O( (n n2 2) )冒泡排序冒泡排序冒泡排序冒泡排序0 0O O( (n n2 2) )O O( (n n2 2) )直接选择排序直接选择排序直接选择排序直接选择排序0 0O O( (n n) )O O( (n n) )渴砂蓄蕊檀毡井酗旅盔融岳候露酉初组勇徐旺胜出滚选虑梢滇想慕御九盏第10章排序-精品PPT课件第10章排序-精品PPT课件关键码的分布情况比较关键码的分布情况比较当待排序记录按关键码有序时，插入排序和冒泡排当待排序记录按关键码有序时，插入排序和冒泡排序能达到序能达到O(

107、(n) )的时间复杂度；对于快速排序而言，的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为这是最坏的情况，此时的时间性能蜕化为O( (n2) )；选；选择排序、堆排序和归并排序的时间性能不随记录序择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。列中关键字的分布而改变。担吩核边墒鹤蘑沉彼挝以尉豹研躁腔臭系图廷葵俞莱恍冈增伤咀厚陌妊务第10章排序-精品PPT课件第10章排序-精品PPT课件关键码的分布情况比较关键码的分布情况比较关键码的分布情况比较关键码的分布情况比较oo当待排序记录按关键码有序时，插入排序和当待排序记录按关键码有序时，插入排序和冒泡排序能达到冒泡排序能达到O(n)的时间复杂度；对于快的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间速排序而言，这是最坏的情况，此时的时间性能蜕化为性能蜕化为O(n2)；选择排序、堆排序和归并；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分排序的时间性能不随记录序列中关键字的分布而改变。布而改变。纵躺油卡碳凝激俯觅剐渐腊润迅摹杂肾秦巨某凡瞻婿僚秃肛凸腮赫小拳沏第10章排序-精品PPT课件第10章排序-精品PPT课件