数据结构第十章幻灯片.ppt
《数据结构第十章幻灯片.ppt》由会员分享,可在线阅读,更多相关《数据结构第十章幻灯片.ppt(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第1页,共47页,编辑于2022年,星期六排序排序:设设 n 个记录的序列为个记录的序列为 R1,R2,R3,.,Rn 其相应的关键字序列为其相应的关键字序列为 K1,K2,K3,.,Kn 若规定若规定 1,2,3,.,n 的一个排列的一个排列 p1,p2,p3,.,pn,使得相应的关键字满足如下非递减关系使得相应的关键字满足如下非递减关系:Kp Kp Kp .Kp123n则原序列变为一个按关键字有序的序列则原序列变为一个按关键字有序的序列:Rp ,Rp ,Rp ,.,Rp123n 此操作过程称为此操作过程称为排序排序。第2页,共47页,编辑于2022年,星期六稳定排序稳定排序 与与 不稳定排
2、序不稳定排序假设假设 Ki=Kj,且排序前序列中,且排序前序列中 Ri 领先于领先于 Rj;若在排序后的序列中若在排序后的序列中 Ri 仍领先于仍领先于 Rj,则称排序方法是,则称排序方法是稳定稳定的的。若在排序后的序列中若在排序后的序列中 Rj 仍领先于仍领先于 Ri,则称排序方法是,则称排序方法是不稳不稳定的定的。例,序列例,序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15稳定的稳定的若排序后得若排序后得 3 6 8 8 9 15不稳定的不稳定的第3页,共47页,编辑于2022年,星期六内部排序内部排序 与与 外部排序外部排序内部排序内部排序:指的是待排序记录存
3、放在计算机指的是待排序记录存放在计算机随机存储器随机存储器中进行中进行的排序过程。的排序过程。外部排序外部排序:指的是待排序记录的数量很大,以致内存一次不指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对能容纳全部记录,在排序过程中尚需对外存外存进行访问的排进行访问的排序过程。序过程。第4页,共47页,编辑于2022年,星期六内部排序内部排序按照排序过程中所依据的原则的不同可以分类为按照排序过程中所依据的原则的不同可以分类为:插入排序插入排序 交换排序交换排序(快速排序快速排序)选择排序选择排序 归并排序归并排序 基数排序基数排序 二叉排序树排序二叉排序树排序第5页,
4、共47页,编辑于2022年,星期六10.2 插入排序插入排序10.2.1 直接插入排序直接插入排序思想思想:利用有序表的插入操作进行排序利用有序表的插入操作进行排序有序表的插入有序表的插入:将一个记录插入到已排好序的有序表中,从将一个记录插入到已排好序的有序表中,从而得到一个新的有序表。而得到一个新的有序表。例,序列例,序列 13 27 38 65 76 97 插入插入 4913 27 38 49 65 76 97第6页,共47页,编辑于2022年,星期六例,序列例,序列 49 38 65 97 76 13 27 初始,初始,S=49 ;38 49 算法描述算法描述:初始,令第初始,令第 1
5、个元素作为初始有序表;个元素作为初始有序表;依次插入第依次插入第 2,3,k 个元素构造新的有序表;个元素构造新的有序表;直至最后一个元素;直至最后一个元素;38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用直接插入排序算法主要应用比较比较和和移动移动两种操作。两种操作。第7页,共47页,编辑于2022年,星期六10.2.2 希尔希尔(shell)排序排序分析直接插入排序分析直接插入排序1.若待排序记录序列按关键字若待排序记录序列按关键字基本有序基本有序,则排序效率,则排
6、序效率可大大提高;可大大提高;2.待排序记录总数越少,排序效率越高;待排序记录总数越少,排序效率越高;第8页,共47页,编辑于2022年,星期六思想思想:先将待排序记录序列分割成为若干子序列分别进行直接插入排序;先将待排序记录序列分割成为若干子序列分别进行直接插入排序;待整个序列中的记录基本有序后,再全体进行一次直接插入排序。待整个序列中的记录基本有序后,再全体进行一次直接插入排序。例,序列例,序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76第9
7、页,共47页,编辑于2022年,星期六第二趟排序第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764 27 49 6519 48 97第三趟排序第三趟排序4 13 19 27 38 48 49 55 65 76 97第10页,共47页,编辑于2022年,星期六10.3 交换排序交换排序10.3.1 冒泡排序冒泡排序思想思想:通过不断比较相邻元素大小,进行交换来实现排序。通过不断比较相邻元素大小,进行交换来实现排序。首先将第一个元素与第二个元素比较大小,若为逆序,则交换;首先将第一个元素与第二个元素比较
8、大小,若为逆序,则交换;然后比较第二个元素与第三个元素的大小,若为逆序,则交换;然后比较第二个元素与第三个元素的大小,若为逆序,则交换;.直至比较第直至比较第 n-1 个元素与第个元素与第 n 个元素的大小,若为逆序,则交换;个元素的大小,若为逆序,则交换;第一趟排序第一趟排序:结果结果:关键字最大关键字最大的记录被交换至的记录被交换至最后最后一个元素位置上。一个元素位置上。第11页,共47页,编辑于2022年,星期六例,序列例,序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初初始始第第一一趟趟排排序序后后最大值最大值13
9、4927 49次大值次大值第第二二趟趟排排序序后后38 13 2713 2713 38 27 38第第三三趟趟排排序序后后第第四四趟趟排排序序后后第12页,共47页,编辑于2022年,星期六10.3.2 快速排序快速排序冒泡排序的一种改进算法。冒泡排序的一种改进算法。思想思想:以以首记录首记录作为作为轴记录轴记录,从前、后双向扫描序列,通过交换,实现大值记录,从前、后双向扫描序列,通过交换,实现大值记录后移,小值记录前移,最终将轴记录安置在一个适当的位置。后移,小值记录前移,最终将轴记录安置在一个适当的位置。(小值记录在小值记录在前、大值记录在后前、大值记录在后)轴记录轴记录将原序列分割成两部
10、分,依次对前后两部分重新设定轴记录,继而分将原序列分割成两部分,依次对前后两部分重新设定轴记录,继而分别再进行快速排序。别再进行快速排序。直至整个序列有序。直至整个序列有序。第13页,共47页,编辑于2022年,星期六例,序列例,序列 49 38 65 97 76 13 27 52 第一趟排序第一趟排序49 38 65 97 76 13 27 52ij从从前前寻找寻找大于大于轴记录的记录,从轴记录的记录,从后后寻找寻找小于小于轴记录的记录轴记录的记录;ij交换交换大值记录与小值记录大值记录与小值记录;27 65重复上述两步操作,直至重复上述两步操作,直至 i j;ji13 97ji交换交换轴记
11、录轴记录和标识和标识 j 指示的记录指示的记录。13 49第14页,共47页,编辑于2022年,星期六第一趟排序后第一趟排序后 13 38 27 49 76 97 65 52 第二趟排序第二趟排序13 38 2776 97 65 52 49 将序列分成两部分,分别进行新的快速排序;将序列分成两部分,分别进行新的快速排序;第二趟排序后第二趟排序后13 38 2765 52 76 97 第三趟排序第三趟排序38 2765 52第三趟排序后第三趟排序后27 3852 65最终有序序列为最终有序序列为:13 27 38 52 65 76 97第15页,共47页,编辑于2022年,星期六10.4 选择排
12、序选择排序思想思想:每一趟都选出一个最大或最小的元素,并放在合适每一趟都选出一个最大或最小的元素,并放在合适的位置。的位置。简单选择排序简单选择排序 树形选择排序树形选择排序 堆排序堆排序第16页,共47页,编辑于2022年,星期六10.4.1 简单选择排序简单选择排序思想思想:第第 1 趟选择趟选择:从从 1n 个记录中选择关键字最小的记录,并和第个记录中选择关键字最小的记录,并和第 1 个记录交换。个记录交换。第第 2 趟选择趟选择:从从 2n 个记录中选择关键字最小的记录,并和第个记录中选择关键字最小的记录,并和第 2 个记录交换。个记录交换。第第n-1趟选择趟选择:从从 n-1n 个记
13、录中选择关键字最小的记录,并和第个记录中选择关键字最小的记录,并和第 n-1 个个记录交换。记录交换。.第17页,共47页,编辑于2022年,星期六例,序列例,序列 49 38 97 65 76第第 1 趟选择趟选择:min38 49 97 65 76第第 2 趟选择趟选择:min38 49 97 65 76第第 3 趟选择趟选择:min38 49 65 97 76第第 4 趟选择趟选择:min38 49 65 76 97第18页,共47页,编辑于2022年,星期六选择排序的主要操作是进行关键字间的选择排序的主要操作是进行关键字间的比较比较。在在 n 个关键字中选出最小值,至少需要个关键字中选
14、出最小值,至少需要 n-1 次比较次比较。在剩余的在剩余的 n-1 个关键字中选出最小值,至少需要个关键字中选出最小值,至少需要 n-2 次比较次比较?如果能利用前如果能利用前 n-1 次比较所得信息,可以减少后面选择的比较次数。次比较所得信息,可以减少后面选择的比较次数。体育比赛中的锦标赛体育比赛中的锦标赛:第19页,共47页,编辑于2022年,星期六10.4.3 堆排序堆排序堆堆:一棵完全二叉树,任一个非终端结点的值均小于等于一棵完全二叉树,任一个非终端结点的值均小于等于(或大于等于或大于等于)其左、右儿子结点的值。其左、右儿子结点的值。例,例,1285473053362491963811
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第十 幻灯片
限制150内