第二十讲.ppt
《第二十讲.ppt》由会员分享,可在线阅读,更多相关《第二十讲.ppt(46页珍藏版)》请在三一文库上搜索。
1、第二十讲,一、第九章知识回顾,二、排序,2,19. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 LL B. LR C. RL D. RR 27. 设有一组记录的关键字为19,14,23,1,68,20,84,27,55,11,10,79,用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有( )个记录。 A1 B. 2 C. 3 D. 4 31. 设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个
2、,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( ) A8 B3 C5 D9 32. 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( ) Ak-1次 B. k次 C. k+1次 D. k(k+1)/2次,C,D,D,D,3,34. 散列函数有一个共同的性质,即函数值应当以( )取其值域的每个值。 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 35. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列
3、表中。 ( )元素59存放在散列表中的 A 8 B. 9 C. 10 D. 11 (2)存放元素59需要搜索的次数是( )。 A 2 B. 3 C. 4 D. 5 36. 将10个元素散列到100000个单元的哈希表中,则( )产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会,D,D,C,C,4,第10章 排序,排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,本章导读,排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序
4、列。由于需要排序的数据表的基本特性可能存在差异,使得排序方法也不同。如何合理地组织数据的逻辑顺序,按照何种方式排出的序列最有效?这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法,讨论其性能和特点,并在此基础上进一步讨论各种方法的适用场合,以便在实际应用中能根据具体的问题选择合适的排序方法。,10.1 排序的基本概念,10.1.1 排序及其分类,1排序概念,排序(sorting)又称分类,是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值(关键字)递增或递减的次序重新排列的过程。,排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检
5、索的例子屡见不鲜。如电话簿、病历、档案室中的档案、图书馆和各种词典的目录表等,几乎都需要对有序数据进行操作。,假设含有n个记录的序列为: R1,R2 ,Rn (1) 其相应的关键字序列为: K1,K2 ,Kn 需确定1,2, ,n的一种排序p1,p2, ,pn,使其 相应的关键字满足如下关系: Kp1Kp2Kpn (2) 即使得式(1)的序列成为一个按关键字有序的序列 R p1,R p2 ,Rpn (3) 这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。,2排序分类,增排序和减排序:如果排序的结果是按关键字从小到大的次序排列的,就是增排序,否则就是减排序。,(2)稳定排序和
6、不稳定排序:假设Ki=Kj(1in,1jn,ij),且在排序前的序列中Ri领先于Rj(即ij)。若在排序后的排序中Ri仍领先于Rj,即那些具有相同关键字的记录,经过排序后它们的相对次序仍然保持不变,则称这种排序方法是稳定的;反之,若Rj领先于Ri,则称所用的方法是不稳定的。,(3) 内部排序与外部排序:在排序中,若数据表中的所有记录的排列过程都是在内存中进行的,称为内部排序。由于待排序的记录数量太多,在排序过程中不能同时把全部记录放在内存,需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程,称为外部排序。在外部排序情况下,只有部分记录进入内存,在内存中进行内部排序,待排序完成后再交
7、换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行,直到全部记录排出次序为止。显然,内部排序是外部排序的基础,本章主要介绍内部排序的各种方法。,10.1.2 排序算法的效率分析,与许多算法一样,对各种排序算法性能的评价主要从两个方面来考虑,一是时间性能;二是空间性能。,1 时间复杂度分析,排序算法的时间复杂度可用排序过程中记录之间关键字的比较次数与记录的移动次数来衡量。,在本章各节中讨论算法的时间复杂度时,一般都按平均时间复杂度进行估算;对于那些受数据表中记录的初始排列及记录数目影响较大的算法,按最好情况和最坏情况分别进行估算。,2空间复杂度分析,排序算法
8、的空间复杂度是指算法在执行时所需的附加存储空间,也就是用来临时存储数据的内存使用情况。 在以后的排序算法中,若无特别说明,均假定待排序的记录序列采用顺序表结构来存储,即数组存储方式,并假定是按关键字递增方式排序。为简单起见,假设关键字类型为整型。待排序的顺序表类型的类型定义如下: typedef int KeyType /定义关键字类型 typedef struct dataType /记录类型 keytype key; /关键字项 elemtype otherelement; /其他数据项 RecType;,10.2 插入排序,插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入
9、到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。也就是说,将待序列表分成左右两部分,左边为有序表(有序序列),右边为无序表(无序序列)。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中,构成新的有序序列。,根据不同的插入方法,插入排序算法主要包括:直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入排序、折半插入排序和希尔排序。,10.2.1 直接插入排序,直接插入排序(Insertion Sort)是所有排序方法中最简单的一种排序方法。其基本原理是顺次地从无序表中取出记录Ri(1in),与有序表中记录的关键字逐个进行比较,找出其应该插入的位置,再
10、将此位置及其之后的所有记录依次向后顺移一个位置,将记录Ri插入其中。 假设待排序的n个记录为R1,R2 ,Rn,初始有序表为R1,初始无序表为R2 Rn。当插入第i个记录Ri(2in)时,有序表为R1Ri-1,无序表为Ri Rn。将关键字K i依次与Ki-1,Ki-2 ,K1进行比较,找出其应该插入的位置,将该位置及其以后的记录向后顺移,插入记录Ri,完成序列中第i个记录的插入排序。当完成序列中第n个记录Rn的插入后,整个序列排序完毕。,向有序表中插入记录,主要完成如下操作: (1) 搜索插入位置。 (2) 移动插入点及其以后的记录空出插入位置。 (3) 插入记录。,假设将n个待排序的记录顺序
11、存放在长度为n+1的数组R1Rn 中。R0作为辅助空间,用来暂时存储需要插入的记录,起监视哨的作用。直接插入排序算法如下:,void Insert_Sort(int R,int n) int i,j; for(i=2;i=n; i+) /表示待插入元素的下标 R0=Ri; /设置监视哨保存待插入元素,腾出Ri空间 j=i-1; /j指示当前空位置的前一个元素 while(R0.keyRj.key)/搜索插入位置并后移腾出空 Rj+1=Rj; j-; Rj+1=R0; /插入元素 ,显然,开始时有序表中只有1个记录R1,然后需要将R2Rn的记录依次插入到有序表中,总共要进行n-1次插入操作。首先
12、从无序表中取出待插入的第i个记录Ri,暂存在R0中;然后将R0.key依次与Ri-1.key,Ri-2.key,进行比较,如果R0.keyRi-j.key(1ji-1),则将Ri-j后移一个单元;如果R0.keyRi-j.key,则找到R0插入的位置i-j+1,此位置已经空出,将R0 (即Ri)记录直接插入即可。然后采用同样的方法完成下一个记录Ri+1的插入排序。如此不断进行,直到完成记录Rn的插入排序,整个序列变成按关键字非递减的有序序列为止。在搜索插入位置的过程中,R0.key与Ri-j.key进行比较时,如果j=i,则循环条件 R0.keyRi-j.key不成立,从而退出while 循环
13、。由此可见R0起到了监视哨的作用,避免了数组下标的出界。,【例10-1】假设有7个待排序的记录,它们的关键字分别为23,4,15,8,19,24,15,用直接插入法进行排序。,【解】直接插入排序过程如图10-1所示。方括号 中为已排好序的记录的关键字,有两个记录的关键字都为15,为表示区别,将后一个15加下划线。,空间性能:该算法仅需要一个记录的辅助存储空间,空间复杂度为O(1)。,稳定性:由于该算法在搜索插入位置时遇到关键字值相等的记录时就停止操作,不会把关键字值相等的两个数据交换位置,所以该算法是稳定的。,时间性能:整个算法执行for循环n-1次,每次循环中的基本操作是比较和移动,其总次数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二十
链接地址:https://www.31doc.com/p-2581565.html