資源簡介

(共27張PPT)
5.3 數(shù) 據(jù) 排 序 (一)
——冒 泡 排 序
冊 別：選擇性必修1
學(xué) 科：高中信息技術(shù)(浙教版)
學(xué)習(xí)目標(biāo)：
能理解冒泡排序的算法思想。
能合理選用數(shù)據(jù)結(jié)構(gòu)，理清冒泡排序的范圍與條件。
能用自然語言、流程圖、Python語言描述冒泡排序算法。
能分析冒泡排序次數(shù)、比較次數(shù)和交換次數(shù)。
能掌握優(yōu)化冒泡排序方法。
想一想：
給下列5位同學(xué)從低到高排好隊(duì)
、
想一想：
給下列5位同學(xué)從低到高排好隊(duì)
、
排序概念：
、
排序：就是整理數(shù)據(jù)的序列，使其中元素按照某個值的遞增（或遞減）的次序重新排列的操作。
排序前：
排序后：
數(shù)組形式存儲
鏈表形式存儲
體驗(yàn)：Python中，對列表排序的方法
一、列表自帶的sort方法，只適用于列表，直接對列表進(jìn)行排序，不會產(chǎn)生新的序列
二、內(nèi)建函數(shù)sorted方法，返回一個新的序列，原來的序列依然存在
reverse=True降序
默認(rèn)： reverse=False升序
冒泡排序[遞增]的方法是
冒泡排序[Bubble Sort]
是在一系列數(shù)據(jù)中對相鄰兩個數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)“下沉”（“上冒”），較小的數(shù)“上冒”（“下沉”）的一種排序技術(shù)。
每一遍加工都是將本遍中最大的元素“下沉” 至本遍的底端位置
——從前往后，升序
每一遍加工都是將本遍中最小的元素像氣泡一樣“上浮” 至本遍的頂端位置
——從后往前，升序
冒泡排序：
第一遍（i=1)加工后，冒泡范圍j :[0,n-1]，最后一個元素d[4]最大
第二遍（i=2)加工后，冒泡范圍j :[0,n-2]，倒數(shù)第二個元素d[3]次大
第三遍（i=3)加工后，冒泡范圍j :[0,n-3]，倒數(shù)第三個元素位置固定
第四遍（i=4)加工后，冒泡范圍j :[0,n-4]，倒數(shù)第四個元素位置固定
對5(n)個元素?cái)?shù)組d從前往后冒泡升序排序
第一個與第二個元素
關(guān)注1：每趟（第i遍）相鄰（j與j+1位置)兩兩比較的起點(diǎn)
關(guān)注2：每趟（第i遍）相鄰（j與j+1位置)兩兩比較的終點(diǎn)
n-i
冒泡排序[遞增]的方法是
對于n個元素，第一遍加工將最大元素下沉到第n個位置
對于剩下的n-1元素，反復(fù)使用該規(guī)則，直到最后余下兩個元素進(jìn)行比較和交換
冒泡排序完成
冒泡排序標(biāo)準(zhǔn)程序的流程圖描述：
開始
i ← 1,L ← len(d)
i<=L-1
j=0
jd[j]>d[j+1]
j=j+1
輸出已排序數(shù)組d
結(jié)束
i=i+1
互換d[j]與d[j+1]
是
是
是
否
否
否
（1）
（2）
（3）
冒泡排序（遞增）
#參考教材P131
d=[12,5,23,6,2]
n=len(d)
#外循環(huán)i取1-n-1共n-1次處理
#內(nèi)循環(huán)從前往后冒：起點(diǎn)0與1位置上的元素，終點(diǎn)每次處理后往前縮進(jìn)1
#相鄰兩兩比較后，大數(shù)往后冒，兩數(shù)互換
for j in range(n-i):
for i in range(1，n):
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
print("排序后的列表",d)
用Python語言編寫程序并調(diào)試
d=[5,3,7,8,1,9,2,6]
n=len(d)
i=0
while ij=0
while :
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
j+=1
i+=1
print（“排序后的列表”,d）
#外循環(huán)i取0至n-2共n-1次加工
#大數(shù)往后冒，兩數(shù)互換
#內(nèi)循環(huán)每趟從第一個與第二個元素比較開始
#升序
填一填：
假如我們實(shí)現(xiàn)從前往后冒泡的升序排列，請問劃線處填什么？
jj+1
j
n-2-i n-1-i
填一填：
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(n-1):
for j in range(n-i-1):
if :
d[j],d[j+1]=d[j+1],d[j]
print( “排序后的列表”,d)
# 外循環(huán)i取0-n-2共n-1次加工
#小數(shù)往后冒，兩數(shù)互換
#內(nèi)循環(huán)從前往后冒
#降序
假如我們實(shí)現(xiàn)從前往后冒泡的降序排列，請問劃線處填什么？
d[j]冒泡排序（從后往前升序）：
d=[5,3,7,8,1,9,2,6]
n=len(d)
print("排序后的列表",d)
#小數(shù)往前冒，升序排列
#內(nèi)循環(huán)從后往前冒,每次都是從第n-1與n-2位置上元素比較開始,至第i個結(jié)束
if d[j]d[j],d[j-1]=d[j-1],d[j]
#外循環(huán)i取0-n-2共n-1次加工
for i in range(n-1):
for j in range(n-1,i,-1):
j
j-1
n-2 n-1
每一趟起點(diǎn)
j
j-1
0 1
第一趟i=0
j
j-1
1 2
第二趟i=1
用Python語言編寫程序并調(diào)試
d=[5,3,7,8,1,9,2,6]
print("排序前的列表：",d)
n=len(d)
i=0
while iwhile j>i-1:
if d[j]d[j],d[j+1]=d[j+1],d[j]
j-=1
i+=1
print（“排序后的列表:”,d）
#外循環(huán)i取0-n-2共n-1次加工
#大數(shù)往前冒，兩數(shù)互換
#內(nèi)循環(huán)從后往前冒
#降序
填一填：
j=n-2
假如我們實(shí)現(xiàn)從后往前冒泡的降序排列，請問劃線處填什么？
n-2 n-1
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(n-1):
for j in range（ ）:
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
print（“排序后的列表”,d）
#小數(shù)往前冒，兩數(shù)互換
#升序
填一填：
假如我們實(shí)現(xiàn)從后往前冒泡的升序排列，請問劃線處填什么？
#外循環(huán)i取0-n-2共n-1次加工
#內(nèi)循環(huán)從后往前冒
n-2,
n-2 n-1
i i+1
i-1,
-1
冒泡排序分析
比較次數(shù) (最多) 交換次數(shù) (最多) 執(zhí)行時間
(時間復(fù)雜度)
冒泡
以n個數(shù)據(jù)為例（在沒有優(yōu)化的情況下）
對n個元素的數(shù)組，用冒泡法進(jìn)行排序時，共需比較
次數(shù)：
O(n2)
(n-1)
+…+1=
+(n-2)
冒泡排序優(yōu)化的常用形式
1、外層優(yōu)化：減少排序趟數(shù)
2、內(nèi)層優(yōu)化：縮小內(nèi)層比較的范圍
3、雙向冒泡：一遍排序同時把最小最大的數(shù)排好
冒泡排序優(yōu)化算法1:外層優(yōu)化：排序遍數(shù)
算法思想：看有無交換，無交換代表數(shù)據(jù)已有序
程序?qū)崿F(xiàn)：設(shè)一個flag變量做標(biāo)記
d=[5,3,7,8,1,9,2,6]
print("原來列表",d)
n=len(d);i=0;c=0;flag=True #flag變量
while ifor j in range(n-i-1): #從前往后冒
c=c+1
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
flag=True #flag變量
i=i+1
print("排序后的列表",d)
print("從前往后冒泡排序趟數(shù)：",i,"，比較次數(shù)",c)
flag=False #flag變量
請問劃線處填什么？
優(yōu)化算法2：內(nèi)層優(yōu)化：縮小內(nèi)層比較的范圍
算法思想：
1、在每遍冒泡過程中，最后一次交換的是last與last-1位置的數(shù)，表明在last之前的相鄰數(shù)據(jù)已有序，進(jìn)行下一遍冒泡時無序區(qū)域設(shè)置為[last,n-1](從后往前為例)
2、在某一遍排序時沒有數(shù)據(jù)交換，說明待排序數(shù)據(jù)已有序，冒泡排序在此遍后結(jié)束
冒泡排序的優(yōu)化算法2(升序從后往前排序)
第1趟處理：
待排序區(qū)域是
[0,n-1]
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
1 2 5 6 12 9 11 10 16
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=8 1 2 5 6 12 9 11 10 16
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=7 1 2 5 6 12 9 10 11 16
st=7
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=6 1 2 5 6 12 9 10 11 16
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=5 1 2 5 6 9 12 10 11 16
st=5
j=4至j=1沒有數(shù)據(jù)交換
下一趟的排序區(qū)域
[st,n-1]
冒泡排序的優(yōu)化算法2
#算法思想：記下最后一次交換的是last與last-1位置的數(shù)，表明在last之前的相鄰數(shù)據(jù)已有序，進(jìn)行下一遍冒泡時無序區(qū)域設(shè)置為[last,n](從后往前為例)
a=[5,10,15,78,16,7,37,25]
;n=len(a);num=0 #num排序遍數(shù)
flag=True
while flag==True:
flag=False
for j in range(n-1,last,-1): #從后往前冒
if a[j]t=a[j];a[j]=a[j-1];a[j-1]=t
flag=True
num=num+1
if last==n-1: break
print（"排序后的數(shù)列為：",a）
print（"冒泡排序過程的加工遍數(shù)為：",num）
請問劃線處填什么？
last=j
last=0
j
j-1
st st+1
下一趟終點(diǎn)
冒泡排序的優(yōu)化算法3
雙向冒泡排序
1、首先從后往前利用冒泡排序算法，兩兩比較，將最小數(shù)放到第一個a[0]
2、然后從前往后利用冒泡排序算法，兩兩比較，將最大數(shù)放到最后一個a[n-1]
3、再對其余的n-2個數(shù)進(jìn)行上述1、2同樣的操作，其結(jié)果是將次小數(shù)放到a[1]，次大數(shù)放到a[n-2]
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
112 22 5 6 12 9 11 10 16
第1趟的排序區(qū)域[0,n-1]
第2趟的排序區(qū)域[1,n-2]
……
冒泡排序的優(yōu)化算法3
import random #雙向冒泡升序
n=10;a=[0]*n
for i in range(n): #隨機(jī)產(chǎn)生n個兩位數(shù)在列表a中顯示
a[i]=random.randint(10,99)
top =0;bottom =n-1 #雙向冒泡升序開始
print("原始列表:",a)
num=0 #num統(tǒng)計(jì)加工次數(shù)
while top < bottom: #外循環(huán)控制加工處理趟數(shù)
for j in range(bottom,top,-1): #從后從前利用冒泡算法，兩兩比較，將最小數(shù)放到第一個a[0]
if a[j] t = a[j];a[j] = a[j - 1];a[j - 1] = t
#頂端點(diǎn)縮進(jìn)一個
for j in range(top,bottom): #從前到后利用冒泡算法，兩兩比較，將最大數(shù)放到最后一個a[n-1]
if a[j] >a[j + 1]:
a[j],a[j+1] = a[j+1],a[j]
#底端縮進(jìn)一個
num+=1 #雙向冒泡升序1趟結(jié)束
print（排序后的數(shù)列為：",a)
print（冒泡排序過程的加工遍數(shù)為：",num)
請問劃線處填什么？
top + = 1
bottom - =1
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
112 22 5 6 12 9 11 10 16
第1趟的排序區(qū)域[0,n-1]
第2趟的排序區(qū)域[1,n-2]
……
課堂小結(jié)
冒泡排序
算法思想 算法描述
從前往后冒
優(yōu)化冒泡排序
程序?qū)崿F(xiàn)
從后往前冒
升序/降序
學(xué)習(xí)評價
對自己的表現(xiàn)進(jìn)行客觀的評價，并思考后續(xù)完善的方向。(3=優(yōu)秀，2=一般，1=仍需加油)
評分項(xiàng) 自我評價
會用sort與sorted函數(shù) 3 2 1
看交誼舞得出冒泡排序兩個特點(diǎn)：相鄰比較、起點(diǎn)相同 3 2 1
能自主學(xué)習(xí)教材并用自然語言、流程圖描述冒泡排序算法 3 2 1
能夠用Python語言描述冒泡排序算法 3 2 1
能獨(dú)立完成從前往后/從后往前/升/降冒泡排序的程序?qū)崿F(xiàn) 3 2 1
能總結(jié)出冒泡排序的比較/交換次數(shù)，優(yōu)化算法 3 2 1
1、程序運(yùn)行后的結(jié)果如下所示：
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(n-1):
for j in range(n-2, ):
if d[j]d[j],d[j+1]=d[j+1],d[j]
print("排序后的列表",d)
課后作業(yè)
參考答案：1、i-1,-1 2、d[j]給劃線處填上合適的語句
2、程序運(yùn)行后的結(jié)果如下所示：
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(1,n):
for j in range(n-1,i-1,-1):
if ：
d[j],d[j-1]=d[j-1],d[j]
print("排序后的列表",d)
3、程序運(yùn)行后的結(jié)果如下所示：
a=[8,10,15,78,16,27,39,21]
print("待排序數(shù)列為：",a)
n=len(a); ;num=0
flag=True
while flag==True:
flag=False
for j in range(1,last+1) :
if a[j]t=a[j];a[j]=a[j-1];a[j-1]=t
last=j-1
flag=True
num=num+1
if last==0: break
print("排序后的數(shù)列為：",a)
print("冒泡排序過程的加工遍數(shù)為：",num)
4、默寫從前往后升序冒泡排序程序，并上機(jī)調(diào)試。

展開更多......

收起↑