5.3 选择排序 课件(共12张PPT)

资源下载
  1. 二一教育资源

5.3 选择排序 课件(共12张PPT)

资源简介

(共12张PPT)
5.3数据排序
——选择排序
冒泡排序
冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。
算法思想
升序时:大则交换,使得从前向后比较时________下沉;
降序时:小则交换,使得从前向后比较时________下沉。
大数
小数
缺点:交换次数过于频繁,浪费效率
核心要素
加工遍数:n个数最多加工 遍就完全有序
范围及方向:范围受加工遍数和比较的两个数影响;从前往后、从后往前
升序/降序:相邻比较,逆则交换
n-1
选择排序
在排序数组的所有元素中找出最小(或最大)数据的元素,使它与第一个元素中的数据相互交换位置。然后在余下的元素中,找出最小(或最大)数据的元素与第二个元素中的数据相互交换位置。以此类推,直至排序完成。
算法思想
核心要素
加工遍数:n个数最多加工 遍就完全有序
范围:范围受加工遍数影响;
升序/降序:最小/大值交换到第一个位置
n-1
选择排序过程
初始值
1遍加工结果:
j:____________
比较____次
交换____次。
2遍加工结果:
j:____________
比较____次
交换____次。
3遍加工结果:
j:____________
比较____次
交换____次。
4遍加工结果:
j:____________
比较____次
交换____次。
29
36
39
38
44
44
36
39
38
29
44
39
36
38
29
44
39
38
36
29
44
39
38
36
29
d[j]与d[k]比较,k存储最大值索引
[1,n-1]
[2,n-1]
4
1
3
1
[3,n-1]
2
1
[4,n-1]
1
0
选择排序
d=[29,36,39,38,44]
n=len(d)
for i in range(_________):#加工遍数
k=i-1
for j in range(________):#每遍加工范围
if d[j]>d[k]:#求最大值索引
k=j
if k != i-1:
___________________#交换
print(d)
i表示遍数 j表示数组下标
1
[1,n-1]
2
[2,n-1]
3
[3,n-1]
4
[4,n-1]
1,n
i,n
d[k],d[i-1]=d[i-1],d[k]
i的范围:______________
j的范围:______________
[1,n-1]
[i,n-1]
课堂练习
【例1】 有6位裁判为运动员评分,给出的分数分别为49,45,61,46,58,57。采用选择排序算法对其进行排序,若完成第一遍时的结果为61,45,49,46,58,57,则完成第二遍时的结果是(  )
A.61,45,49,46,58,57 B.61,58,57,49,45,46
C.61,58,57,46,45,49 D.61,58,49,46,45,57
D
解析 从第一遍的结果可以看出排序要求是从大到小排。选择排序的基本思想是从所有的记录中选出最大(从大到小排序时)的数据,把它与第一个数据进行交换,然后在其余的记录中再选出最大的数据与第二个数据进行交换。因此第二遍排序58与45交换,得到61、58、49、46、45、57。
选择排序小结
有比较不一定有交换。
交换次数<=比较次数
n个数据比较次数为
n个数据交换次数为
【结论】比较与交换
(n-1)+(n-2)+...+1=n*(n-1)/2
0——n-1
冒泡排序与选择排序
冒泡排序 选择排序 算法原理 一边比较,一边交换 先选出最大值或最小值的索引,再交换 核心代码 for i in range(1,n): for j in range(n-1,i-1,-1): if a[j]如何区分 因为是边比较边交换,所以交换的代码是在内层循环里面的 因为是先选出最大值或最小值再交换,所以交换的代码在内层循环的外面
n*(n-1)/2
n-1
a[j],a[j-1]=a[j-1],a[j]
a[i-1],a[k]=a[k],a[i-1]
课堂练习
2.某排序算法的Python程序段如下:
a=[18,12,11,21,13]
n=len(a)
f=[False]*5 #含有5个元素,且初始值为False的列表
for i in range(n):
k=i
for j in range(n-1,i,-1):
if a[j]k=j
if k!=i:
a[k],a[i]=a[i],a[k]
f[i]=True
print(f)
执行该程序段,f中元素值为True的个数是___________。
3
课堂练习
3.有如下Python程序段:
a=[52,36,68,79,27]
n=len(a)
b=0
c=0
for i in range(n-1):
k=i
for j in range(i+1,n):
if a[j]k=j
b=b+1
if k!=i:
a[i],a[k]=a[k],a[i]
c=c+1
print(b,c)
该程序段执行后,b和c的值分别为( )
A.5 3 B.4 4 C.4 3 D.3 4
C
课堂练习
2.有如下python程序段:先生成6个随机正整数,依次存入数组元素a[0]到a[5],代码略
for i in range(0,2):
for j in range(5,i,-1):
if a[j]%3>a[j-1]%3:
a[j],a[j-1]=a[j-1],a[j]
执行上述程序段后,下列选项中,a[0]到a[5]各元素值不可能的是( )
D
End
Thank you

展开更多......

收起↑

资源预览