您所在位置：网站首页 > 高等教育 > 大学课件数据结构(第二版) 教学课件 ppt 作者郑泳方风波第八章排序

数据结构(第二版) 教学课件 ppt 作者郑泳方风波第八章排序

16页

卖家[上传人]：E****

文档编号：89184562

上传时间：2019-05-20

文档格式：PPT

文档大小：1.11MB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 16 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第八章排序,知识教学目标,排序的有关概念插入排序、交换排序、选择排序、归并排序各种排序方法的比较,能力培养目标,直接插入排序、希尔排序冒泡排序、快速排序直接选择排序、堆排序归并排序各种排序算法的比较及时间复杂度的分析,8.1 基本概念,排序（Sorting）又称为分类，就是将一组数据元素的无序序列按一定的规律进行排列，使之成为有序序列。其中，这些数据元素可以是数值型，也可以为字符型。若为数值型，则按数值的大小排序，若为字符型，则按其ASCII码值的顺序排序。线性表由排序关键字和数据域组成，其定义为： typedef int KeyType; typedef struct KeyType key; OtherType other_data; RecordType;,8.2 插入排序,插入排序（Insertion Sort）的基本思想是，每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。常见的插入排序有：直接插入排序和希尔排序。,8.2.1 直接插入排序,【算法8.1】直接插入排序。 void InsertSort

2、ing(RecordType R,int n) int i,j; for(i=2;in;i+) R0=Ri; j=i-1; while(R0.keyRj.key) Rj+1=Rj; j-; Rj+1=R0; ,8.2.2 希尔排序,【算法8.2】希尔排序。 void ShellInsertSorting(RecordType R,int n) int i,j,d; for(d=n/2;d=1;d/=2) for(i=d;i=0;j-=d) if(R0Rj) Rj+d=Rj; else break; Rj+d=R0; ,8.3 交换排序,【算法8.3】冒泡排序。 void BubbleSorting(RecordType R,int n) int i,j,flag; for(i=1;i=i;j-) if(Rj+1.keyRj.key) R0=Rj+1; Rj+1=Rj; Rj=R0; /反序，交换两个数 Flag=0; if(flag) break; /本趟没有逆序 ,【算法8.4】快速排序。 void QuickSorting(RecordType R,int s,int t)

3、int i=s,j=t; RecordType temp; while(i=temp.key) ,8.4 选择排序,【算法8.5】直接选择排序。 void SelectSorting(RecordType R,int n) int i,j,m; RecordType temp; for(i=0;i=n-2;i+) m=i; for(j=i+1;j=n-1;j+) if(Rj.keyRm.key) m=j; /找本趟最小关键字的记录序号 if(m!=i) temp=Ri; Ri=Rm; Rm=temp; ,8.4.2 堆排序,通过分析选择排序可得知，选择排序移动效率很高，但是每趟排序中，需要比较大量的元素，每次为了在k个元素中选择出最小的元素，需要进行k1次比较。若能充分利用上一趟排序中比较的结果信息，可能会减少比较的次数，这就是堆排序的基本思路。,8.5 归并排序,【算法8.6】二路归并排序。 void Merge(RecordType R,RecordType A,int s,int m,int t) int i=s,j=m+1,k=s; while(i=m) ,8.6 排序方法

4、的比较和选择,8.6.1 排序方法的比较,8.6.2 排序方法的选择,1从时间复杂度选择对记录个数较多的排序，可以选择快速排序、归并排序，记录个数较少时，可以选简单的排序方法。 2从空间复杂度选择尽量选空间复杂度为O(1)的排序方法，其次选空间复杂度为O (log2n)的快速排序方法，最后才选空间复杂度为O(n)的二路归并排序方法。,3一般选择规则 1) 当待排序记录的个数n较大，关键字分布是随机的，而对稳定性不做要求时，采用快速排序为好。 2) 当待排序记录的个数n较大，内存空间允许，且要求排序稳定时，采用二路归并排序为好。 3) 当待排序记录的个数n较大，记录的关键字可能会出现正序或反序的情况，且对稳定性不做要求时，采用二路归并排序为好。 4) 当待排序记录的个数n较小，记录基本按关键字有序或分布较随机，且要求排序稳定时，采用直接插入排序为好。 5) 当待排序记录的个数n较小，对稳定性不做要求时，采用直接选择排序为好，若记录的关键字不接近反序，也可以采用直接插入排序。 6) 若待排序列初始状态基本有序，则选用直接插入排序、冒泡排序或快速排序为宜。若待排序列初始状态基本无序，则选用快速排序为宜。,8.7本章小结,直接插入排序、直接选择排序和冒泡排序是三种简单型的排序方法，其时间复杂度均为O(n2)，空间复杂度均为O(1)，但直接插入排序又优于直接选择排序，而直接选择排序又优于冒泡排序。快速排序和归并排序是改进型的排序方法，时间复杂度均为O (nlog2n)，空间复杂度分别为O (log2n)和O(n)。通常快速排序优于归并排序。希尔排序也是一种改进型的排序方法，其时间复杂度大约为O(n1.3)左右，空间复杂度为O(1)。直接插入排序、冒泡排序、归并排序是稳定的排序方法，而希尔排序、直接选择排序、快速排序是不稳定的排序方法。快速排序的最好情况是每次能划分出左右两个均匀的子序列，最坏情况是划分出来的两个子序列有一个为空。归并排序是将两个有序子序列合并为一个有序序列，合并后，序列的个数不断减少，序列的长度不断增加，直至剩下一个有序序列，才得到排序结果，但排序中必须占用等量的辅助空间。,

《数据结构(第二版) 教学课件 ppt 作者郑泳方风波第八章排序》由会员E****分享，可在线阅读，更多相关《数据结构(第二版) 教学课件 ppt 作者郑泳方风波第八章排序》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源

逍遥游复习知识点整理

近现代法德关系史高三展示课3稿

当代大学生人生信仰及追求的调查研究

长相思纳兰性德-ppt课件

课件：危机意识一

英语ppt演讲关于阿甘正传

发达国家基础教育改革的动向与趋势修改版

中国民间美术课件.ppt

生物质发电技术与系统课程ppt 第1章生物质发电技术现状及发展趋势 2学时 -----2016

现代信号处理思考题含答案

执业药师继续教育抑郁症的药物治疗 100分

小学生的成长档案模板不用修改万能型

增订六版现代汉语上册第二章文字思考与练习答案

国家财政ppt课件

加拿大英语介绍

六年级统计图的选择课件

中学生成长档案ppt

中国现代文学史期末复习整理

lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究

风雨贾平凹阅读答案

点击查看更多

新上传的PPT文档

有关爱心募捐倡议书戛洒镇中心小学2013年秋季学期科学实验教学计划企业计时人员薪酬制度实施细则 2019清洁取暖双替代（气代煤）取暖设备采购项目初中数学教学案例分析工程管理专业人才培养方案 2022学年度助推站年终工作总结功能模块线束项目申请报告写作参考模板个人信息管理系统课程设计报告鼓励退伍学生坚定信心向榜样看齐道路景观绿化工程施工设计方案集合竞价的秘密 2023年体育教案田径运动理论力学试卷B 县长履行党风廉政建设主体责任报告

数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第八章 排序

数据结构(第二版) 教学课件 ppt 作者郑泳方风波第八章排序