算法與程序設(shè)計(jì)1數(shù)據(jù)排序?qū)ｎ}復(fù)習(xí)課件　

排序算法專(zhuān)題復(fù)習(xí)二輪復(fù)習(xí)2023.4.17四月份第四課時(shí)

學(xué)期第22課時(shí)教學(xué)目標(biāo)：歸并排序，選擇排序，插入排序，冒泡排序的基礎(chǔ)代碼格式教學(xué)難點(diǎn)：冒泡排序的優(yōu)化教學(xué)難點(diǎn)處理方案：例題剖析+逐層遞進(jìn)我們學(xué)過(guò)的排序算法：1.冒泡排序（首考已考，最重要）2.選擇排序（首考未考，但要會(huì)看基礎(chǔ)代碼）3.插入排序（首考未考，地方卷喜歡考）4.歸并排序（首考已考，思想重要如鏈表合二歸一就是歸并排序的變式，地方卷幾乎沒(méi)考過(guò)）由于冒泡排序我們已經(jīng)做過(guò)很多題，我們倒著從最不熟悉的開(kāi)始4，3，2，1lst1,lst2各自已按首位“時(shí)間”升序排序，要把lst2歸并到lst1中，使得lst1整體依然升序4.歸并排序23.1首考真題再現(xiàn)defmerge(lst1,lst2):i=len(lst1)-1j=len(lst2)-1fortinrange(len(lst2)):lst1.append([0,0,0])#為lst1追加一個(gè)元素[0,0,0]k=len(lst1)-1whilej>=0:ifi>=0andlst1[i][0]>lst2[j][0]:lst1[k]=lst1[i]i-=1else:lst1[k]=lst2[j]j-=1k-=1returnlst14.歸并排序23.1首考真題再現(xiàn)問(wèn)：while語(yǔ)句中循環(huán)體的執(zhí)行次數(shù)？A3.插入排序3.插入排序：習(xí)題集p68T11.【2022年6月寧波九校高二信息技術(shù)第11題】1．有如下python程序段，運(yùn)行該程序段后，列表a中的值可能是()importrandoma=[]foriinrange(6):a.append(random.randint(1,5)*2+i%2)foriinrange(1,5):j=i;k=a[j]whilea[j-1]<kandj>0:a[j]=a[j-1];j=j-1a[j]=kA．11,8,7,6,5,5 B．8,6,5,5,3,8 C．9,6,7,8,8,11 D．11,11,8,2,2,11a=[偶，奇，偶，奇，偶，奇]012345D2.經(jīng)典選擇排序的代碼：a=[3,2,5,4,1]#經(jīng)典選擇排序n=len(a)#找比i項(xiàng)小且最小的數(shù)的下標(biāo)j賦值給k，然后a[i]和a[k]互換foriinrange(n-1):#i標(biāo)記待排序區(qū)間左邊界k=iforjinrange(i+1,n):#掃描待排序區(qū)間，找最小值下標(biāo)j，給k=j，用當(dāng)前數(shù)a[i]和a[k]互換ifa[j]<a[k]:k=jifk!=i:#若a[i]不是最小值則將最小值交換到下標(biāo)為i的位置a[i],a[k]=a[k],a[i]數(shù)據(jù)變化過(guò)程如下：[3,2,5,4,1][1,2,5,4,3][1,2,3,4,5]練習(xí)1.某Python程序段如下:foriinrange(2):k=iforjinrange(i+1,5):ifa[j]>a[k];k=jifi!=k:t=a[i];a[i]=a[k];a[k]=t數(shù)組元素a[0]到a[4]的數(shù)據(jù)依次為“10,41,75,12,63”。則此程序運(yùn)行完成后數(shù)組元素a[0]到a[4]的數(shù)據(jù)依次是()

A.75,63,41,12,10B.10,12,41,63,75C.10,12,75,41,63D.75,63,10,12,41D練習(xí)2.利用如下Python程序段對(duì)列表a其進(jìn)行處理:a=[‘15’,’2’,’5’,’43’,’24’]i=4whilei>0:k=iforjinrange(i):ifa[k]<a[j]:k=ja[k],a[i]=a[i],a[k]i=i-1print(a)該程序段執(zhí)行后輸出的內(nèi)容是()A.[’15’,’2’,’24’,’43’,’5’]B.[’5’,’15’,’2’,’43’,’24’]C.[’5’,’15’,’2’,’24’,’43’]

D.[’2’,’5’,’15’,’24’,’43’]A2023.03杭州地區(qū)（含周邊）重點(diǎn)中學(xué)卷（雙向選擇排序，最小的向前換，最大的向后換）小明利用“在線(xiàn)社團(tuán)報(bào)名系統(tǒng)”收集了全校學(xué)生的社團(tuán)報(bào)名信息，并將報(bào)名數(shù)據(jù)導(dǎo)出到“社團(tuán)報(bào)名.xlsx”中，如第14題圖1所示。然后編寫(xiě)Python程序?qū)?bào)名數(shù)據(jù)進(jìn)行處理，生成分別以班級(jí)名和社團(tuán)名為文件名的Excel文件，以便分發(fā)給相應(yīng)的社團(tuán)指導(dǎo)老師和班主任。

第14題圖1第14題圖2（1）在對(duì)表格進(jìn)行數(shù)據(jù)整理時(shí)發(fā)現(xiàn)，關(guān)于“Jacky.Y”同學(xué)的記錄可能存在的數(shù)據(jù)問(wèn)題是__▲___（選填：A.數(shù)據(jù)缺失B.數(shù)據(jù)異常C.邏輯錯(cuò)誤D.數(shù)據(jù)格式不一致）。（2）其中生成每個(gè)社團(tuán)名單文件的過(guò)程是：先對(duì)報(bào)名數(shù)據(jù)按社團(tuán)名稱(chēng)進(jìn)行分類(lèi)，并對(duì)選報(bào)同一社團(tuán)的學(xué)生按班級(jí)進(jìn)行升序排序,然后生成各個(gè)社團(tuán)名單文件，如第14題圖2所示。對(duì)應(yīng)的程序代碼如下，請(qǐng)?jiān)趧澗€(xiàn)處填寫(xiě)合適的代碼。D（2）其中生成每個(gè)社團(tuán)名單文件的過(guò)程是：先對(duì)報(bào)名數(shù)據(jù)按社團(tuán)名稱(chēng)進(jìn)行分類(lèi)，并對(duì)選報(bào)同一社團(tuán)的學(xué)生按班級(jí)進(jìn)行升序排序,然后生成各個(gè)社團(tuán)名單文件，如第14題圖2所示。對(duì)應(yīng)的程序代碼如下，請(qǐng)?jiān)趧澗€(xiàn)處填寫(xiě)合適的代碼。importpandasaspddefread_file(filename): #讀入報(bào)名數(shù)據(jù)的原始文件，并將表中的數(shù)據(jù)轉(zhuǎn)換成列表，代碼略defsave_file(a):#保存名單到相應(yīng)社團(tuán)的Excel電子表格文件 df=pd.DataFrame(a,columns=[“班級(jí)”，“姓名”，“選報(bào)社團(tuán)”]) df.to_excel(①+“.xlsx”,index=False)a=read_file(“社團(tuán)報(bào)名.xlsx”)n=len(a)#按社團(tuán)名（參照拼音的字母順序）進(jìn)行升序排序，代碼略#統(tǒng)計(jì)各社團(tuán)人數(shù)，存在列表rs中，rs=[[“滑板社”，36]，…]，代碼略①a[0][2]或df.at[0,“選報(bào)社團(tuán)”]或df[“選報(bào)社團(tuán)”][0]s=0foriinrange(len(rs)):

②

left,right=s,s+num-1 whileleft<right: imin=imax=left forkinrange(left+1,right+1): ifa[k][0]<a[imin][0]:

imin=k

elifa[k][0]>a[imax][0]:

imax=k ifimin!=left: a[imin],a[left]=a[left],a[imin] ifimax==left:

③

ifimax!=right:

a[imax],a[right]=a[right],a[imax]

left=left+1;right=right–1

④

s+=numnum=rs[i][1]imax=iminsave_file(a[s:s+num])1：冒泡排序的基本思想每一輪從第0位或len（a）-1開(kāi)始，通過(guò)相鄰元素的比較，將較大或較小的數(shù)向后或向前推移的排序技術(shù)。由此會(huì)產(chǎn)生4種冒泡排序組合：1、從前向后冒，大的往后跑，升序2、從前向后冒，小的向后跑，降序3、從后向前冒，大的向前跑，降序4、從后向前冒，小的向前跑，升序1、從前向后冒，大的往后跑，升序a=[5,2,1,4,3]#從前向后冒，大的往后跑,升序foriinrange(1,len(a)):#外循環(huán)i控制冒泡輪數(shù)forjinrange(len(a)-i):#內(nèi)循環(huán)j控制冒泡方向ifa[j]>a[j+1]:#前一項(xiàng)>后一項(xiàng)a[j],a[j+1]=a[j+1],a[j]print(a)#監(jiān)控?cái)?shù)據(jù)變化j=0或1小數(shù)開(kāi)始，從前向后冒j=len（a）-1大數(shù)開(kāi)始，從后向前冒2、從前向后冒，小的向后跑，降序a=[5,2,1,4,3]foriinrange(1,len(a)):#外循環(huán)i控制冒泡輪數(shù)forjinrange(len(a)-i):#內(nèi)循環(huán)j控制冒泡方向ifa[j]<a[j+1]:#前一項(xiàng)<后一項(xiàng)a[j],a[j+1]=a[j+1],a[j]print(a)#監(jiān)控?cái)?shù)據(jù)變化j=0或1小數(shù)開(kāi)始，從前向后冒j=len（a）-1大數(shù)開(kāi)始，從后向前冒

3、從后向前冒，小的向前跑，升序a=[5,2,1,4,3]foriinrange(1,len(a)):forjinrange(len(a)-1,i-1,-1):ifa[j]<a[j-1]:a[j],a[j-1]=a[j-1],a[j]print(a)4、從后向前冒，大的向前跑，降序a=[4,2,1,5,3]

foriinrange(1,len(a)):forjinrange(len(a)-1,i-1,-1):ifa[j]>a[j-1]:a[j],a[j-1]=a[j-1],a[j]外循環(huán)i和內(nèi)循環(huán)j，合作控制冒泡的范圍2len（a）-2[4,5,3,2,1]

[5,4,2,1,3]

排序后：a=[5,4,3,2,1]誰(shuí)控制排序范圍？10.列表s包含8個(gè)互不相等的元素,即s[0],s[1],s[2],……,s[7]，有如下Python程序段：2023年1月首考第10題n=8foriinrange(1,n-1):forjinrange(1,n-i-1):ifs[j]>s[j-1]:s[j],s[j-1]=s[j-1],s[j]該程序段實(shí)現(xiàn)的是（

）A.s[0]到s[5]的降序排列 B.s[1]到s[6]的降序排列C.s[1]到s[7]的升序排列 D.s[2]到s[6]的升序排列A2023年1月首考第10題真題回顧例1：采用冒泡排序算法對(duì)某數(shù)據(jù)序列進(jìn)行排序，經(jīng)過(guò)第一輪排序后的結(jié)果是＂2，8，3，9，5，6，7＂，那么原數(shù)據(jù)序列不可能的是 ()A．8，3，9，5，2，7，6 B．8，3，9，2，6，5，7C．8，2，9，3，5，7，6 D．8，3，2，9，6，5，7D例2：有如下python程序段，程序運(yùn)行結(jié)束后，結(jié)果可能是以下哪個(gè)選項(xiàng)（

）a=[3,1,9,7,6,3]n=len(a)foriinrange(1,n):forjinrange(n-2,i-2,-1):ifa[j]<a[j+1]:a[j],a[j+1]=a[j+1],a[j]A.[9,3,1,7,6,3]C.[1,3,3,9,7,6]B.[9,7,6,3,3,1]D.[1,3,3,6,7,9]B外循環(huán)控制輪次，n個(gè)元素進(jìn)行了n-1輪循環(huán)，說(shuō)明已完成排序內(nèi)循環(huán)控制輪次，步長(zhǎng)-1，從后往前，確定前面的數(shù)后一個(gè)數(shù)比前一個(gè)數(shù)大，互換，大的往前D練習(xí)2：有如下Python程序段：a=[6,7,5,3,8,4]f=1foriinrange(2):forjinrange(4-2*i):ifa[j]*f<a[j+2]*fa[j],a[j+2]=a[j+2]<a[j]f=-fprint(a)該程序段運(yùn)行后，輸出結(jié)果為（

）A.[8,3,6,4,5,7]B.[3,4,5,6,7,8]C.[5,7,6,4,8,3]D.[6,4,8,7,5,3]變量f作用控制升降A(chǔ)冒泡排序算法優(yōu)化a=[23,20,13,18,14,11]x=y=z=0n=len(a)foriinrange(1,n):x+=1

forjinrange(0,n-i):

y+=1ifa[j]<a[j+1]:z+=1a[j],a[j+1]=a[j+1],a[j]

#統(tǒng)計(jì)排序加工的遍數(shù)#統(tǒng)計(jì)排序的比較次數(shù)#統(tǒng)計(jì)排序的交換次數(shù)#加工的遍數(shù)#單遍兩兩比較的范圍#比較的方向程序中的x、y、z有什么作用？a=[23,20,13,18,14,11]n=len(a)foriinrange(1,n):c=0

forjinrange(0,n-i,-1):ifd[j]<d[j+1]:c+=1d[j],d[j+1]=d[j+1],d[j]

ifc==0:break

如果一次加工過(guò)程中沒(méi)有發(fā)生數(shù)據(jù)交換說(shuō)明數(shù)據(jù)已經(jīng)有序。更新每一遍中交換次數(shù)的存儲(chǔ)變量用于統(tǒng)計(jì)每一遍中交換的次數(shù)判斷數(shù)據(jù)是否已經(jīng)有序優(yōu)化遍數(shù)a=[23,20,13,18,14,11]n=len(a)foriinrange(1,n):flag=False

forjinrange(0,n-i,-1):ifd[j]<d[j+1]:flag=Trued[j],d[j+1]=d[j+1],d[j]

ifflag==False:break

優(yōu)化遍數(shù)23.4嘉興二模第10題10.列表s中包含n個(gè)互不相等的元素，用Python編程實(shí)現(xiàn)如下功能:s[0]到s[n-1]降序排序，當(dāng)序列已經(jīng)有序時(shí)結(jié)束排序，部分代碼如下。n=len(s)foriinrange(1,n):

（1）

forjinrange(

（2）):

if（3）:

s[j],s[j-1]=s[j-1],s[j]flag=Trueifflag==False:break上述程序段中方框可選代碼為:①flag=True②flag=False③1,n-i+1④1,n-i⑤s[j]<s[j-1] ⑥s[j]>s[j-1]，則（1）（2）（3）處代碼依次為A.②④⑥ B.②③⑥ C.①④⑤ D.①③⑥?優(yōu)化遍數(shù)C典例1有如下Python程序段：d=[173,172,169,178,183]foriinrange(1,len(d)):c=0forjinrange(0,len(d)-i):ifd[j]>d[j+1]:c+=1;d[j],d[j+1]=d[j+1],d[j]ifc==0:breakprint(i)則程序運(yùn)行之后，i的值為（）A.1B.2C.3D.4注意：此優(yōu)化會(huì)在人觀察到有序后再做一遍！（不超過(guò)n-1遍）C173172169178183i=1172169173178183i=21691721731781832次1次i=31691721731781830次優(yōu)化遍數(shù)例4：有如下python程序段：a=[2,1,9,8,6,3]cnt=0foriinrange(len(a)-1,0,-1):flag=Falseforjinrange(i):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]flag=Truecnt+=1

ifnotflag:break則程序運(yùn)行結(jié)束后，變量cnt的值為

（

）A.3 B.4 C.5D.6B典例有如下Python程序段：d=[173,172,169,178,183]last=len(d)-1;s=0foriinrange(1,len(d)):forjinrange(0,last):s+=1ifd[j]>d[j+1]:

d[j],d[j+1]=d[j+1],d[j]

last=jprint(s)則程序運(yùn)行之后，s的值為（）A.10B.8C.6D.5D列表格還原比較過(guò)程！173172169178183比較lastj172173169172169優(yōu)化加工范圍練習(xí)1：已知字符串?dāng)?shù)組a的原始數(shù)據(jù)為[“128”,“26”,“9”,“61”,“15”,“2”,“318”],為了對(duì)該數(shù)組進(jìn)行排序操作，小美編寫(xiě)了如下Python程序：foriinrange(3):forjinrange(6,i+1,-1):ifa[j]<a[j-1]:a[j],a[j-1]=a[j-1]<a[j]則程序運(yùn)行后，數(shù)組a的值為（

）A.[“128”,“15”,“2”,“26”,“318”,“61”,“9”]B.[“128”,“15”,“26”,“9”,“61”,“2”