数据结构--第九章内部排序解读.ppt

  1. 1、本文档共51页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
归并排序的示例为: (19) (13) (05) (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) (01,05,13,16,19,26,27,31) 2-路归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列。 合并算法描述如下: void Merge ( RecordType r1[], int low, int mid, int high, RecordType r[]) /*已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列,将它们合并成一个有序序列,存放在r[low..high] */ {i=low;j=mid+1; k=low; while ( (i=mid)(j=high) ) {if ( r1[i].key=r1[j].key ) {r[k]=r1[i] ; ++i;} else {r[k]=r1[j] ; ++j;} ++k ; } if ( i=mid ) r[k..high] =r1[i..mid]; if ( j=high ) r[k..high] =r1[j..high]; } /* Merge */ 2-路归并排序可以采用递归方法实现,具体描述如下: void MergeSort (RecordType r1[], int low, int high, RecordType r[]) /* r1[low..high]经过排序后放在r[low..high]中,r2[low..high]为辅助空间 */ { RecordType *r2; r2=(RecordType*)malloc(sizeof(RecordType)*(hight-low+1)); if ( low==high ) r[low]=r1[low]; else{ mid=(low+high)/2; MergeSort(r1,low, mid, r2); MergeSort(r1,mid+1,high, r2); Merge (r2,low,mid,high, r); } free(r2); } /* MergeSort */ 归并排序的算法分析: 归并排序中一趟归并中要多次用到2-路归并算法,一趟归并排序的操作是调用 ?n/2h ?次算法merge 将r1[1…n]中前后相邻且长度为h的有序段进行两两归并,得到前后相邻、长度为2h的有序段,并存放在r[1…n]中,其 时间复杂度为O(n)。整个归并排序需进行m(m=log2n)趟2-路归并,所以归并排序总的时间复杂度为O(nlog2n)。在实现归并排序时,需要和待排记录等数量的辅助空间,空间复杂度为O(n)。 归并排序的最大特点是,它是一种稳定的排序方法。 类似2-路归并排序,可设计多路归并排序法,归并的思想主要用于外部排序。 外部排序可分两步,①待排序记录分批读入内存,用某种方法在内存排序,组成有序的子文件,再按某种策略存入外存。②子文件多路归并,成为较长有序子文件,再记入外存,如此反复,直到整个待排序文件有序。 外部排序可使用外存、磁带、磁盘,最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略,归并路数取决于所能提供排序的外部设备数。 * * 第九章 内部排序 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序法 9.4 选择类排序法 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的综合比较 9.1 排序的基本概念 排序:有n个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2, …,Kn },相应的下标序列为1,2,…, n。通过排序,要求找出当前下标序列1,2,…, n的一种排列p1,p2, …,pn,使得相应关键字满足如下的非递减(或非递增)关系,即:Kp1≤ Kp2≤…≤ Kpn ,这样就得到一个按关键字有序的记录序列:{Rp1, Rp2, …, Rpn}。 内部排序:整个排序过程完全在内存中进行,称为内部排序。 外部排序:由于待排序记录数据量太大,内存无

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档