2022選考復(fù)習(xí)系列之一(冒泡排序復(fù)習(xí))【新教材】浙教版(2019)高中信息技術(shù)選擇性必修一《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》_第1頁
2022選考復(fù)習(xí)系列之一(冒泡排序復(fù)習(xí))【新教材】浙教版(2019)高中信息技術(shù)選擇性必修一《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》_第2頁
2022選考復(fù)習(xí)系列之一(冒泡排序復(fù)習(xí))【新教材】浙教版(2019)高中信息技術(shù)選擇性必修一《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》_第3頁
2022選考復(fù)習(xí)系列之一(冒泡排序復(fù)習(xí))【新教材】浙教版(2019)高中信息技術(shù)選擇性必修一《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》_第4頁
2022選考復(fù)習(xí)系列之一(冒泡排序復(fù)習(xí))【新教材】浙教版(2019)高中信息技術(shù)選擇性必修一《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》_第5頁
已閱讀5頁,還剩19頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

冒泡排序復(fù)習(xí)浙教版新教材(2019)《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》選擇性必修1——冒泡排序復(fù)習(xí)經(jīng)典冒泡從后往前冒,以下演示從前往后冒2

345101505第一遍:比較5次,交換2次經(jīng)典冒泡從后往前冒,以下演示從前往后冒2

34105第一遍:比較5次,交換2次第二遍:比較4次,交換2次1404經(jīng)典冒泡從后往前冒,以下演示從前往后冒2

3104

5第一遍:比較5次,交換2次第二遍:比較4次,交換2次3130第三遍:比較3次,交換2次經(jīng)典冒泡從后往前冒,以下演示從前往后冒2

103

4

5第一遍:比較5次,交換2次第二遍:比較4次,交換2次第三遍:比較3次,交換2次2120第四遍:比較2次,交換2次經(jīng)典冒泡從后往前冒,以下演示從前往后冒1

02

3

4

5第一遍:比較5次,交換2次第二遍:比較4次,交換2次第三遍:比較3次,交換2次第四遍:比較2次,交換2次10第五遍:比較1次,交換1次經(jīng)典冒泡:從前往后與從后往前,總比較次數(shù)和交換次數(shù)不變,排序遍數(shù)n-1一、冒泡排序思想排序遍數(shù)是?比較次數(shù)?交換次數(shù)?1、2組從前往后冒3、4組從后往前冒一、冒泡排序思想冒泡排序思想總結(jié):★升序:將后數(shù)小于前數(shù)的兩個數(shù)進行交換;降序:將后數(shù)大于前數(shù)的兩數(shù)進行交換★n個數(shù)最多進行

n-1遍排序★兩數(shù)比較的次數(shù)為:n*(n-1)/2★兩數(shù)交換次數(shù)最多為:

n*(n-1)/2升序核心代碼foriinrange(0,n-1):forjinrange(n-1,i,-1)ifa[j]<a[j-1]:

交換a[j]與a[j-1]控制遍數(shù)為n-1遍即可初值定,控制每遍冒泡方向和比較次數(shù),一般為n-1/n-2或0,1。終值與i和前后項表達相關(guān)。初值和終值不能換位置。控制次序——后項<前項,交換,升序。表達方法a[j-1]或a[j+1],從j初值可得二、冒泡排序程序?qū)崿F(xiàn)(一維數(shù)組為例)課堂練習(xí)7.

D三、冒泡排序應(yīng)用觀察d變量,有哪些特征?三、冒泡排序應(yīng)用編程實現(xiàn),以左圖形式顯示三、冒泡排序應(yīng)用1編程實現(xiàn),按總分高到低排序三、冒泡排序應(yīng)用2編程實現(xiàn),女生在前,男生在后,分別按降序排序三、冒泡排序應(yīng)用3編程實現(xiàn),男生在前,降序排序,女生在后,升序排序三、冒泡排序應(yīng)用3還有哪些排序形式?出現(xiàn)同分情況怎么處理?只排男生或只排女生?(位置不變)只排前三名不改變原有順序排序?四、冒泡排序優(yōu)化1——遍數(shù)優(yōu)化foriinrange(1,len(d)):

flag=False

forjinrange(0,len(d)-i):ifd[j]>d[j+1]:

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

ifflag==False:

break標記是否存在交換變量flag,默認無序有交換,則標記True內(nèi)循環(huán)結(jié)束如無交換,則表明有序一、冒泡排序優(yōu)化1——遍數(shù)優(yōu)化i=1;flag=FalseWhilei<len(d)andflag==False

flag=True

forjinrange(0,len(d)-i):ifd[j]>d[j+1]:

flag=False

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

i+=1notflag課堂練習(xí)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:

break則程序運行之后,i的值為()A.1B.2C.3D.4cd=[173,172,169,178,183]foriinrange(1,len(d)):forjinrange(0,len(d)-i):ifd[j]>d[j+1]:c+=1

d[j],d[j+1]=d[j+1],d[j]則程序運行之后,c的值為(

)A.10B.8C.5D.3D課堂練習(xí)2.若冒泡排序在某一遍加工過程中沒有數(shù)據(jù)交換,則說明數(shù)據(jù)已經(jīng)有序,優(yōu)化程序段如下:a=[58,36,23,97,77]n=len(a);i=1;flag=Truewhilei<=4andflag==True:

flag=Flaseforjinrange(4,i-1,-1):ifa[j]>a[j-1]:a[j],a[j-1]=a[j-1],a[j];flag=True

i+=1數(shù)組元素a[0]到a[4]的值依次為“58,36,23,97,77”,經(jīng)過該程序段“加工”后,變量i的值是___________。4四、冒泡排序優(yōu)化2——范圍優(yōu)化當某一遍加工過程中沒有數(shù)據(jù)交換,說明數(shù)據(jù)已經(jīng)有序,無需進一步加工。當某段數(shù)據(jù)某遍加工過程中未發(fā)生任何一次數(shù)據(jù)交換,說明該段數(shù)據(jù)已經(jīng)有序,無需進一步加工,只需處理其后數(shù)據(jù)即可。下次冒泡只需比較到最后記錄的位置,因為前段有序。四、冒泡排序優(yōu)化2——范圍優(yōu)化last=len(d)-1foriinrange(1,len(d)):

c=0

forjinrange(0,last):ifd[j]>d[j+1]:

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

last=jifc==0:break有如下Python程度段生成隨機數(shù)組a并將其中的元素從小到大排序:importrandoma=[0]*10;

i=0x=random.randint(1,100)whilei<10:ifxnotina:a[i]=x;i=i+1x=random.randint(1,100)i=0whilei<9:

k=I

;i=9forjinrange(9,k,-1):ifa[j]<a[j-1]:a[j],a[j-1]=a

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論