chapter9 内部排序.ppt

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

数 据 结 构 9.4 选择类排序 第 9 章 内部排序 从记录的无序子序列中“选择”关键字最小或 最大的记录,并将它加入到有序子序列中, 以此方法增加记录的有序子序列的长度。 ①简单选择排序 ③堆排序 ②树型选择排序 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ①简单选择排序 98 35 14 55 77 35 62 48 i 第 1 趟 k j j k j j j k j j 14 48 2 i k j 35 62 3 35 62 4 48 77 5 55 6 62 77 7 77 8 98 void SelectSort(RecordType r[ ],int n) { n=length; for(i=1;i=n-1;i++) { k=i; for(j=i+1;j=n; ++j) if(r[j].keyr[k].key) k=j; if(k!=i) { x=r[i];r[i]=r[k];r[k]=x;} } } 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ①简单选择排序 时间性能分析 对 n 个记录进行简单选择排序,所需进 行的关键字间的比较次数 总计为: 移动记录的次数,最小值为 0, 最大值为3(n-1) 。 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ②树型选择排序 是一种按锦标赛的思想进行排序的方法。 49 38 27 65 97 76 49 13 38 65 13 27 38 13 13 ∞ 76 13 27 27 27 ∞ 49 49 38 38 ∞ 49 49 49 49 ∞ ∞ 65 49 49 ∞ ∞ 76 65 65 ∞ 97 97 76 76 ∞ ∞ ∞ 97 97 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 对树型排序的进一步改进。 堆是满足下列性质的数列{r1, r2, …,rn}: 或 堆的定义: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如: 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小顶堆) (大顶堆) ? í ì £ £ + 1 2 2 i i i i r r r r ? í ì 3 3 + 1 2 2 i i i i r r r r ri r2i r2i+1 若将该数列视作完全二叉树,则 r2i 是 ri 的左孩子;r2i+1 是 ri 的右孩子。 例如: 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 12 36 27 65 40 34 98 81 73 55 49 14 14 是小顶堆 不 堆排序即是利用堆的特性对记录序列进行排序。 例如: 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交换 98 和 12 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 经过筛选 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 1、如何由一个无序序列“建初堆”? 堆排序的两个问题: 2、输出堆顶后,如何“筛选”? 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 所谓“筛选”指的是,对一棵左/右子树均为堆的完全 二叉树,“调整”根结点使整个二叉树也成为一个堆。 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 48 98 35 77 55 14 35 62 48 98 77 62 48 数 据 结 构 9.4 选择类排序 第 9 章 内部排序 ③堆排序 例如: { 48, 62, 35, 77, 55, 14, 35, 98} 48 62 35 77 55 14 35 98 显然不是一个堆 调整 如何建初堆? * 数 据 结 构 9.1 排序的基本概念 9.2 插入类排序 9.4 选择类排序 第 9 章 内部排序 9.3 交换类排序 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的总和比较 数 据 结 构 9.1排序的基本概念 第 9 章 内部排序 排序是计算机内经常进行的一种操作,其目的是将

文档评论(0)

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

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

1亿VIP精品文档

相关文档