5.3　数据排序——选择排序算法　课件　2022—2023学年浙教版（2019）高中信息技术选修1

选择排序算法 知识回顾：选择排序的基本思想 在参加排序的数组的所有元素中找出_______（或最大）的数据，使它与________ 元素（左端）中的数据相互交换位置，然后在余下的元素中找出最小（或最大）的数据，与第二个元素中的数据相互交换位置。以此类推，直到所有元素成为一个有序的序列。 最小 知识回顾：选择排序的基本思想 最小 第一个 例1：已知数组a的初始值[5,9,3,8,1,2],采用选择排序算法对其进行从小到大排序。请写出每一趟排序后数组a的值。 1，9，3，8，5，2 1，2，3，8，5，9 1，2，3，8，5，9 1，2，3，5，8，9 1，2，3，5，8，9 如何找到最小数呢？ 还记得我们找到全班最高的同学的例子吗？假设，我们把全班同学的身高都放在数组a（）中，如何找到最高的那位同学max？ 如果要找到的是最小数的位置k呢？ 5 9 3 8 1 2 数组a 0 4 1 2 3 5 0 下标 假设第一个人身高是最高的 与后面的所有数进行比较 k=j j k 比它大就跳到它的位置上 5 9 3 8 1 2 数组a 0 4 1 2 3 5 0 下标 通过变量描述选择排序的执行过程： i表示轮次 k初值 j表示数组下标 比较次数 本轮结果 0 1、2、3、4、5 5 1，9，3，8，5，2 1 2、3、4、5 4 1，2，3，8，5，9 2 3、4、5 3 1，2，3，8，5，9 3 4、5 2 1，2，3，5，8，9 4 5 1 1，2，3，5，8，9 0 1 2 3 4 一、程序实现冒泡排序： for i in range(_________): len(a)-1 for j in range(_____,_________): len(a) i+1 if a[j]<a[k]: k=______ 程序语言的核心不是背代码，而是理解算法？ k=____ i j if k!=i: a[i],a[k]=a[k],a[i] 说明k跳过 把a[i],a[k]=a[k],a[i]改成a[i],a[j]=a[j],a[i]可以吗？ 选择排序小结： n个数需要经过n-1轮才能完成整个排序过程。 比较次数：(n-1)+(n-2)+(n-3)……+1=n*(n-1)/2 交换次数为：0~n-1 找到最大的数，j的变化范围是从[i+1,n),可不可以写成[n-1,i)呢？ 如果是从后往前选择排序，代码该如何写呢？ 思维拓展： 二、读代码 例2：有如下python程序段 for i in range(4): k=i for j in range(i+1,len(a)): if a[j]<a[k]: k=j if k!=i: a[i],a[k]=a[k],a[i] f(i) = True 当数组元素a的值依次为“8，2， 1，21，3”，数组f的初值均为False,执行该程序段，f数组中元素值为True的个数有( )A.1个 B.2个 C.3个 D.4个 外循环控制轮次，n个元素进行了n-1轮循环，说明已完成排序 如果遇到更小的数，跳到它的位置上 将小的数换到前面 C 二、读代码 例3：有如下python程序段 a=list(“welcome to my class”) for i in range(len(a)-1): k=i for j in range(i+1,len(a)): if a[j]<a[k]: k=j if k!=i: a[i],a[k]=a[k],a[i] 则程序运行结束后，变量count的值是（ ）A.7 B.8 C.9 D.10 a=””.join(a) count=0 for i in range(len(a)-1): if a[i]==a[i+1]: conut+=1 A 提效方法：当我们判定好代码语句后，就已经知道排序的结果了，不需要一步一步执行过程 三、选择排序的优化 双向排序指的是在参加排序的所有元素中，同时选出最小值和最大值，分别交换到左、右边界，再缩小左右边界。 当选择排序某一轮没有交换时，并不能表示排序已经完成。我们可以通过两头双向排序来优化代码。 高考题改编 L,R=0,len(a)-1