收藏 分销(赏)

第四部分-查找与排序技术(new).ppt

上传人:仙人****88 文档编号:14761510 上传时间:2026-11-15 格式:PPT 页数:31 大小:386KB 下载积分:10 金币
下载 相关
第四部分-查找与排序技术(new).ppt_第1页
第1页 / 共31页
第四部分-查找与排序技术(new).ppt_第2页
第2页 / 共31页


点击查看更多>>
资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.6,查找与排序,2.6.1,查找的基本概念,所谓查找:根据一个给定的元素,在数据结构中根据不同策略确定符合给定元素值的数据元素的过程。,2.6.2,静态查找技术,根据策略可以分成三大类:,1,、顺序查找法,2,、有序表的对分查找法,3,、分块查找法,1,顺序查找法,顺序查找法又称为顺序搜索法。基本方法如下:,1,、从线性表的第一个元素开始,依次将线性表中元素与给定元素的值进行比较。,2,、相等则表示找到,否则表示失败。如果遍历了整个表都没有找到,说明表中没有要找的元素。,从上面的方法来看,其顺序查找的效率很低,但在以下两种情况中,却只能使用顺序查找法:,1,、线性表是无序表,2,、采用链式存储的有序线性表,2,有序表的对分查找法,对分查找法,只应用于顺序存储的有序表。,假设有序线性表的长度为,n,,被查元素为,x,,则对分法如下:,1,、将,x,与线性表的中间项进行比较,若中间项的值等于,x,,说明查找成功;,2,、若,x,小于中间项,则在表的前面部分进行相同的查找,否则在表的后面部分进行查找。,3,、此过程直到查找成功或者子表长度为,0,时结束。,对分查找法在最坏的情况下,也只比较,log,2,N,次,算法程序,int search_SL_List(int*v,int start,int end,int x),int k;,while(start=end),k=(start+end)/2;,if(vk=x)return k;,if(vk x),start=k+1;,else,end=k-1;,return-1;,3,分块查找,分块查找又称索引顺序查找。它是一种顺序查找的改进策略,用于在分块有序表中查找。,所谓分块是指将长度为,N,的线性表分成,M,个子表,各子表的长度可以相等,也可以不相等,但要求后一子表的每一个元素都要大于前一个子表的所有元素。,分块有序表的结构可以分为两部分:,1,、线性表本身是顺序存储结构,2,、再建立一个索引表,线性表中每个子表建立一个索引节点。索引节点包括两部分:一是数据域,一是指针域。数据域存放对应子表中的最大元素值,指针域用于指示子表第一个元素的在整个表中序号。,3,分块查找,上图查找过程:首先查找索引表,确定查找的子表,然后再相应的子表中应顺序表查找法查找。,struct indnode,int key;,int k;,;,二叉排序树的定义,二叉排序树可能为一棵空的二叉树,若非空则必须满足以下特征:,(,1,)根结点左子树中所有结点的关键字小于根结点的关键字;,(,2,)根结点右子树中所有结点的关键字大于或等于根结点的关键字;,(,3,)根结点的左右子树也都是二叉排序树。,一棵二叉排序树,2.6.3,动态查找技术,建立了二叉排序树之后,若查找过程中不插入或删除元素,(,静态查找,),,则在二叉排序树中查找方法为:,1),将给定数据,key,与根结点关键字,x,进行比较,若,key=x,则查找成功;,2),若,keyx,,则与右子树的根结点的关键字值进行比较。,重复上述步骤,直到查找成功;或者一直比较到叶子结点也找不到目标元素,则查找失败。,可定义二叉排序树结点如下:,typedef struct Node,KeyType x;/,关键字,struct Node*left,*right;,BinNode;,typedef BinNode*BinNodePtr;,二叉排序树查找算法(静态查找)实现:,BinNode*search_btree(BinNodePtr p,KeyType key),while(p!=NULL&p-x!=key),if(keyx)p=p-left;,elsep=p-right;,return,p;,进行动态查找时,查找过程还涉及到插入新结点。其方法为:,(1),在二叉排序树中查找数据,key(,按前一页的方法,),,若查找成功则程序中止,若查找失败则转入下面插入过程,(2),(2),以数据,key,作为关键字建立新结点,假定查找过程最后到达某叶子结点,比较,key,与此叶子结点的关键字,若,key,小于后者则将新结点插入为叶子结点的左孩子,若,key,大于后者则新结点插入为叶子结点的右孩子。,例:动态查找,10,,,6,,,19,,,22,,,8,,,2,动态查找,过程也是生成二叉排序树的过程。假定由整数序列,10,,,6,,,19,,,22,,,8,,,2,生成一棵二叉排序树,可以采用逐个元素插入的方法实现。,(1),首先将,10,作为根结点,(2),然后插入,6,时,通过比较知,6x!=key),pre=p;/pre,为结点,p,的父结点指针,if(keyx)p=p-left;,else p=p-right;,/,查找失败,插入新结点,(,见下一页,),(接上一页内容),if(p=NULL)/,建立新结点,p=new BinNode;p-left=NULL;,p-right=NULL;p-x=key;/,新结点不是根,则作为叶子插入,if(pre!=NULL)if(pre-x p-x)pre-left=p;/,插入为左孩子,else pre-right=p;/,插入为右孩子,return p;/,返回找到的结点或插入的新结点的指针,2.6.4,排序基本概念,排序是计算机内经常进行的一种操作,其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。,排序的形式化定义为:假设含,n,个记录的序列为,R,1,R,2,,,R,n,,其相应的关键字序列为,K,1,K,2,,,K,n,。这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系,K,p1,K,p2,K,pn,,按此固有关系将最初的记录序列重新排列为,R,p1,R,p2,,,R,pn,的操作称作排序。,根据是否需要访问外存,排序分为,内部排序,和,外部排序,。,内部排序方法有很多类型:,按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等;,按方法效率可分为简单的排序法、先进的排序法等等。,简单的排序法包括,插入排序、选择排序、冒泡排序,等,它们的时间复杂度为,O(n,2,),。,而先进的排序法包括,快速排序,、,归并排序,等,它们的时间复杂度大约为,O(nlog,2,n),。,2.6.5,常用排序方法,1,、直接插入排序,将记录分为有序和无序两个序列,假定当插入第,k,个记录时,前面的,R,1,,,R,2,,,,,R,k-1,已经排好序,而后面的,R,k,,,R,k+1,,,,,R,n,仍然无序。,这时,用,R,k,的关键字与,R,k-1,的关键字进行比较,若,R,k,小于,R,k-1,则将,R,k-1,向后移动一个单元;,再用,R,k,与,R,k-2,比较,若,R,k,小于,R,k-2,则将,R,k-2,向后移动一个单元,依次比较下去,直到找到插入位置即将,R,k,插入。,初始状态可以认为有序序列为,R,1,。,例:对序列,35,,,22,,,16,,,19,,,22,进行排序,初始状态:,35,221619,22,第,1,趟 :,22,351619,22,第,2,趟 :,16,223519,22,第,3,趟 :,16,19,2235,22,第,4,趟 :,161922,22,35,直接插入排序执行过程,显示在序列,35,,,22,,,16,,,19,,,22,上应用插入排序的过程,为了对序列中相同记录加以区别,使用了下划线。,直接插入排序算法实现:,void InsertSort(int v,int n),int i,j,temp;,for(i=1;i0&tempvj-1),/,从后向前依次比较,找到插入位置,vj=vj-1;j-;,vj=temp;/,插入元素,2,、简单选择排序,简单选择排序的基本思想是:,将记录分为有序和无序两个序列,假定第,k,趟排序时,前面的,R,1,,,R,2,,,R,k-1,已经排好序,而后面的,R,k,,,R,k+1,,,R,n,仍然无序。,选择,R,k,到,R,n,中的,关键字最小的记录与,R,k,交换,,交换后有序序列增加了第,k,个记录。,当第,n-1,趟选择执行完,待排序记录只剩下,1,个,就不用再选了。,在初始状态可以认为有序序列为空。,例:对序列,35,,,22,,,16,,,19,,,22,进行排序,在序列,35,,,22,,,16,,,19,,,22,上应用简单选择排序的过程:,初始状态:,35 22 16 19,22,第,1,趟 :,1622 35 19,22,第,2,趟 :,16 19 35 22,22,第,3,趟 :,16 19 22 35,22,第,4,趟 :,16 19 22,22,35,简单选择排序算法实现:,void SelectSort(int v,int n)int i,j,temp;,for(i=0;in-1;i+),int k=i;/k,存放最小记录位置,for(j=i+1;jn;j+)/,找最小记录位置,if(vjvk)k=j;,if(k!=i)/,交换第,i,和第,k,个位置记录,temp=vi;vi=vk;vk=temp;,3,、冒泡排序,冒泡排序的基本思路是:,第一趟排序对全部记录,R,1,,,R,2,,,,,R,n,自左向右顺次两两比较,若,R,k,大于,R,k+1,则交换,R,k,和,R,k+1,(k=1,2,n-1),,第一趟排序完成后,R,n,成为序列中最大记录,;,第二趟排序对序列前,n-1,个记录采用同样的比较和交换方法,第二趟排序完成后,R,n-1,成为序列中仅比,R,n,小的次大的记录,;,第三趟排序对序列前,n-2,个记录采用同样处理方法,;,如此做下去,最多做,n-1,趟排序,整个序列就排序完成。,例:对序列,35,,,22,,,16,,,19,,,22,进行排序,下,图显示了在序列,35,,,22,,,16,,,19,,,22,上应用冒泡排序的过程。,初始状态:,35 22 16 19,22,第,1,趟 :,22 16 19,22,35,第,2,趟 :,16 19 22,22,35,第,3,趟 :,16 19,22,22,35,第,4,趟 :,16 ,19,22,22,35,冒泡排序算法实现,:,void BubleSort(int v,int n),int temp;,for(int i=1;in;i+),for(int j=0;jvj+1)/,交换两个相邻元素,temp=v j;,vj=vj+1;,vj+1=temp;,/,第,i,大的元素筛选结束,4,、快速排序,快速排序的基本思想是:,任取待排序序列中某个记录,S(,例如取第一个记录,),作为基准,经过一系列比较和交换,将整个序列划分为如下形式:,左侧子序列,S,右侧子序列,并且满足以下两点:,左侧子序列中所有记录的关键字都小于或等于基准对象,S,的关键字;,右侧子序列中所有记录的关键字都大于或等于基准对象,S,的关键字,然后分别对左右两个子序列重复施行上述方法,直到排序完成。,在,22,35,27,16,45,19,22,上应用划分算法(即一趟快速排序),下列快速排序中划分序列的算法对,vlow,与,vhigh,之间的元素进行划分,利用了序列第一个记录作为基准,最终将,low,与,high,区间中的序列划分为左右两个子序列,将基准对象放到适当位置并返回其位置的下标。,int Partition(int low,int high),int pivot=vlow;/,基准对象,pivot,位置为,low,while(lowhigh),while(low=pivot),high-;/,右边界下移,vlow=vhigh;/,小于,pivot,的放到左侧,while(lowhigh&vlowpivot),low+;/,左边界上移,vhigh=vlow;/,大于,pivot,的放到右侧,vlow=pivot;/,此时,low,等于,high,return low;,前面的序列经过划分后,基准元素,22,的位置已经确定不变了。只需将序列,19,,,16,和,27,45,35,22,分别排序即可。进一步的工作是将两个子序列分别划分,可分别取,19,和,27,为基准元素。,22,,,35,,,27,,,16,,,45,,,19,,,22,19,,,16,22,27,,,45,,,35,,,22,16,19 22,22,27,35,,,45,16 19 22 22 27 35,45,快速排序执行过程,Thank You!,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服