5.3.2 选择排序 ppt课件（共19张PPT）-2023新浙教版《高中信息技术》选择性必修第一册.pptx

1、5.3.2 选择排序第一次排序第二次排序第三次排序第四次排序任务完成！选择排序的基本思想是第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后从剩余的未排序元素中找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。在参加排序数组的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据交换位置，然后在余下的元素中找出最小（或最大）数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。以四个数据21,99,16,67为例，升序（从小到大）选择排序的过程如图所示：2121991667原始数

2、据12342121991667第1次比较j=2k=1比较后，k=12121991667第2次比较k=1j=3比较后，k=32121991667第3次比较k=3j=4比较后，k=3并交换选择排序第一遍排序1616992167第一遍排序后的结果12341616992167第1次比较k=2j=3比较后，k=3第2次比较1616992167k=3j=4比较后，k=3并交换选择排序第二遍排序16162199671234第二遍排序后的结果第1次比较1616219967k=3j=4比较后，k=3并交换选择排序第三遍排序16162167991234第三遍排序后的结果数据已经有序，完成排序！选择排序算法对规模为

3、n的数据进行排序，总共需要进行n-1遍加工。在选择排序的每一遍操作中，最多需要进行一次交换，当某一遍的最小（或最大）数据元素的位置就在排序数组最前面时，不需要进行交换。即最坏情况下需要交换n-1次，最好情况下（排序元素已经有序）需要交换0次。选择排序的程序实现如下：a=12,25,33,10,15n=len(a)for i in range(n-1):min_idx=i#记录最小值的索引 for j in range(i+1,n):if ajamin_idx:min_idx=j#更新索引 if min_idx!=i:#判断是否需要交换位置 amin_idx,ai=ai,amin_idxprin

4、t(a)选择排序的迁移应用一a=12,25,33,10,15n=len(a)for i in range(n-1):min_idx=i#记录最小值的索引 for j in range(n-1,i,-1):if ajamin_idx:min_idx=j#更新索引 if min_idx!=i:#判断是否需要交换位置 amin_idx,ai=ai,amin_idxprint(a)迁移原理：将比较的顺序修改为从后往前，每一遍循环中变量min_idx还是在记录排序范围中最小数据的元素索引。选择排序的优化在数组的所有元素中同时找出最小的元素和最大的元素，然后将这两个元素分别与第一个和最后一个元素交换，在余

5、下的元素中再找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换，依次类推，直到所有元素的数据按升序排列，这就是选择排序的优化。代码如下：a=31,69,55,23,18,57,90,82,97,27n=len(a)p=0q=9while p=q:iMin=p iMax=p for i in range(p+1,q+1):if aiaiMax:iMax=i aiMin,ap=ap,aiMin if iMax=p:iMax=iMin aiMax,aq=aq,aiMax p=p+1 q=q-1print(a)优化原理：从两端往中间同时进行，一端从小到大排，一端从大到小排，变量p和q表示本次排

6、序的范围（p前和q后的数据已经完成排序）。for语句找出本次排序的最小数组元素aiMin和最大数组元素aiMax，然后将aiMin与ap交换，将aiMax与aq交换。冒泡排序冒泡排序选择排序选择排序算法原理一边比较，一边交换先选出最大值或最小值的索引，再交换核心代码for i in range(1,n):for j in range(n-1,i-1,-1):if ajaj-1:aj,aj-1=aj-1,ajfor i in range(1,n):k=i-1 for j in range(i,n):if ajak:k=j if k!=i-1:ai-1,ak=ak,ai-1相同点n个数都需要n-1

7、遍排序，其中变量i控制排序的遍数；比较的次数一样多，都是n*（n-1）/2；最好的情况下，交换的次数一样，都是0不同点边比较边交换，最坏的情况下交换的次数是n*(n-1)/2先选择再交换，最坏的情况下交换的次数是n-1如何区分因为是边比较边交换，所以交换的代码是在内层循环里面的因为是先选出最大值或最小值再交换，所以交换的代码在内层循环的外面练一练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 ajak:k=j b=b+1 if k!=i:ai,ak=ak,ai c=c+1 print(b,c)该程序段执行后，b和c的值分别为（）A.5 3 B.4 4 C.4 3 D.3 4C2.某排序算法的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 ajak:k=j if k!=i:ak,ai=ai,ak fi=True print(f)执行该程序段，f中元素值为True的个数是_。3谢 谢