5.3.2選擇排序課件-浙教版高中信息技術選修1

5.3.2選擇排序第一次排序第二次排序第三次排序第四次排序任務完成！選擇排序的基本思想是第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后從剩余的未排序元素中找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。在參加排序數(shù)組的所有元素中找出最小（或最大）數(shù)據(jù)的元素，使它與第一個元素中的數(shù)據(jù)交換位置，然后在余下的元素中找出最小（或最大）數(shù)據(jù)的元素，與第二個元素中的數(shù)據(jù)交換位置。以此類推，直到所有元素成為一個有序的序列。以四個數(shù)據(jù)21,99,16,67為例，升序（從小到大）選擇排序的過程如圖所示：21991667原始數(shù)據(jù)123421991667第1次比較j=2k=1比較后，k=121991667第2次比較k=1j=3比較后，k=321991667第3次比較k=3j=4比較后，k=3并交換選擇排序第一遍排序16992167第一遍排序后的結(jié)果123416992167第1次比較k=2j=3比較后，k=3第2次比較16992167k=3j=4比較后，k=3并交換選擇排序第二遍排序162199671234第二遍排序后的結(jié)果第1次比較16219967k=3j=4比較后，k=3并交換選擇排序第三遍排序162167991234第三遍排序后的結(jié)果數(shù)據(jù)已經(jīng)有序，完成排序！選擇排序算法對規(guī)模為n的數(shù)據(jù)進行排序，總共需要進行n-1遍加工。

在選擇排序的每一遍操作中，最多需要進行一次交換，當某一遍的最?。ɑ蜃畲螅?shù)據(jù)元素的位置就在排序數(shù)組最前面時，不需要進行交換。即最壞情況下需要交換n-1次，最好情況下（排序元素已經(jīng)有序）需要交換0次。選擇排序的程序?qū)崿F(xiàn)如下：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)遷移原理：將比較的順序修改為從后往前，每一遍循環(huán)中變量min_idx還是在記錄排序范圍中最小數(shù)據(jù)的元素索引。選擇排序的優(yōu)化在數(shù)組的所有元素中同時找出最小的元素和最大的元素，然后將這兩個元素分別與第一個和最后一個元素交換，在余下的元素中再找出最小和最大數(shù)據(jù)的元素，分別與第二個和倒數(shù)第二個元素交換，依次類推，直到所有元素的數(shù)據(jù)按升序排列，這就是選擇排序的優(yōu)化。代碼如下：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)

優(yōu)化原理：從兩端往中間同時進行，一端從小到大排，一端從大到小排，變量p和q表示本次排序的范圍（p前和q后的數(shù)據(jù)已經(jīng)完成排序）。for語句找出本次排序的最小數(shù)組元素a[iMin]和最大數(shù)組元素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個數(shù)都需要n-1遍排序，其中變量i控制排序的遍數(shù)；②比較的次數(shù)一樣多，都是n*（n-1）/2；③最好的情況下，交換的次數(shù)一樣，都是0不同點邊比較邊交換，最壞的情況下交換的次數(shù)是n*(n-1)/2先選擇再交換，最壞的情況下交換的次數(shù)是n-1如何區(qū)分因為是邊比較邊交換，所以交換的代碼是在內(nèi)層循環(huán)里面的因為是先選出最大值或最小值再交換，所以交換的代碼在內(nèi)層循環(huán)的外面練一練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)該程序段執(zhí)行后，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[