数据排序　课件【高效备课精研+知识精讲提升】浙教版（2019）高中信息技术选修1

知识回顾迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。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