版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数 据 结 构 DATA STRUCTURE, DS 授课教师:郭 艳授课班级: 191131-2中国地质大学计算机学院2014年秋上堂课要点回顾图的应用三:拓扑排序问题提出AOV网和拓扑排序的定义算法 借助栈或队列图采用邻接矩阵结构O(n2),采用邻接表O(n+e)图的应用四:关键路径两个问题的提出AOE网和关键路径的定义事件vj的最早发生时间Ve(j)计算事件vj的最迟发生时间Vl(j)计算活动ai的最早开始时间e(i)计算活动ai的最迟开始时间l(i)计算关键活动第 十七 次 课阅读: 朱战立,第228-240页作业16数据结构课程内容9.1 引言三种O(n2)的简单排序算法9.2.1
2、直接插入排序 9.3.1 直接选择排序9.4.1 冒泡排序9.2.2 希尔排序O(n3/2)9.3.2 堆排序O(nlogn) 9.4.2 快速排序O(nlogn)9.5 归并排序O(nlogn)9.6 基数排序O(nlogn)9.7 排序算法性能比较Chapter 9 内部排序9.1 引言排序(Sorting)记录( record)是进行排序的基本单位。文件是记录的集合。关键字( key )是唯一确定记录的一个或多个域。设有一含n个记录的文件R=r1, r2, , rn, 其对应的关键字为 K=k1, k2, , kn,将此n个记录按其关键字大小递增(或递减)的次序排列起来,成为一个有序的文
3、件R=r1, r2, ,rn,相应关键字为K =k1, k2, ,kn, 这样一种运算称为排序。如果k1k2kn称为不减序。如果k1k2kn 称为不增序。正序序列:待排序序列正好符合排序要求。,逆序序列:把待排序序列逆转过来,正好符合排序要求排序的类型内部排序(internal sorting):整个排序过程中所有的记录都可以直接存放在内存中 外部排序(external sorting):内存无法容纳所有记录,排序过程中还需要访问外存 排序算法的衡量标准稳定性(stability)“稳定的”(stable)排序算法 :如果存在多个具有相同关键字的记录,经过排序后这些记录的相对次序仍然保持不变的
4、排序算法。例: 15,18,18,10,70,13,44 10,13,15,18,18,44,70 稳定的 10,13,15,18,18,44,70 不稳定的 稳定的排序方法有:直接插入、冒泡、归并、基数不稳定的排序方法有:希尔、选择(直接选择、堆)、快速排序复杂度(complexity)时间代价:记录的比较次数和记录的交换次数 空间代价 如不作特别说明,记录数据类型均为如下定义的DataType类型,且为了方便讨论,设记录的关键字类型为整型。采用一维数组描述待排序文件。 typedef int KeyType; typedef struct KeyType key; /*关键字域*/ /*其
5、它数据域*/ DataType;DataType a100;/待排序文件void swap (DataType a , int i, int j)/交换ai和ajDataType tmp = ai; ai = aj; aj = tmp;9.2 插入排序9.2.1 直接插入排序基本思想 依次将每个记录插入到一个已排好序的子文件的合适位置中,插入后的文件仍然有序。 例: 8, 3, 2, 5, 9, 4, 6 假设前面几个记录已按关键字递增的次序有序: 2, 3, 5, 8, 9 4 , 6 现将4插入以得到一个新的有序文件, 49,48,45 应插在第3与5之间, 得到新的文件:2, 3, 4,
6、 5, 8, 9 6 i=1:(3) 3 8 2 5 9 4 6i=2:(2) 2 3 8 5 9 4 6i=3:(5) 2 3 5 8 9 4 6i=4:(9) 2 3 5 8 9 4 6i=5:(4) 2 3 4 5 8 9 6i=6:(6) 2 3 4 5 6 8 9 完成!i例:初始关键字: 8 3 2 5 9 4 6【直接插入排序算法】 void InsertSort(DataType a ,int n) /*用直接插入排序法对a0an-1排序*/ int i,j; DataType temp; /临时变量 for(i=0;i-1&temp.keyn-1,每次比较aj和asmall:
7、 若aj.keyasmall.key,则small=j;循环退出后,如果small i, 则交换ai和asmall。例:465513429417570ijsmall=0jjjjjjsmall=2small=6smalli,交换5 55 13 42 94 1746 705 13 55 42 94 1746 705 13 17 42 94 5546 705 13 17 42 94 5546 705 13 17 42 46 5594 705 13 17 42 46 5594 705 13 17 42 46 5570 94 完成!【直接选择排序算法】 void SelectSort(DataType
8、a ,int n) int i,j,small; for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(aj.keyasmall.key) small=j; if(small!=i) swap(a,i,small); 算法分析 不稳定的排序算法 辅助空间:O(1) 时间: (1) 比较次数 (2) 记录移动次数 正序Mmin=0, 逆序Mmax=3(n-1) 总的时间复杂度仍为O(n2) 9.4 “交换”排序9.4.1 冒泡排序 基本思想不停地比较相邻的两个记录,如果不满足排序要求,就交换相邻记录,直到第n-1个记录与第n个记录进行比较、交换后为止,完成一
9、趟冒泡排序,使得关键字最大的记录被安置在最后一个位置上。 然后,对前n-1个记录进行同样的操作,直到进行了n-1趟。改进避免不必要的比较。例如检查每次冒泡过程中是否发生过交换,如果没有,则表明整个数组已经排好序了,排序结束。例: 初值:44 55 22 33 99 11 66 77第一趟排序之后:44 22 33 55 11 66 77 99第二趟排序之后:22 33 44 11 55 66 77 99第三趟排序之后:22 33 11 44 55 66 77 99第四趟排序之后:22 11 33 44 55 66 77 99第五趟排序之后:11 22 33 44 55 66 77 99第六趟排
10、序之后:11 22 33 44 55 66 77 99 完成!【改进的冒泡排序算法】 void BubbleSort(DataType a ,int n) /*用冒泡排序法对a0an-1排序*/ int i, j, flag=1; DataType temp; for(i=1;in&flag=1;i+) /共n-1趟 flag=0; for(j=0;jaj+1.key) flag=1; swap(a,j,j+1); 算法分析 稳定的排序算法 辅助空间:O(1) 时间: (1) 比较次数最好(正序)要执行1趟, 最小比较次数为n-1次。最坏(逆序)要执行n-1趟,最大比较次数为: (2) 移动次
11、数 最小:不移动,为0。 最大:每次比较都移动3次,比较次数为最大移动量为 总的时间复杂度为O(n2)。三种简单排序算法的比较直接插入排序直接选择排序冒泡排序关键字比较次数记录移动次数关键字比较次数记录移动次数关键字比较次数记录移动次数最好(正序)O(n)O(n)O(n2)0O(n)0最坏(逆序)O(n2)O(n2)O(n2)O(n)O(n2)O(n2)平均值O(n2)O(n2)O(n2)O(n)O(n2)O(n2)平均时间复杂度O(n2)O(n2)O(n2)空间复杂度O(1)O(1)O(1)三种简单排序算法的特点 以上几种排序方法(直接插入排序、直接选择排序、冒泡排序)的共同特点是:以显示或
12、者非显示的方法对相邻的元素进行比较和交换。 理论上可以证明:通过交换相邻元素进行排序的任何算法的平均时间需要O(n2)。Data Structures and Algorithm Analysis in C. (Mark Allen Weiss.) 迫切需要更好的算法,以Donald Shell名字命名的希尔排序成为冲破二次时间屏障的第一批算法。 9.2.2 Shell排序直接插入排序的两个性质在最好情况下(即序列本身已是有序)时间代价为O(n)对于短序列,直接插入排序比较有效Shell排序有效地利用了直接插入排序的这两个性质9.2.2 Shell排序算法思想:先将序列转化为若干小序列,在这些
13、小序列内进行直接插入排序;通过逐渐扩大小序列的规模,从而逐渐减少小序列个数,使得待排序序列逐渐处于更有序的状态;最后对整个序列进行扫尾直接插入排序,从而完成排序。 9.2.2 Shell排序(“缩小增量排序法”)技巧: 子序列的构成不是简单地“逐段分割”,而是将相隔某个增量dk的记录组成一个子序列。让增量dk逐趟缩短,直到dk1为止。 “增量”的选择: (1) 增量每次除以2递减:d1=(2)2k-1,2k -1 -1,7,3,1 (3) 都取奇数: 如 17,15,13,11,9,7,5,3,1 (4) di之间互素:如 17,13,11,7,5, 3, 2, 1, di+1=例:记录数n=
14、8,进行希尔排序初始: 465513429417570d2=2461754294551370第一趟排序结果:1755513d1=4第二趟排序结果:517134246559470d3=1513174246557094第三趟排序结果:void ShellInsertSort(DateType a,int n, int k, int span)/ span表示增量,将第k组增量为span的序列直接插入排序。int i, j; DataType tmp;/临时变量for ( i = k; i = -1 & tmp.key=aj.key) a j+span = a j;j=j span ; a j+sp
15、an = tmp;void ShellSort(DateType a ,int n, int d , int numOfD )int m,span;/注意:增量每次递减for (m=0; mnumOfD; m+)span=dm;for(k=0;k0;span=/2,i+) di=span;return i-1;main()int a8=46,55,13,42,94,17,5,70,n=8,d8, numOfD, i; numOfD =D(d,n); ShellSort(a, n, d , numOfD );for(i=0;in;i+) coutai“ “;希尔排序算法分析不稳定的排序算法空间代价:O(1)时间代价:开始时dk 的值较大,子序列中的对象
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 南京邮电大学《程序设计语言B》2023-2024学年第一学期期末试卷
- 江西省上饶市2024年中考数学二模试题含答案
- 九江职业大学《商业推广设计》2023-2024学年第一学期期末试卷
- 江苏航空职业技术学院《Premere视频编辑应用与实践》2023-2024学年第一学期期末试卷
- 黄淮学院《舞蹈编创(一)》2023-2024学年第一学期期末试卷
- 【物理】第十二章 简单机械 章末练习-2024-2025学年八年级下册人教版物理
- 重庆商务职业学院《工程制图与CAD》2023-2024学年第一学期期末试卷
- 重庆第二师范学院《药物流行病学》2023-2024学年第一学期期末试卷
- 浙江长征职业技术学院《普通生物学(一)》2023-2024学年第一学期期末试卷
- 浙江横店影视职业学院《建筑工程计里与计价》2023-2024学年第一学期期末试卷
- 钢材压延加工生产技术
- 农村教师政协提案范文
- JT-T 1495-2024 公路水运危险性较大工程专项施工方案编制审查规程
- 2024年高级养老护理员职业鉴定考试题库大全-下(多选、判断题)
- 数学学科的重要性与应用
- 【阅读提升】部编版语文五年级下册第二单元阅读要素解析 类文阅读课外阅读过关(含答案)
- 病理科医院感染控制
- 购销合同电子版完整版
- 福建省福州市延安中学2023-2024学年八年级上学期期末物理模拟试卷+
- 2024年度医院肝胆外科实习生带教计划课件
- 微机原理与接口技术考试试题及答案(综合-必看)
评论
0/150
提交评论