完美信息教室讲义排序算法伸_第1页
完美信息教室讲义排序算法伸_第2页
完美信息教室讲义排序算法伸_第3页
完美信息教室讲义排序算法伸_第4页
完美信息教室讲义排序算法伸_第5页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

选择第i至第n项中最小的元素，并且与第i项交换位置。void{for(int{intpos=j;//记录最小元素的位置for(intj=i+1;j<=n;j++)}} void{for(intfor(intj=i;j>1&&a[j]<a[j-1];j--}何也不会使得a[0]和a[1]进行交换（那a[0]自然就应该取-inf了。void{for(int}int{intfor(int{intfor(intj=1;j+i<=n;j++)if(!cnt)break已经排序完毕，可以提前退出}}归并排序是使用折半治法的一个典例子。在每轮迭代过程中，算将当前序一分为二，分别递归地完成排序（当然，如果序列中只含有一个元素，则直接返回即可；（故总的复杂度为O(nlogn)。voidmerge_sort(intl,int{intmid=(l+r)>>1;////一for(intp=l,q=mid+1,i=l;p<=mid&&if(q>r||p<=mid&&b[p]<b[q])a[i++]=b[p++];elsea[i++]=b[q++];}O(nlogn)partition点两侧递归进行partition操作。O(logn)（根据具体实现的不同略有差别O(nlogn)。2ii2i+1。它的插入和删除使用到了“上浮”和“下沉”的struct{intintnewnode(int{ returncnt;}intmerge(intx,int{if(!y)returnr[x]=merge(r[x],y);//合并右子树与新堆（递归）if(d[l[x]]<d[r[x]])//保证左子树深度较大，右子树启发式合returnx;}voidpush(intx,int{}voidpop(int{}最短路，同时可并堆还可以优化树形DP上状态传递的效率。以总的时间复杂度为O(n)。Sy也是一样的O(logn)的时间开销。散化后对应的Hash值。

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论