[高等教育]数据结构讲义第10章.ppt

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

第十章 内部排序 §10.1 基本概念 基本概念 基本概念 基本概念 基本概念 §10.2 插入排序 直接插入排序 直接插入排序 直接插入排序 直接插入排序 折半插入排序 希尔插入排序 希尔插入排序 希尔插入排序 希尔插入排序 希尔插入排序 希尔插入排序 §10.3 交换排序 交换排序 交换排序 快速排序 快速排序 快速排序 快速排序 快速排序 §10.4 选择排序 直接选择排序算法分析 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 §10.5 归并排序 归并排序 归并排序 归并排序 §10.5 基数排序 基数排序 基数排序 基数排序 基数排序 基数排序 基数排序 各种内部排序方法的比较 各种内部排序方法的比较 作业 例:设由关键字集合:{ 49,38,65,97,76,13,27,49) 49 38 65 97 76 13 27 49 76 13 27 49 38 65 97 49 49 38 65 97 76 13 27 49 49 97 65 49 76 13 27 38 97 76 65 49 49 13 27 38 38 76 65 49 49 13 27 97 76 49 65 38 49 13 27 97 第1个与第8个交换 前7个调整成堆 27 49 65 38 49 13 76 97 第1个与第7个交换 13 49 27 38 49 65 76 97 13 65 27 49 49 27 38 97 第1个与第6个交换 前6个调整成堆 65 49 27 38 49 13 76 97 第1个与第5个交换 前5个调整成堆 49 65 27 13 49 27 38 97 13 38 27 49 49 65 76 97 49 65 27 38 13 27 49 97 第1个与第4个交换 前4个调整成堆 第1个与第3个交换 前3个调整成堆 49 65 27 49 38 27 13 97 49 65 27 27 13 38 49 97 13 27 38 49 49 65 76 97 第1个与第2个交换 前2个调整成堆 49 65 27 27 13 38 49 97 排序完成:13,27,38,49,49,65,76,97 这里要解决两个问题: 1、如何由一个无序序列建成一个堆; 2、输出一个根结点后,如何将剩余元素调整成一个堆。 大根堆:把一棵完全二叉树调整成堆的过程实际上是一个筛选过程,小的关键字筛到筛底,大的关键字浮到筛上面。调整时,取左右孩子的大者进行调整。 1、将一个无序序列建成一个堆的方法: 筛选过程的算法为: 从最后一个非叶结点开始,逐步向根结点,反复进行“筛选”过程,使其结点元素的关键字大于左右孩子结点的关键字。 将指定结点为根的子树调整成堆的算法: void Heapadjust(Sqlist H,int s,int m) // 除结点H.r[s]外,H.r[s+1..m]为堆,将s 结点调整到适当位置 { temp=H.r[s]; for (j=2*s;j=m;j*=2) { if ( jm LT(H.r[j].key,H.r[j+1]) ++j; //直接子树根结点中较大者为 j if ( LT(temp.key,H.r[j].key) { H.r[s]=H.r[j];s=j;} //若 s 结点 小于 j 结点,则交换. else break; } H.r[s]=temp; } 堆排序的算法: void Heapsort(Sqlist H) { // 建立初始堆 for (i=H.length/2;i0;--i) Heapadjust(H,i,H.length); //将堆顶记录与未排序子序列末记录交换,并调整成堆 for (i=H.length;i1;--i) { H.r[0]=H.r[1]; H.r[1]=H.r[i]; H.r[i]=H.r[0]; Heapadjust(H,1,i-1) //剩余 1..i-1 个元素调整为堆 } } 算法分析: 对深度为k的堆,筛选算法中进行关键字的比较次数至多为2(k-1)。建堆时,n个元素所需的比较次数不超过4n。堆排序时,2n㏒2n. 堆排序在最坏的情况下,时间复杂度为O(n㏒2n) 仅需一个记录大小的辅助存储空间。 堆排序方法当记录较少时,不值得提倡。当n很大时,效率高。 堆排序是非稳定的。 “归并”的含义:将两个或两个以上有序表组合成一个新的有序表。 归并排序

文档评论(0)

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

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

1亿VIP精品文档

相关文档