资源简介

(共16张PPT)
选择排序算法
知识回顾：选择排序的基本思想
在参加排序的数组的所有元素中找出_______（或最大）的数据，使它与________ 元素（左端）中的数据相互交换位置，然后在余下的元素中找出最小（或最大）的数据，与第二个元素中的数据相互交换位置。以此类推，直到所有元素成为一个有序的序列。
最小
知识回顾：选择排序的基本思想
最小
第一个
例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]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]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]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
while Limin=imax=L
for i in range(L+1,R+1):
if a[i]>a[imax]:
imax=i
elif a[i]imin=i
a[imin],a[L]=a[L],a[min]
if imax==L:
imax=_____
a[imax],a[L]=a[L],a[imax]
L=L+1
R=R-1
3,1,2,8,5
8,1,2,3,5
imin
6.【台州】有如下VB程序段:
a(1)=3:a(2)=8:a(3)=9:a(4)=5:a(5)=6:a(6)=1
n=6
m=int(rnd*3)*2+1
for i=m to 5
k=i
for j=6 to i+1 step -1
if a[j]next j
tmp=a[k):a(k)=a(i):a(i)=tmp
next i
该程序段执行后，a（1）~a（6）个元素不可能的是（ ）
A.1,3,5,6,8,9 B.3,1,5,6,8,9
C.3,8,1,5,6,9 D.3,8,9,5,1,6
B
考察：m的变化与排序区域
7.【2019.6舟山】有如下程序段：
n=6
m=int(rnd*6+1)
for i=1 to n-m
k=i
for j=m to n-i
if a(j)>a(j+1) then
t=a(j):a(j)=a(j+1):a(j+1)=t
elseif a(j)>a(k) then
k=j
endif
next j
tmp=a(k):a(k)=a(i):a(i)=tmp
next i
数组元素a(1)到a(6)的值依次为“2,77,82,71,5,42”。经过该程序段加工后，数组元素 a(1)到a(6)的值不可能是 （ ）
A.2,5,42,71,82,77 B.5,77,82,71,2,42
C.2,77,42,5,71,82 D.2,77,82,5,42,71
本节课小结
回顾冒泡排序的基本思想，并基于基本思想完成代码的编写
通过i，j变化了解此类题型解题的一般方法
通过引入变量对冒泡排序进行优化
谢谢

展开更多......

收起↑