資源簡介

(共28張PPT)
5.3.1 數據排序（第一課時）
單擊此處添加副標題
思考1：什么是排序？
一、排序的概念
排序就是整理數據的序列，使其中元素按照某個值的遞增（或遞減）的次序重新排列的操作。
在排序的過程中，數據元素的值保持不變，但其在序列中的順序可能發生變化。
思考2：怎么排序？
二、數據的組織形式 （以Python語言環境為例）
待排序數據的存儲方式一般有兩種：
（1）以數組作為存儲結構
將數據依次存放在一組地址連續的存儲單元中，通過關鍵字之間的比較判斷，將數據移到合適的位置進行物理重排
（2）以鏈表作為存儲結構
對鏈表進行排序無須移動數據，比較判斷后，只修改指針即可。
待排序數據的存儲方式一般有兩種：
（1）以數組作為存儲結構
將數據依次存放在一組地址連續的存儲單元中，通過關鍵字之間的比較判斷，將數據移到合適的位置進行物理重排
（2）以鏈表作為存儲結構
對鏈表進行排序無須移動數據，比較判斷后，只修改指針即可。
二、數據的組織形式 （以Python語言環境為例）
思考3：數組的排序如何實現？
三、Python中的排序函數
1.內建函數sorted()：返回一個新序列，而原序列依然存在
2.列表自帶的sort方法：直接對列表排序，不產生新序列
以a=[23,20,13,18,14,11]為例
三、Python中的排序函數
>>>a.sort( )
>>>print(a)
>>>a.sort(reverse=True) #reverse=True實現降序排序
>>>print(a)
>>>b=sorted(a)
>>>print(b)
>>>print(a)
以a=[23,20,13,18,14,11]為例
[11,13,14,18,20,23]
[23,20,13,18,14,11]
[11,13,14,18,20,23]
[23,20,18,14,13,11]
知其然
知其所以然
1.內建函數sorted()：返回一個新序列，而原序列依然存在
2.列表自帶的sort方法：直接對列表排序，不產生新序列
四、常見的排序算法
思考4: 若請你設計一個實現排序
的算法，你會如何設計？
冒泡排序
出處：十大經典排序算法 https:///onepixel/articles/7674659.html
四、常見的排序算法
選擇排序
出處：十大經典排序算法 https:///onepixel/articles/7674659.html
四、常見的排序算法
插入排序
出處：十大經典排序算法 https:///onepixel/articles/7674659.html
四、常見的排序算法
冒泡排序、選擇排序、插入排序、快速排序、
堆排序、歸并排序、桶排序……
出處：十大經典排序算法 https:///onepixel/articles/7674659.html
五、冒泡排序算法及其程序實現
算法思想：在一系列數據中對相鄰兩個數依次進行比較和
調整，讓較大的數“下沉（或上冒）”，較小
的數“上冒（或下沉）”的一種排序方法。
前 后
前 后
前 后
前 后
五、冒泡排序算法及其程序實現
23
20
13
18
14
11
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
20
23
13
18
14
11
20
13
23
18
14
11
20
13
18
23
14
11
20
13
18
14
23
11
20
13
18
14
11
23
①
②
③
④
⑤
第一遍加工過程
若將n個元素的數組看成是垂直堆放的一列數據
（以從上往下比，將大數往下沉，實現升序排序為例）
五、冒泡排序算法及其程序實現
20
13
18
14
11
23
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
13
20
18
14
11
23
13
18
20
14
11
23
13
18
14
20
11
23
13
18
14
11
20
23
①
②
③
④
第二遍加工過程
若將n個元素的數組看成是垂直堆放的一列數據
（以從上往下比，將大數往下沉，實現升序排序為例）
……
五、冒泡排序算法及其程序實現
13
11
14
18
20
23
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
11
13
14
18
20
23
①
第五遍加工過程
若將n個元素的數組看成是垂直堆放的一列數據
（以從上往下比，將大數往下沉，實現升序排序為例）
若要排序的數有6個，
則需經過 遍加工
11
13
14
18
20
23
5
五、冒泡排序算法及其程序實現
思考5：
1.若要排序的數有n個，則需經過 遍加工
2.對n個元素的數組，用冒泡排序算法排序時，共需比較：
3.其時間復雜度為:
n-1
(n-1)+(n-2)+…+1=（次）
O(n2)
五、冒泡排序算法及其程序實現
排序過程中，按下面的方式使用變量i和j:
i:記錄正進行的處理遍數（ ）
j:記錄當前比較元素的下標( )
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
j
j+1
i=1
i=3
i=2
i=4
i=5
1 n-1
0 n-i-1
j
0
n-2
j
0
n-3
五、冒泡排序算法及其程序實現
開始
是
j＜n-i
i≤n-1
是
d[j]>d[j+1]
i i+1
否
交換d[j]和d[j+1]
否
是
輸出結果
結束
否
i 1
j 0
j j+1
流程圖：
五、冒泡排序算法及其程序實現
程序代碼實現：
def bubble_sort(a):
n=len(a)
#序列長度為n，需要執行n-1遍加工
for i in range(1, n):
for j in range( 0 , n-i ):
if a[j] > a[j+1]:
a[j],a[j+1]=a[j+1], a[j]
思考6：若要實現降序排序，如何修改代碼？
<
思考7：若從后往前加工，如何修改代碼？
無序區
有序區
無序區
有序區
課堂小結：
1.排序的概念
2.Python中的排序函數
3.常見的排序算法
4.冒泡排序的算法過程及代碼實現
評分項 自我評價
理解排序的基本概念 5 4 3 2 1
掌握Python中的排序函數 5 4 3 2 1
能夠了解常見的排序算法 5 4 3 2 1
初步掌握冒泡排序的算法過程及代碼實現 5 4 3 2 1
學習評價：
對自己的表現進行客觀的評價，并思考后續完善的
方向。（5=優秀，4=超出一般水平，3=滿意，2=有待
改進，1=不太理想）
同學們，再見！
單擊此處添加副標題

展開更多......

收起↑