5.3.2选择排序课件-浙教版高中信息技术选修1

5.3.2选择排序第一次排序第二次排序第三次排序第四次排序任务完成！选择排序的基本思想是第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后从剩余的未排序元素中找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。在参加排序数组的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据交换位置，然后在余下的元素中找出最小（或最大）数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。以四个数据21,99,16,67为例，升序（从小到大）选择排序的过程如图所示：21991667原始数据123421991667第1次比较j=2k=1比较后，k=121991667第2次比较k=1j=3比较后，k=321991667第3次比较k=3j=4比较后，k=3并交换选择排序第一遍排序16992167第一遍排序后的结果123416992167第1次比较k=2j=3比较后，k=3第2次比较16992167k=3j=4比较后，k=3并交换选择排序第二遍排序162199671234第二遍排序后的结果第1次比较16219967k=3j=4比较后，k=3并交换选择排序第三遍排序162167991234第三遍排序后的结果数据已经有序，完成排序！选择排序算法对规模为n的数据进行排序，总共需要进行n-1遍加工。

在选择排序的每一遍操作中，最多需要进行一次交换，当某一遍的最小（或最大）数据元素的位置就在排序数组最前面时，不需要进行交换。即最坏情况下需要交换n-1次，最好情况下（排序元素已经有序）需要交换0次。选择排序的程序实现如下：a=[12,25,33,10,15]n=len(a)foriinrange(n-1):min_idx=i#记录最小值的索引forjinrange(i+1,n):ifa[j]<a[min_idx]:min_idx=j#更新索引ifmin_idx!=i:#判断是否需要交换位置a[min_idx],a[i]=a[i],a[min_idx]print(a)选择排序的迁移应用一a=[12,25,33,10,15]n=len(a)foriinrange(n-1):min_idx=i#记录最小值的索引forjinrange(n-1,i,-1):ifa[j]<a[min_idx]:min_idx=j#更新索引ifmin_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=0q=9whilep<=q:iMin=piMax=pforiinrange(p+1,q+1):ifa[i]<a[iMin]:iMin=iifa[i]>a[iMax]:iMax=ia[iMin],a[p]=a[p],a[iMin]ifiMax==p:iMax=iMina[iMax],a[q]=a[q],a[iMax]p=p+1q=q-1print(a)

优化原理：从两端往中间同时进行，一端从小到大排，一端从大到小排，变量p和q表示本次排序的范围（p前和q后的数据已经完成排序）。for语句找出本次排序的最小数组元素a[iMin]和最大数组元素a[iMax]，然后将a[iMin]与a[p]交换，将a[iMax]与a[q]交换。冒泡排序选择排序选择排序算法原理一边比较，一边交换先选出最大值或最小值的索引，再交换先选出最大值或最小值的索引，再交换核心代码foriinrange(1,n):forjinrange(n-1,i-1,-1):ifa[j]<a[j-1]:a[j],a[j-1]=a[j-1],a[j]foriinrange(1,n):k=i-1forjinrange(i,n):ifa[j]<a[k]:k=jifk!=i-1:

a[i-1],a[k]=a[k],a[i-1]foriinrange(1,n):k=i-1forjinrange(i,n):ifa[j]<a[k]:k=jifk!=i-1:

a[i-1],a[k]=a[k],a[i-1]相同点①n个数都需要n-1遍排序，其中变量i控制排序的遍数；②比较的次数一样多，都是n*（n-1）/2；③最好的情况下，交换的次数一样，都是0不同点边比较边交换，最坏的情况下交换的次数是n*(n-1)/2先选择再交换，最坏的情况下交换的次数是n-1如何区分因为是边比较边交换，所以交换的代码是在内层循环里面的因为是先选出最大值或最小值再交换，所以交换的代码在内层循环的外面练一练1.有如下Python程序段：a=[52,36,68,79,27]n=len(a)b=0c=0foriinrange(n-1):k=iforjinrange(i+1,n):ifa[j]<a[k]:k=jb=b+1ifk!=i:a[i],a[k]=a[k],a[i]c=c+1print(b,c)该程序段执行后，b和c的值分别为（）A.53B.44C.43D.34C2.某排序算法的Python程序段如下：a=[18,12,11,21,13]n=len(a)f=[False]*5#含有5个元素，且初始值为False的列表foriinrange(n):k=iforjinrange(n-1,i,-1):ifa[j]<a[