![数据排序 课件【高效备课精研+知识精讲提升】浙教版(2019)高中信息技术选修1_第1页](http://file4.renrendoc.com/view/2d9876d786debf6834ce1ba2ce5458d5/2d9876d786debf6834ce1ba2ce5458d51.gif)
![数据排序 课件【高效备课精研+知识精讲提升】浙教版(2019)高中信息技术选修1_第2页](http://file4.renrendoc.com/view/2d9876d786debf6834ce1ba2ce5458d5/2d9876d786debf6834ce1ba2ce5458d52.gif)
![数据排序 课件【高效备课精研+知识精讲提升】浙教版(2019)高中信息技术选修1_第3页](http://file4.renrendoc.com/view/2d9876d786debf6834ce1ba2ce5458d5/2d9876d786debf6834ce1ba2ce5458d53.gif)
![数据排序 课件【高效备课精研+知识精讲提升】浙教版(2019)高中信息技术选修1_第4页](http://file4.renrendoc.com/view/2d9876d786debf6834ce1ba2ce5458d5/2d9876d786debf6834ce1ba2ce5458d54.gif)
![数据排序 课件【高效备课精研+知识精讲提升】浙教版(2019)高中信息技术选修1_第5页](http://file4.renrendoc.com/view/2d9876d786debf6834ce1ba2ce5458d5/2d9876d786debf6834ce1ba2ce5458d55.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
知识回顾迭代算法:利用计算机运算速度快、适合做重复性操作的特点,让计算机重复执行一组指令,这组指令每执行一次时,都会将变量从原值递推出一个新值,即由旧值不断推出新值的过程。f1=1
f2=1
i=3
whilei<=12:
f=f1+f2
f1=f2
f2=f
i+=1
print(f"第{i-1}月共有{f}对兔子“)迭代算法处理问题:确定迭代变量:由旧值递推出新值的变量;建立迭代关系式:从变量的前值推出下个值的公式;控制迭代条件:经过若干次重复执行后能够结束。知识回顾递归算法:在计算机科学中,指一种通过重复将问题分解为同类的子问题而解决问题的方法,它通过函数自己调用自己来实现,即一个函数在其定义中直接或间接调用自身的一种方法。核心思想:把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,规模较小的又转化为规模更小的问题求解,当问题小到一定程度时,可以直接得出它的解,从而回归求解问题原来的解。即“大事化小,小事化了”的思想。实现条件:1、每一步解决问题的方法有一致的规律:递归公式
2、可以达到某个边界条件:递归出口CHZX5.3数据排序浙江省高中信息技术选择性必修一《数据与数据结构》昌化中学应彤鑫冒泡排序算法思想程序实现01冒泡排序Maopaopaixu算法思想冒泡排序Maopaopaixu算法思想是一系列数据中对相邻两个数依次进行比较和调整,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。三要素趟数:n个数最多排
趟就完全有序方向:从前往后、从后往前升降:升序、降序n-1冒泡排序Maopaopaixu算法实践原始数据170176165183162比较次数交换次数第一趟排序第二趟排序第三趟排序第四趟排序170165176162183421651701621761833216516217017618321162165170176183114+3+2+1=102+2+1+1=6总比较次数:总交换次数:冒泡排序Maopaopaixu算法实践原始数据170176165183162比较次数交换次数第一趟第二趟第三趟第四趟原始数据170176165183162比较次数交换次数第一趟第二趟第三趟第四趟原始数据170176165183162比较次数交换次数第一趟第二趟第三趟第四趟原始数据170176165183162比较次数交换次数第一趟第二趟第三趟第四趟①从前往后升序②从前往后降序③从后往前升序④从后往前降序17016517616218342165170162176
18332165162170
176
170
176
1831117617018316516242176183170165
16231183176170
165
16221183176
170
165
16210162170176165183
44162
165170176183
32162165170
176
1832016216517017618310183170176165162
43183
176170165162
31183176170
165
1622018317617016516210练一练有一组数为:6,2,9,8,7,4,经过一趟冒泡排序后的序列为:2,6,4,9,8,7,第二趟排序后的序列是()A.2,6,7,4,8,9 B.2,6,4,7,8,9C.2,4,6,7,9,8 D.2,4,6,7,8,9C冒泡排序Maopaopaixu程序实现——从前往后的升序forjinrange(______________):If____________________:foriinrange(______________):temp=a[j]a[j]=a[j+1]a[j+1]=tempa[j]>a[j+1]①如果符合条件,实现相邻两数交换②每一趟升降的控制当后者比前者小(升序)③每一趟比较方向及次数的控制④处理的趟数的控制1,n0,n-i冒泡排序Maopaopaixu程序变式——从前往后的降序?forjinrange(______________):If____________________:foriinrange(______________):temp=a[j]a[j]=a[j+1]a[j+1]=tempa[j]>a[j+1]①如果符合条件,实现相邻两数交换②每一趟升降的控制当后者比前者小(升序)③每一趟比较方向及次数的控制④处理的趟数的控制1,n0,n-ia[j]<a[j+1]练一练有如下一段代码a=[6,2,8,4,3,7]length=len(a)foriinrange(1,length):forjinrange(0,length-i):ifa[j]>a[j+1]:temp=a[j]a[j]=a[j+1]a[j+1]=tempprint(a)Q1:这段代码实现的是冒泡排序算法,根据代码可知排序(选填:从前往后或从后往前)的
(选填:升序/降序)。Q2:代码运行结果为
。其中第二趟排序结果为
。从前往后升序[2,3,4,6,7,8][2,4,3,6,7,8]冒泡排序Maopaopaixu自定义函数的使用对于需要重复调用的冒泡排序算法,我们可以创建自定义函数bubble_sort()来实现defbubble_sort(a):
n=len(a)foriinrange(1,n):
forjinrange(0,n-i):
ifa[j]>a[j+1]:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp使用方法:a=[3,1,9,7,6]bubble_sort(a)print(a)运行结果:[1,3,6,7,9]练一练运行以下Python程序段后,输出的列表为(
)defbubble_sort(L):length=len(L)foriinrange(1,3):forjinrange(length,i,-1):ifL[j]<L[j-1]:temp=L[j]L[j]=L[j-1]L[j-1]=tempa=[6,8,2,4,3,7]bubble_sort(a)print(a)A.[2,3,4,6,7,8] B.[8,7,6,4,3,2]C.[2,3,4,6,8,7] D.[2,3,6,8,4,7]D冒泡排序Maopaopaixu冒泡排序的程序优化优化:观察排序过程,可以发现第三趟冒泡排序后数组已经有序,后面两趟排序实际上没有做任何交换操作,因此可以设置一个标记变量flag来标记某趟排序过程中是否发生了交换。若无交换操作,表示已经完成排序,退出循环。defbubble_sort(a):
n=len(a)
flag=Falseforiinrange(1,n):
forjinrange(0,n-i):
ifa[j]>a[j+1]:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
flag=True
ifnotflag:
break
returna练一练有如下python程序段:a=[2,1,9,8,6,3]cnt=0foriinrange(len(a)-1,0,-1):flag=False
forjinrange(i):
ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]
flag=True
cnt+=1
ifnotflag:
break则程序运行结束后,变量cnt的值为()A.3
B.4
C.5
D.6B思考冒泡排序不足?数据交换发生的太频繁,影响计算机处理速度五个数据8,7,3,5,4,如何用尽可能少的交换次数,完成升序排序?8735483745887选择排序算法思想程序实现02选择排序Xuanzepaixu概念:选择排序Xuanzepaixu算法思想在排序数组的所有元素中找出最小(或最大)数据的元素,使它与第一个元素中的数据相互交换位置。然后在余下的元素中,找出最小(或最大)数据的元素与第二个元素中的数据相互交换位置。以此类推,直至排序完成。核心要素趟数:n个数最多排
趟就完全有序找最值(最大或最小)和谁交换(第一个位置或最后一个位置)n-1选择排序Xuanzepaixu435623155078原始数据1515562343507823152356435078431523435650785015234350567856第1轮第2轮第3轮第4轮152343505678第5轮问题1:6个数据共需处理_____轮?n个数据共需处理______轮?5n-1问题2:n个数据排序,最多交换次数为______次?n-1算法演算问题3:6个数一共比较了
次如果有n个数据进行选择排序,共需要比较____________次?n(n-1)/215选择排序Xuanzepaixu435623155078如何在数组中找到最小的数据?43231515最小的数据是15算法演算选择排序Xuanzepaixu找到了最小数组元素后,如何交换?如何确定最小元素在数组中的位置?d[0]d[1]d[2]d[3]d[4]d[5]435623155078确定元素的位置记录数组元素的下标K=0K=2K=3K=3K=3最小的数据在d[k]即d[3]如何把最小的元素和第1个数组元素进行交换?d[0],d[k]=d[k],d[0]算法演算选择排序Xuanzepaixu算法演算思考:如何在6个数据中找出最小的数据并与第1个数据进行交换?(代码如何编写)①先假设最小数组元素的下标为1②利用循环语句逐个比较数组元素,并记录较小数据的数组下标③将最小的数据与第1个数据进行交换选择排序Xuanzepaixu算法实现k=0forjinrange():If_____________:_______t=d[0]d[0]=d[k]d[k]=tIf_____________:1,6d[k]>d[j]k=jk!=0第1轮选择排序Xuanzepaixu算法实现推广到n个数据k=0forjinrange():If_____________:_______t=d[0]d[0]=d[k]d[k]=tIf_____________:1,6d[k]>d[j]k=jk!=0foriinrange():0,n-1ii+1,n+1it=d[i]d[i]=d[k]d[k]=t选择排序Xuanzepaixu算法实现foriinrange(0,n-2):k=i
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 办公场所安全工作自查报告
- 四川大学锦城学院-管理学-测评
- 海城市2023年三年级数学第二学期期末学业质量监测模拟试题含解析
- 哈尔滨市重点达标名校2025年初三下学期第二学段考试生物试题试卷含解析
- 食堂员工安全操作培训内容
- 新浙教版八下科学氧气制取与性质课件
- 适合在教师节送给老师的鲜花搭配文案
- 果洛藏族自治州玛多县2023-2024学年三下数学期末检测试题含解析
- 桂林市临桂县2023-2024学年小升初总复习数学精练含解析
- 记录仪产品相关项目建议书
- 预防冬季呼吸系统疾病
- 模具特种加工课程标准
- 汽轮机课程设计计算
- 汉高,国民淀粉,乳液涂料应用
- 飞行控制系统课件[共554页]
- 机械制造及自动化专业调研报告
- 商标侵权投诉书
- 武汉理工大学管理体制与运行机制改革工程实施方案
- 安全施工方案及预案
- 水质工程学作业及参考答案
- 一年级上册美术《美丽的大自然》课件
评论
0/150
提交评论