資源簡介

(共16張PPT)
第五章 數據結構與算法
選修一《數據與數據結構》
5.3.2 常見的排序算法——冒泡排序
排序就是整理數據的序列，使其中元素按照某個值遞增（或遞減）的次序重新排列的操作。
排序是什么？
太抽象了，無法理解
排序是什么？
18 9 14 12 7
18 9 14 12 7
按數組形式進行存儲
18
9
14
12
7
按鏈表形式進行存儲
7 9 12 14 18
對數組進行升序排序
Python中的排序實現
第一種：列表自帶的sort算法
列表自帶的sort方法，只適用于列表，直接對列表進行排序，不會產生新的序列。
第二種：內建函數sorted方法
內建函數sorted方法，返回一個新的序列，原來序列依然存在。
a=[5,7,6,3,4,1,2]
a.sort()
print(a) #[1,2,3,4,5,6,7]
a=[5,7,6,3,4,1,2]
a.sort( reverse=True )
print(a) #[7,6,5,4,3,2,1]
a=[5,7,6,3,4,1,2]
b=sorted(a)
print(a) #[5,7,6,3,4,1,2]
print(b) #[1,2,3,4,5,6,7]
常見的排序算法 — 冒泡排序
冒泡排序是在一系列數據中對相鄰兩個數依次進行比較和調整，讓較大的數“下沉（上冒）”，較小的數“上冒（下沉）”的一種排序技術。
18
9
14
12
7
p[0]
p[1]
p[2]
p[3]
p[4]
9
18
14
12
7
9
14
18
12
7
9
14
12
18
7
9
14
12
7
18
冒泡排序算法對數組p做的第1遍加工
常見的排序算法 — 冒泡排序
9
14
12
7
18
9
14
12
7
18
9
12
14
7
18
9
12
7
14
18
冒泡排序算法對數組p做的第2遍加工
冒泡排序算法對數組p做的第3遍加工
9
12
7
14
18
9
12
7
14
18
9
7
12
14
18
常見的排序算法 — 冒泡排序
9
7
12
14
18
7
9
12
14
18
冒泡排序算法對數組p做的第4遍加工
對長度為5的數組p，一共需要4次加工
對長度為n的數組p
① 一共需要(n-1)次加工
② 在第i遍加工當中，共需比較(n-i)次
③ 總共需要比較次
① 一共需要(n-1)次加工
常見的排序算法 — 冒泡排序
9
14
12
7
18
9
12
7
14
18
9
7
12
14
18
7
9
12
14
18
排好第1大的元素
排好第2大的元素
排好第4大的元素
排好第3大的元素
每一次加工，都是為了排好未排序數據當中最大的元素
常見的排序算法 — 冒泡排序
② 在第i遍加工當中，共需比較(n-i)次
n=5
i=1
n-i=4
排好元素：i-1=0個
共有n-(i-1)=5個元素需要比較
兩兩比較需要比較4次
常見的排序算法 — 冒泡排序
② 在第i遍加工當中，共需比較(n-i)次
n=5
i=2
n-i=3
排好元素：i-1=1個
共有n-(i-1)=4個元素需要比較
兩兩比較需要比較3次
常見的排序算法 — 冒泡排序
② 在第i遍加工當中，共需比較(n-i)次
n=5
i=3
n-i=2
排好元素：i-1=2個
共有n-(i-1)=3個元素需要比較
兩兩比較需要比較2次
n=5
i=4
n-i=1
排好元素：i-1=3個
共有n-(i-1)=2個元素需要比較
兩兩比較需要比較1次
如果說一共有n個元素，第i遍加工當中
共有(n-i+1)個元素需要比較
兩兩比較需要比較(n-i)次
常見的排序算法 — 冒泡排序
③ 總共需要比較次
第1遍加工：比較（n-1）次
第2遍加工：比較（n-2）次
…
第（n-2）遍加工：比較2次
第（n-1）遍加工：比較1次
① 一共需要(n-1)次加工
Q：一共需要幾次加工？
算法時間復雜度為
總共需要比較次數S
冒泡排序算法實現
自主閱讀課本第130頁，思考一共需要幾個變量？每個變量的作用是什么？
i：記錄當前正進行的處理遍數
j：記錄當前數組元素的下標。
每遍處理過程中，
j總是從第一個數據元素，下標為0開始。
按每次加1的方式
直至j+1=n-i => j=n-i-1為止
每次比較p[j]與p[j+1]進行比較，
若p[j]>p[j+1]，則進行互換
i=2
j=0
j+1
j=1
j+1
j=2
j+1
j=3
j+1
i=1
i=1
i=1
i=1
j=0
j+1
j=1
j+1
j=2
j+1
i=2
i=2
i=3
i=3
i=4
j=0
j+1
j=1
j+1
j=0
j+1
每遍處理過程中，
j總是從第一個數據元素，下標為0開始。
按每次加1的方式
直至j+1=n-i => j=n-i-1為止
每次比較p[j]與p[j+1]進行比較，
若p[j]>p[j+1]，則進行互換
冒泡排序算法實現
i：記錄當前正進行的處理遍數
j：記錄當前數組元素的下標。
① 一共需要(n-1)次加工
冒泡排序算法實現
Python代碼實現
def bubble_sort(p):
length = len(p)
for i in range(1, length):
for j in range(0, length-i):
if p[j]>p[j+1]:
temp = p[j]
p[j] = p[j+1]
p[j+1] = temp
return p
冒泡排序算法實現
課后作業：
課后了解選擇排序、插入排序、快速排序、堆排序、歸并排序、桶排序算法
并思考冒泡排序從大到小的Python實現方式

展開更多......

收起↑