ImageVerifierCode 换一换
格式:PPT , 页数:18 ,大小:254KB ,
文档编号:476308      下载积分:2.5 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-476308.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(Q弹啤酒肚)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(Scratch学习课件-10-排序.ppt)为本站会员(Q弹啤酒肚)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

Scratch学习课件-10-排序.ppt

1、10 排序排序 程序设计基础 2 home back first prev next last 本节目标本节目标 排序排序 外排序外排序 内排序内排序 插入排序插入排序 冒泡排序冒泡排序 快速排序快速排序 3 home back first prev next last 排序排序 2-1 排序排序(Sorting) 是计算机程序设计中的一种重是计算机程序设计中的一种重 要操作,它的功能是将一个数据元素(或记要操作,它的功能是将一个数据元素(或记 录)的任意序列,重新排列成一个关键字有录)的任意序列,重新排列成一个关键字有 序的序列。序的序列。 例如,例如, 8 3 2 1 7 4 6 5 1

2、2 3 4 5 6 7 8 4 home back first prev next last 排序排序 2-2 内排序,指的是待排序记录存放在计算机内内排序,指的是待排序记录存放在计算机内 存中进行的排序过程,内排序有多种算法,存中进行的排序过程,内排序有多种算法, 不同的算法,所用的时间和内存空间也不同不同的算法,所用的时间和内存空间也不同 外排序,指的是待排序记录的数量很大,以外排序,指的是待排序记录的数量很大,以 致内存一次不能容纳全部记录,在排序过程致内存一次不能容纳全部记录,在排序过程 中尚需对外存如硬盘进行访问的排序过程中尚需对外存如硬盘进行访问的排序过程 5 home back

3、first prev next last 插入排序插入排序 2-1 插入排序是这样实现的:插入排序是这样实现的: 1、新建一个空列表,用于保存已排序的有序数、新建一个空列表,用于保存已排序的有序数 列(我们称之为“有序列表”)。列(我们称之为“有序列表”)。 2、从原数列中取出一个数,将其插入“有序列、从原数列中取出一个数,将其插入“有序列 表”中,使其仍旧保持有序状态表”中,使其仍旧保持有序状态 3、重复、重复2号步骤,直至原数列为空。号步骤,直至原数列为空。 插入排序的,效率不高,但是容易实现。它借插入排序的,效率不高,但是容易实现。它借 助了助了“逐步扩大成果逐步扩大成果“的思想,使有序

4、列表的长的思想,使有序列表的长 度逐渐增加,直至其长度等于原列表的长度。度逐渐增加,直至其长度等于原列表的长度。 6 home back first prev next last 插入排序插入排序 2-2 编程,通过插入排序,完成编程,通过插入排序,完成 49 38 65 97 76 13 27 的升序排列的升序排列 7 home back first prev next last 冒泡排序冒泡排序 2-1 冒泡排序属于交换排序冒泡排序属于交换排序 1、将所有待排序的数字放入工作列表中。、将所有待排序的数字放入工作列表中。 2、从列表的第一个数字到倒数第二个数字,逐、从列表的第一个数字到倒数第

5、二个数字,逐 个检查:若某一位上的数字大于他的下一位,个检查:若某一位上的数字大于他的下一位, 则将它与它的下一位交换。则将它与它的下一位交换。 3、重复、重复2号步骤,直至再也不能交换。号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,冒泡排序的平均时间复杂度与插入排序相同, 也是非常容易实现的算法也是非常容易实现的算法 8 home back first prev next last 冒泡排序冒泡排序 2-2 9 home back first prev next last 快速排序快速排序 8-1 快速排序(快速排序(Quick sort)是对冒泡排序的一)是对冒泡排序

6、的一 种改进。它的基本思想是:种改进。它的基本思想是: 通过一趟排序将要排序的数据分割成独立的两通过一趟排序将要排序的数据分割成独立的两 部分,其中一部分的所有数据都比另外一部分部分,其中一部分的所有数据都比另外一部分 的所有数据都要小,然后再按此方法对这两部的所有数据都要小,然后再按此方法对这两部 分数据分别进行快速排序,以此达到整个数据分数据分别进行快速排序,以此达到整个数据 变成有序序列变成有序序列 10 home back first prev next last 快速排序快速排序 8-2 设要排序的数组是设要排序的数组是A1AN, 首先任意选取一个数据(通常选用第一个数据)首先任意选

7、取一个数据(通常选用第一个数据) 作为关键数据,作为关键数据, 然后将所有比它小的数都放到它前面,所有比然后将所有比它小的数都放到它前面,所有比 它大的数都放到它后面,它大的数都放到它后面, 这个过程称为一趟快速排序。这个过程称为一趟快速排序。 值得注意的是,快速排序不是一种稳定的排序值得注意的是,快速排序不是一种稳定的排序 算法,也就是说,多个相同的值的相对位置也算法,也就是说,多个相同的值的相对位置也 许会在算法结束时产生变动许会在算法结束时产生变动 11 home back first prev next last 快速排序快速排序 8-3 一趟快速排序的算法是:一趟快速排序的算法是:

8、1)设置两个变量)设置两个变量I、J,排序开始的时候:,排序开始的时候:I=1,J=N; 2)以第一个元素作为关键数据,赋值给)以第一个元素作为关键数据,赋值给key,即,即 key=A1; 3)从)从J开始向前搜索,即由后开始向前搜索,即每次开始向前搜索,即由后开始向前搜索,即每次 J=J-1,找到第一个小于,找到第一个小于key的值的值AJ,并与,并与AI交换;交换; 4)从)从I开始向后搜索,即由前开始向后搜索,即每次开始向后搜索,即由前开始向后搜索,即每次 I=I+1,找到第一个大于,找到第一个大于key的的AI,与,与AJ交换;交换; 5)重复第)重复第3、4、5步,直到步,直到 I

9、=J 12 home back first prev next last 快速排序快速排序 8-4-1 例如:待排序的数组例如:待排序的数组A的值分别是:的值分别是: 49 38 65 97 76 13 27 初始关键数据:初始关键数据:X=49 注意注意X在一趟排序中不变,在一趟排序中不变, 每次都是和每次都是和X进行比较,无论在什么位置,一趟进行比较,无论在什么位置,一趟 排序的目的就是把排序的目的就是把X放在中间,小的放前面,大放在中间,小的放前面,大 的放后面。的放后面。 按照第三步从后面开始找,第一次交换后:按照第三步从后面开始找,第一次交换后:27 38 65 97 76 13 4

10、9 第二次交换后:第二次交换后:27 38 49 97 76 13 65 ( 按照第四按照第四 步从前面开始找步从前面开始找X的值,的值,6549,两者交换两者交换) 13 home back first prev next last 快速排序快速排序 8-4-2 第三次交换后:第三次交换后:27 38 13 97 76 49 65 ( 按照第五按照第五 步将又一次执行算法的第三步从后开始找步将又一次执行算法的第三步从后开始找 ) 第四次交换后:第四次交换后:27 38 13 49 76 97 65 ( 按照第四按照第四 步从前面开始找大于步从前面开始找大于X的值,的值,9749,两者交换两者

11、交换) 此时再执行第三步的时候就发现此时再执行第三步的时候就发现 I=J,从而结束,从而结束 一趟快速排序一趟快速排序 经过一趟快速排序之后的结果是:经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所有大于,即所有大于49的数全部在的数全部在49的后面,所的后面,所 有小于有小于49的数全部在的数全部在49的前面的前面 14 home back first prev next last 快速排序快速排序 8-5 快速排序就是递归调用此过程快速排序就是递归调用此过程在以在以49为中点分为中点分 割这个数据序列,分别对前面一部分和后面一部割这个数据序列,分别对前面一部分和

12、后面一部 分进行类似的快速排序,从而完成全部数据序列分进行类似的快速排序,从而完成全部数据序列 的快速排序,最后把此数据序列变成一个有序的的快速排序,最后把此数据序列变成一个有序的 序列序列 根据这种思想对于上述数组根据这种思想对于上述数组A的快速排序的全过程的快速排序的全过程: 初始状态初始状态 49 38 65 97 76 13 27 进行一次快速排序之后划分为进行一次快速排序之后划分为 27 38 13 49 76 97 65 分别对前后两部分进行快速排序分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序 76 97 65 经第三步和第

13、四步交换后变成 65 76 97 完成排序 15 home back first prev next last 快速排序快速排序 8-6 实践证明,快速排序是所有排序算法中最高效的实践证明,快速排序是所有排序算法中最高效的 一种。它采用了分治的思想:先保证列表的前半一种。它采用了分治的思想:先保证列表的前半 部分都小于后半部分,然后分别对前半部分和后部分都小于后半部分,然后分别对前半部分和后 半部分排序,这样整个列表就有序了。这是一种半部分排序,这样整个列表就有序了。这是一种 先进的思想,也是它高效的原因。因为在排序算先进的思想,也是它高效的原因。因为在排序算 法中,算法的高效与否与列表中数字

14、间的比较次法中,算法的高效与否与列表中数字间的比较次 数有直接的关系,而数有直接的关系,而“保证列表的前半部分都小于保证列表的前半部分都小于 后半部分后半部分“就使得前半部分的任何一个数从此以后就使得前半部分的任何一个数从此以后 都不再跟后半部分的数进行比较了,大大减少了都不再跟后半部分的数进行比较了,大大减少了 数字间不必要的比较。数字间不必要的比较。 16 home back first prev next last 快速排序快速排序 8-7 链表链表 list 用于存储待排序的数据用于存储待排序的数据 因为因为 Scratch 不支持递归,因此建立一个辅不支持递归,因此建立一个辅 助的链

15、表助的链表 sub_seq 用来记录生成的子序列的用来记录生成的子序列的 起始和终止元素的位置起始和终止元素的位置 变量变量 i, j 代表一趟排序的起始和终止元素的代表一趟排序的起始和终止元素的 位置位置 变量变量 key 表示一趟排序的关键数据表示一趟排序的关键数据 变量变量 temp 是临时变量,用于链表是临时变量,用于链表 list 第第i, j 元素的交换元素的交换 17 home back first prev next last 快速排序快速排序 8-8 18 home back first prev next last 总结总结 排序排序 外排序外排序 内排序内排序 插入排序插入排序 冒泡排序冒泡排序 快速排序快速排序

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|