[理学]数据结构第十章 排序.ppt

  1. 1、本文档共110页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[理学]数据结构第十章 排序

堆排序的时间复杂度分析: 1. 对深度为 k 的堆,“筛选”所需进行的关键字 比较的次数至多为2(k-1); 3. 调整“堆顶” n-1 次,总共进行的关键 字比较的次数不超过 2 (?log2(n-1)?+ ?log2(n-2)?+ …+log22) 2n(?log2n?) 因此,堆排序的时间复杂度为O(nlogn)。 2. 对 n 个关键字,建成深度为h(=?log2n?+1)的堆, 所需进行的关键字比较的次数至多 4n; 10.5 归 并 排 序   归并排序的过程基于下列基本思想进行: 将两个或两个以上的有序子序列 “归并” 为一个有序序列。   在内部排序中,通常采用的是2-路归并排序。即:将两个位置相邻的记录有序子序列 归并为一个记录的有序序列。 有 序 序 列 R[l..n] 有序子序列 R[l..m] 有序子序列 R[m+1..n] 这个操作对顺序表而言,是轻而易举的。 void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) { // 将有序的记录序列 SR[i..m] 和 SR[m+1..n] // 归并为有序的记录序列 TR[i..n] } // Merge for (j=m+1, k=i; i=m j=n; ++k) { // 将SR中记录由小到大地并入TR if (SR[i].key=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } … … if (i=m) TR[k..n] = SR[i..m]; // 将剩余的 SR[i..m] 复制到 TR if (j=n) TR[k..n] = SR[j..n]; // 将剩余的 SR[j..n] 复制到 TR 归并排序的算法  如果记录无序序列 R[s..t] 的两部分 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t] 分别按关键字有序, 则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此,应该先分别对这两部分进行 2-路归并排序。 例如: 52, 23, 80, 36, 68, 14 (s=1, t=6) [ 52, 23, 80] [36, 68, 14] [ 52, 23][80] [ 52] [ 23, 52] [ 23, 52, 80] [36, 68][14] [36][68] [36, 68] [14, 36, 68] [ 14, 23, 36, 52, 68, 80 ] [23] void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) { // 将SR[s..t] 归并排序为 TR1[s..t] if (s= =t) TR1[s]=SR[s]; else { } } // Msort … … m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m] Msort (SR, TR2, m+1, t); //递归地SR[m+1..t]归并为有序的TR2[m+1..t] Merge (TR2, TR1, s, m, t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] void MergeSort (SqList L) { // 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1, L.length); } // MergeSort  容易看出,对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)。即: 每一趟归并的时间复杂度为 O(n), 总共需进行 ?log2n? 趟。 10.6 基 数 排 序  基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 多关键字

您可能关注的文档

文档评论(0)

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

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

1亿VIP精品文档

相关文档