资源简介

(共19张PPT)
5.3.2 选择排序
第一次排序
第二次排序
第三次排序
第四次排序
任务完成！
选择排序的基本思想是第一次从待排序的数据元素中选出最小（或最大）
的一个元素，存放在序列的起始位置，然后从剩余的未排序元素中找到最小
（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序
的数据元素的个数为零。
在参加排序数组的所有元素中找出最小（或最大）数据的元素，使它与第
一个元素中的数据交换位置，然后在余下的元素中找出最小（或最大）数
据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成
为一个有序的序列。
以四个数据21,99,16,67为例，升序（从小到大）选择排序的过程如图所示：
21
99
16
67
原始数据
1
2
3
4
21
99
16
67
第1次比较
j=2
k=1
比较后，k=1
21
99
16
67
第2次比较
k=1
j=3
比较后，k=3
21
99
16
67
第3次比较
k=3
j=4
比较后，k=3并交换
选择排序第一遍排序
16
99
21
67
第一遍排序后的结果
1
2
3
4
16
99
21
67
第1次比较
k=2
j=3
比较后，k=3
第2次比较
16
99
21
67
k=3
j=4
比较后，k=3并交换
选择排序第二遍排序
16
21
99
67
1
2
3
4
第二遍排序后的结果
第1次比较
16
21
99
67
k=3
j=4
比较后，k=3并交换
选择排序第三遍排序
16
21
67
99
1
2
3
4
第三遍排序后的结果
数据已经有序，完成排序！
选择排序算法对规模为n的数据进行排序，总共需要进行n-1遍加工。
第一遍加工的比较次数为n-1，第二遍加工的比较次数为n-2，依次下去，
最后一遍（n-1遍）加工的比较次数为1。所以总的比较次数为(n-1)+(n-2)
+(n-3)+…+1=
在选择排序的每一遍操作中，最多需要进行一次交换，当某一遍的最小
（或最大）数据元素的位置就在排序数组最前面时，不需要进行交换。
即最坏情况下需要交换n-1次，最好情况下（排序元素已经有序）需要
交换0次。
选择排序的程序实现如下：
a=[12,25,33,10,15]
n=len(a)
for i in range(n-1):
min_idx=i #记录最小值的索引
for j in range(i+1,n):
if a[j]min_idx=j #更新索引
if min_idx!=i: #判断是否需要交换位置
a[min_idx],a[i]=a[i],a[min_idx]
print(a)
选择排序的迁移应用一
a=[12,25,33,10,15]
n=len(a)
for i in range(n-1):
min_idx=i #记录最小值的索引
for j in range(n-1,i,-1):
if a[j]min_idx=j #更新索引
if min_idx!=i: #判断是否需要交换位置
a[min_idx],a[i]=a[i],a[min_idx]
print(a)
迁移原理：将比较的顺序修改为从后往前，每一遍循环中变量min_idx还
是在记录排序范围中最小数据的元素索引。
选择排序的优化
在数组的所有元素中同时找出最小的元素和最大的元素，然后将这两个
元素分别与第一个和最后一个元素交换，在余下的元素中再找出最小和
最大数据的元素，分别与第二个和倒数第二个元素交换，依次类推，直
到所有元素的数据按升序排列，这就是选择排序的优化。
代码如下：
a=[31,69,55,23,18,57,90,82,97,27]
n=len(a)
p=0
q=9
while p<=q:
iMin=p
iMax=p
for i in range(p+1,q+1):
if a[i]iMin=i
if a[i]>a[iMax]:
iMax=i
a[iMin],a[p]=a[p],a[iMin]
if iMax==p:
iMax=iMin
a[iMax],a[q]=a[q],a[iMax]
p=p+1
q=q-1
print(a)
优化原理：从两端往中间同时进行，一端从小到大排，一端从大到小排，变量p和q表示本次排序的范围（p前和q后的数据已经完成排序）。for语句找出本次排序的最小数组元素a[iMin]和最大数组元素a[iMax]，然后将a[iMin]与a[p]交换，将a[iMax]与a[q]交换。
冒泡排序 选择排序 算法原理 一边比较，一边交换 先选出最大值或最小值的索引，再交换 核心代码 for i in range(1,n): for j in range(n-1,i-1,-1): if a[j]如何区分 因为是边比较边交换，所以交换的代码是在内层循环里面的 因为是先选出最大值或最小值再交换，所以交换的代码在内层循环的外面
练一练
1.有如下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程序段如下：
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
谢 谢

展开更多......

收起↑