归并排序-ppt课件_第1页
归并排序-ppt课件_第2页
归并排序-ppt课件_第3页
归并排序-ppt课件_第4页
归并排序-ppt课件_第5页
已阅读5页，还剩31页未读， 继续免费阅读

下载本文档

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

文档简介

1、10.5合并和排序，基本思想是将两个或多个有序子序列“合并”成一个有序序列。在内部排序中，通常采用双向合并排序。也就是说，两个相邻的有序子序列被合并成一个有序序列。10.5合并和排序，如何以两种方式合并？比较两个有序表的元素，并将较小的一个复制到目标表中。(5，24，35，74，222)，(19，23，30)，()，5，24，35，74，222，(，)，19，23，30，(，)，(，)Int r1，int s，int m，int t) /*用序列rs合并两条路径.m和rm 1.t进入R1 * * */I=s；j=m1；k=s；当(i=m /下一个子序列的剩余部分，10.5合并和排序时，原理假设

2、初始序列包含n个记录，那么它可以被视为n个有序子序列，并且每个子序列的长度为1。然后每两个合并得到长度为2或1的n/2有序子序列；成对合并，重复直到得到长度为n的有序序列。开头：49 38 65 97 76 13 27，void m sort (elemsr，elemstr1，int s，int t)/* * * * sort SRs.t进入TR1s.t * * * */if(s=t)TR1s=SRs；否则m=(s t)/2；/划分SRs.t至m端口(SR、TR1、s、m)；/递归排序子序列SRs.m . m . ort(SR，TR2，m . 1，t)；/递归排序子序列SRm 1.合并(TR2

3、，TR1，s，m，t)；/合并，10.5合并和排序，10.5合并和排序，性能分析一遍合并操作是将r1rn中长度为h的相邻有序序列成对合并，需要O(n)个时间。整个合并排序需要log2n次，因此总时间开销为O(nlog2n)。10.5合并和排序，当执行性能分析算法时，它需要占用与原始记录序列相同的存储空间，因此空间复杂度为O(n)。10.5合并和排序，总结最佳、最差和平均时间复杂度为0(nlogn)；空间复杂度高，为0(n)；它是高效算法中唯一“稳定”的排序方法；较少用于内部排序，较多用于外部排序。10.6基数排序，基本思想基数排序是通过“分配”和“收集”对单个关键字进行排序的方法。10.6基数排序，多键排序，以扑克排序为例。每张扑克牌有两个“关键码”:花色和面值。顺序关系如下：花色：面值：2345678910jQKA，10.6基数，“花色”先分为4堆；然后，按照“面值”排列每一堆；最后，我得到了一个好收成。以扑克牌“排序”为例，10.6基数排序，“面值”首先分为13堆；每一堆都是按照“花色”排列的；以扑克牌“排序”为例，10.6基数排序，多键排序，假设序列中有n条记录R1

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

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

最新文档

评论

0/150

提交评论