资源简介

(共25张PPT)
课时31 选择排序
一、选择排序算法的基本思想
在参加排序的所有元素中找出最小（或最大）的数据，将它与第一个元素（左端）交换位置。然后在余下的元素中找出最小（或最大）的数据，与第二个元素交换位置。以此类推，直到所有元素成为一个有序的序列。
如图所示，n=6 时，最多进行 5 轮选择排序。
二、选择排序算法的过程
对 n 个数进行选择排序时，总共需要排序 n-1 趟，第 1 趟需进行 n-1 次比较，第 2 趟需进行 n-2 次比较，以此类推，总共比较的次数是 (n-1)+(n-1)+…+ 1=n(n-1)/2，其时间复杂度为 O(n2)。
三、选择排序算法的算法效率
def selection_sort(a):
n=len(a)
for i in range(n-1): #i标记待排序区间左边界
k=i
for j in range(i+1,n): #寻找最小值的下标
if a[j]k=j #k 记录当前最小值的下标
if k!=i: #若 a[i]不是最小值
a[i],a[k]=a[k],a[i]
return a
四、选择排序的 Python 实现
典例 1 对数组元素 a[0]到 a[6]进行选择排序，经过第 1 遍排序加工后，数组元素 a[0]到 a[6]的数据依次是“10,41,75,12,85,11,63”，则下一遍排序加工后，数组元素 a[0]到 a[6]的数据依次是（　　）
A.10,11,41,75,12,85,63
B.10,11,75,12,85,41,63
C.10,11,12,75,85,41,63
D.10,41,75,12,63,11,85
B
√
题型导向一　选择排序的原理
胜券点拨1
明考向 本题主要考查选择排序的原理和过程
审关键 第1个位置为最值
考场思 维快闪 第1遍选择排序加工后，最小值10在最左端，故该算法为升序排序，故第2遍排序加工时，次小值11应和第2个位置的元素41交换，其余元素的位置不变
典例 2 有如下 Python 程序段：
d=[5,9,10,7,8,20,6,0]
for i in range(len(d)-1):
k=i
for j in range(i+1,len(d)):
if d[j]k=j
if k!=i:
d[k],d[i]=d[i],d[k]
print(d)
执行该程序段后，输出的结果是 （　　）
A.[20,10,9,8,7,6,5,0] B.[5,9,10,7,8,20,6,0]
C.[0,5,6,7,8,9,10,20] D.[0,5,6,7,8,20,10,9]
C
√
题型导向二　选择排序的 Python 实现
胜券点拨2
明考向 本题考查选择排序算法的程序实现
审关键 选择排序算法实现过程中的语句作用
考场思 维快闪 外循环变量i遍历数组d中的元素索引，赋值给变量k，内循环变量j遍历i之后的索引，依次比较d[j]和d[k]，将较小值的索引赋值给变量k，内循环结束后，若k与i不相等，则交换d[k]和d[i]的值，因此每轮外循环将数组中的最小值交换到最前面，从而实现升序排序
典例 3 有如下 Python 程序段：
a=[10,41,75,12,63]
for i in range(2):
k=i
for j in range(i+1,len(a)):
if a[j]>a[k]:
k=j
if i!=k:
t=a[i]
a[i]=a[k]
a[k]=t
print(a)
执行该程序段后，输出的结果是 （　　）
A.[75,63,41,12,10] B.[10,12,41,63,75] C.[10,12,75,41,63] D.[75,63,10,12,41]
D
√
题型导向三　选择排序的变式
胜券点拨3
明考向 本题主要考查选择排序算法的变式
审关键 外循环决定排序的轮数
考场思 维快闪 根据代码“if a[j]>a[k]”可知，该程序段实现降序排序，根据代码“for i in range(2)”可知，共进行2轮排序：第1轮排序将最大值75和第1个位置的元素10交换，第2轮排序将次大值63与第2个位置的元素41交换，其余数据保持不变
典例 4 有如下 Python 程序段：
from random import randint
x=randint(2,4)*2
a=[9,2,5,1,3,4,8,7]
n=len(a)
for i in range(0,n-1):
k=i
for j in range(i+1,x):
if a[k]>a[j]:
k=j
if i!=k:
a[k],a[i]=a[i],a[k]
print(a)
执行该程序段后，输出的结果不可能是 （　　）
A.[1,2,3,4,5,7,8,9] B.[1,2,3,4,5,9,8,7] C.[1,2,5,9,3,4,8,7] D.[1,2,3,4,5,9,7,8]
D
√
胜券点拨4
明考向 本题主要考查选择排序算法的变式
审关键 内循环决定比较的范围
考场思 维快闪 x为[4,8]内的偶数，内循环的比较范围为[i+1,x-1]，因此数组a中只有前x个元素参与排序，每轮排序将范围内的最小值交换到最前面。当x的值为4时，只有前4个元素参与排序，排序结果为[1,2,5,9,3,4,8,7]；当x的值为6时，只有前6个元素参与排序，排序结果为[1,2,3,4,5,9,8,7]；当x的值为8时，所有元素都参与排序，排序结果为[1,2,3,4,5,7,8,9]
典例 5 有如下 Python 程序段：
a=[9,4,8,10,7,11,6,5]
for i in range(7):
k=i
f=(-1)**i
for j in range(i+1,8):
if a[j]*f>a[k]*f:
k=j
if i!=k:
a[i],a[k]=a[k],a[i]
print(a)
执行该程序段后，输出的结果是 （　　）
A.[4,9,10,8,11,7,5,6] B.[11,4,10,5,9,6,8,7]
C.[4,5,6,7,8,9,10,11] D.[4,11,5,10,6,9,7,8]
B
√
胜券点拨5
明考向 本题主要考查选择排序算法的变式
审关键 比较语句决定排序方式
考场思 维快闪 每次循环变量f的值在1和-1之间交替变化，当f的值为1时，将最大值交换到前面，当f的值为-1时，将最小值交换到前面，因此最终数组a中的元素依次为最大值、最小值、次大值、次小值……
典例 6 ［2025江浙发展共同体］某机器在上午 8 点到 12 点的时间段可以安排加工产品。按如下规则选择部分产品加工：先选择所有产品中加工结束时间最早的产品（若有多个产品的结束时间相同，则优先选择加工时长少的产品），然后在剩余产品中选择时间不冲突的加工结束时间最早的产品进行加工，以此类推，直至选择完毕。编写 Python 程序，实现读取 n 个产品的编号、预计到达时间和所需加工时长，输出选择加工的产品编号、加工起始时间和结束时间。
请回答下列问题：
（1）若有 6 个产品的产品编号、预计到达时间和所需加工时长（分钟）为[[1,"08:00",105],[2,"08: 30",60],[3,"09:35",105],[4,"10:30",90],[5,"10:00",35],[6,"09:40",40]]，则选择加工的第 2 个
产品的编号为　　　　　　　（填数字）。
6
题型导向四　选择排序的应用
flag=[False]*n
for i in range(n-1):
　　　①　　　1
for j in range(i+1,n):
if a[j] [4] k=j
a[i],a[k]=a[k],a[i]
st=convert1("08:00")
ed=convert1("12:00")
for i in range(n):
if a[i][3]>=st and a[i][4]<=ed:
flag[i]=True
　　　②　　　1
print("产品编号","起始时间","结束时间")
for i in range(n):
if 　　　③　　　:
print(a[i][0],a[i][1],convert2(a[i][4]))
（2）实现上述功能的 Python 程序如下，请在画线处填入合适的代码。
def convert1(t):
'''将时间 t 转换为整数，如"08:30"转换为 510，代码略'''
def convert2(t):
'''将整数 t 转换为时间，如 510 转换为"08:30"，代码略'''
'''读取 n 个产品的数据存入 a[0]至 a[n-1]中，a[i]包含 3 个数据项，a[i][0]、a[i][1]和 a[i][2]分别存放产品编号、预计到达时间和所需加工时长，代码略'''
for i in range(n):
st=convert1(a[i][1])
a[i].append(st)
ed=st+a[i][2]
a[i].append(ed)
k=i
st=a[i][4]
flag[i]　或　flag[i]==True
胜券点拨6
明考向 本题考查选择排序算法的应用
审关键 选择排序的基本算法思想
考场思维快闪 （1） 先选择所有产品中加工结束时间最早的产品，则选择的第1个产品是[2,"08:30",60]，结束时间是09:30，则剩余产品中时间不冲突的有[3,"09:35",105]，[4,"10:30",90]，[5,"10:00",35]，[6,"09:40",40]，其中加工结束时间最早的产品是[6,"09:40",40]，结束时间是10:20，剩余产品中时间不冲突的为[4,"10:30",90]，结束时间是12:00。因此选择加工的产品编号依次是2、6、4
（2） ①根据选择排序算法，应初始化比较索引为当前索引，故填入代码为k=i。②要选择时间不冲突的产品进行加工，故更新起始时间为当前选择产品的结束时间，故填入代码为st=a[i][4]。③flag为True表示已选择了该产品，故填入代码为flag[i]或flag[i]==True
1.下列关于冒泡排序和选择排序的说法，正确的是 （　　）
A.冒泡排序中，值相同的两个数据在排序前后的相对位置可能变动
B.选择排序中，值相同的两个数据在排序前后的相对位置可能变动
C.冒泡排序中，数据的交换次数与比较次数一定相同
D.选择排序中，数据的交换次数与比较次数一定相同
冒泡排序中由于是相邻两个数据进行比较，故值相同的两个数据的相对位置不会变化。选择排序中，由于每次选择数据中最小（或最大）元素与数据中的元素进行比较，有可能出现值相同的两个数据在与最小（或最大）元素比较时被交换到其他位置，导致相对位置发生改变。冒泡排序和选择排序中，数据的交换次数小于等于比较次数。
一、选择排序的原理
B
√
2.使用选择排序算法对数据8，7，5，9，5，6进行降序排序，需要交换的次数是 （　　）
A.3次
B.4次
C.5次
D.6次
已知使用选择排序算法对数据8，7，5，9，5，6进行降序排序，第1次交换8和9，变为9，7，5，8，5，6；第2次交换8和7，变为9，8，5，7，5，6；第3次交换5和7，变为9，8，7，5，5，6；第4次交换5和6，变为9，8，7，6，5，5，此时完成排序。故共交换了4次。
B
√
3.有如下Python程序段：
a=[8,3,6,0,1,2,9,4]
n=len(a)
i=n-1
while i>0:
imax=i
for j in range(i):
if a[j]>a[imax]:
imax=j
if imax!=i:
a[i],a[imax]=a[imax],a[i]
i-=1
print(a)
执行该程序段后，输出的结果是 （　　）
A.[9,8,3,6,0,1,2,4]
B.[3,6,0,1,2,4,8,9]
C.[9,8,6,4,3,1,2,0]
D.[0,1,2,3,4,6,8,9]
D
√
该程序段使用选择排序算法逐个将数组剩余部分的最大数交换到未排序部分的末尾，故最终得到的是升序排序的数组。
二、选择排序的Python实现
4.有如下Python程序段：
import random
d=[33,24,45,39,67,18]
m=2*int(random.random()*3+1)
for i in range(m,5):
k=i
for j in range(i+1,6):
if d[j]k=j
if i!=k:
d[i],d[k]=d[k],d[i]
执行该程序段后，数组d的值不可能是 （　　）
A.[18,24,33,39,45,67]
B.[33,24,18,39,45,67]
C.[33,24,45,39,67,18]
D.[33,24,45,39,18,67]
A
√
随机数m的取值有2、4、6三种可能，然后以下标m为起点，对部分数组区间进行升序的选择排序，故最终得到的数组d只有三种可能：①从d[2]~d[5]升序；②从d[4]~d[5]升序；③保持原顺序不变。故最终得到的数组d不可能从d[0]~d[5]升序。
三、选择排序的变式
5.采用选择排序算法对某数据序列进行排序，若经过第一轮排序后的结果是2，8，3，5，6，7，9，则原数据序列不可能是 （　　）
A.8，2，3，5，6，7，9
B.7，8，3，5，6，2，9
C.8，2，9，3，5，7，6
D.2，8，3，9，6，7，5
已知选项A、B可以将序列中最小值与第一个元素交换得到，选项D可以将序列中最大值与最后一个元素交换得到，故原数据序列不可能是8，2，9，3，5，7，6。
C
√
6.有数组li=[4,9,7,13,25,11,12,3]，若对该数组进行升序的选择排序，依次在未排序序列中找到最小元素，交换到排序序列的起始位置，则第三次有数据交换位置时，两个数据的下标分别是 （　　）
A.3和7 B.3和1
C.2和7 D.2和5
第一次交换数据4和3，即交换li[0]和li[7]；第二次交换9和4，经过第一次交换后，4的位置下标为7，所以此处交换li[1]和li[7]；之后数字7在 li[2]的位置，无须交换，第三次交换13和9，在经过第二次交换后，9的位置下标为7，所以第三次交换的是li[3]和li[7]。
A
√
7.已知长度为n的数组a为无序数组，其对应索引数组b的初始值为b[i]=i，有如下Python程序段：
for i in range(n-1):
k=i
for j in range(i+1,n):
if 　　　　　　　:
k=j
if k!=i:
b[k],b[i]=b[i],b[k]
执行该程序段后，能够使得a[b[0]]<=a[b[1]]<=…<=a[b[n-1]]，则画线处应填入的正确代码为 （　　）
A.a[j]B.a[b[j]]C.a[j]D.a[b[i]]B
该程序段用选择排序算法对索引数组b进行排序，实现升序输出数组a的效果。因为是让b[k]指向当前最小元素，故判断条件应为a[b[j]]√
8.［2025金色阳光联盟］某排序算法的Python程序段如下：
a=[98,66,16,78,25,69,55,78]
n=len(a);c=0
for i in range(n-1):
k=i
for j in range(i+1,n):
if a[j]>a[k]:
k=j
if k!=i:
a[k],a[i]=a[i],a[k]
c+=1
下列说法正确的是 （　　）
A.执行该程序段后，a的值为[16,25,55,66,69,78,78,98]
B.将代码“if a[j]>a[k]:”修改为“if a[j]>=a[k]:”，不会影响程序的运行结果
C.若某一轮中没有数据交换，则说明数组a已经有序
D.执行该程序段后，c的值为5
B
该程序段通过选择排序算法对数组a中的元素进行降序排序，每轮找到最大值，然后与最前面的元素的进行交换，变量c表示排序的轮数。执行该程序段后，a的值为[98,78,78,69,66,55,25,16]，c的值为7。若某一轮中没有数据交换，则说明当前元素已经排在了正确的位置，并不代表数组a已经有序。
√
9.利用选择排序算法的思想，将数组排列为指定的顺序，规则如下：
①找出数组中的最大数和最小数，将最大数交换到数组第一位，最小数交换到数组第二位。
②在剩余部分继续寻找最大数和最小数，依次交换到第三位和第四位……直到数组中所有元素排序完毕。
　　例如，当数组a=[1,2,3,4,5,6]时，经过排列后数组a的值为[6,1,5,2,4,3]。实现上述功能的Python程序如下：
a=[6,4,1,3,4,8,0]
i=0
while 　　　③　　　:
x= imax(a[i:])　#①
a[i],a[x]=a[x],a[i]
y= imin(a[i:])　#②
a[i+1],a[y]=a[y],a[i+1]
　　　④　　　1
print(a)
def imax(a):
imax=0
for i in range(len(a)):
if a[i]>a[imax]:
imax=i
return imax
def imin(a):
imin=0
for i in range(len(a)):
if a[i]imin=i
return imin
ii+=2
请回答下列问题：
（1）执行该程序段后，输出的结果是[6,4,3,0,1,8,4]，与预期不符，则加框①②处代码应修改为　　　　　　　（单选）。
A.①imax(a)　②imin(a)
B.①imax(a[i+1:])　②imin(a[i+1:])
C.①imax(a[i:])+i　②imin(a[i:])+i
D.①imin(a[i:])　②imax(a[i:])
（2）请在画线③④处填入合适的代码。
C
√
（1）自定义函数的作用是输出数组最大值（最小值）在数组中的位置下标，当传入的参数为a[i:]时，则a[i:]被作为一个整体，返回的下标是其在a的子序列a[i:]中的下标，画线处x要在返回的数组a下标的基础上，再加上子列表的初始值i。　（2）③处while循环的迭代变量是i，所以判断条件与i有关，i表示遍历a中的下标，且循环体内的最大下标值为i+1，所以i的值最大为len(a)-2，故填入代码为i

展开更多......

收起↑