程式語法熟練度是程式員的馬步功, 而演算法則是程式員的內功, 不學演算法只能算是花拳繡腿, 所以我打算有計畫地透過寫筆記徹底把 Python 演算法與資料結構基礎建立起來以備隨時查考.
演算法參考書籍如下 :
# 圖說演算法-使用 Python (博碩, 吳燦銘, 胡昭民)
# 動畫圖解資料結構使用Python (深石, 李春雄)
線上視頻教學參考 :
# Data Structures and Algorithms in JavaScript - Full Course for Beginners
# Data structures and algorithms with python
演算法第一課應該是寫程式最常用的排序吧! 本篇為排序中最好理解的的氣泡排序 (bubble sort), 此排序法目標是要將一個陣列的 n 個元素由小到大排列, 首先從陣列的第一個元素開始, 將其與相鄰的第二個元素比較大小, 若比第二個元素大就交換位置, 否則不做動作; 接著指標往下移到第二個元素, 繼續與下一個元素 (第三個) 相比.
如此這般依序往下比較, 當我們完成第一輪的 n-1 次比較時, 陣列中最大的元素必定會被移到陣列最後面. 但整個排序尚未完成, 我們還要將指標移回陣列之首再進行好幾輪同樣的比較, 但因為最大的元素已經在第一輪時被移到陣列尾端, 在第二輪比較時不需要再管它, 所以第二輪時只要比較前 n-1 個元素即可, 亦即要做 n-2 次比較, 完成第二輪比較時, 陣列中次大的元素必然被移到從陣列尾部倒數第二個元素.
這個程序每完成一輪, 下次掃描比較的個數就少一個, 直到需要被比較的元素只剩最前面那個時就可停止了, 那個元素必定是最小的, 因為這過程很像氣泡由水底往上升, 故稱為氣泡排序. n 個元素的陣列需經過 n-1 輪的掃瞄 (因為最後只剩第一個元素最小), 總共需要做 1+2+ ...+(n-1)=(n-1)*(1+n-1)/2=n*(n-1)/2 次比較, 整個演算法須使用兩層迴圈來做, 第一層為掃描之輪數, 第二層為每輪之比較次數, Python 程式碼如下 :
範例 1 : 氣泡排序 bubble_sort_1.py
#bubble_sort_1.py
arr=[99, 6, 7, 3, 78, 56, 72, 12]
print('陣列排序前 : ', arr)
n=0 #比較次數
for i in range(len(arr)-1, -1, -1): #掃描輪數=元素個數-1
for j in range(i): #掃描各輪內之元素
if arr[j] > arr[j+1]: #比大小
arr[j], arr[j+1]=arr[j+1], arr[j] #大於就互換位置
n += 1
print('第 %d 次排序結果 :' %(len(arr)-i), end='')
print(arr)
print('陣列排序後 : ', arr)
print('比較次數 : ', n)
執行結果 :
D:\test\python>python bubble_sort.py
陣列排序前 : [99, 6, 7, 3, 78, 56, 72, 12]
第 1 次排序結果 :[6, 7, 3, 78, 56, 72, 12, 99]
第 2 次排序結果 :[6, 3, 7, 56, 72, 12, 78, 99]
第 3 次排序結果 :[3, 6, 7, 56, 12, 72, 78, 99]
第 4 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 5 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 6 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 7 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
第 8 次排序結果 :[3, 6, 7, 12, 56, 72, 78, 99]
陣列排序後 : [3, 6, 7, 12, 56, 72, 78, 99]
比較次數 : 28
此陣列有 8 個元素, 故總比較次數 1+2+3+4+....+7=7*(1+7)/2=28 次.
如果串列元素是字串, 比大小時會以字元的 Unicode 編碼去比較, 將上面範例 1 改寫為函數, 然後傳入不同串列參數如下 :
範例 2 : 氣泡排序 bubble_sort_2.py
def bubble_sort(arr):
for i in range(len(arr)-1, -1, -1):
for j in range(i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1]=arr[j+1], arr[j]
print('第 %d 次排序結果 :' %(len(arr)-i), end='')
print(arr)
return arr
arr=['f', 'e', 'd', 'c', 'b', 'a']
print('陣列排序前 : ', arr)
bubble_sort(arr)
print('陣列排序後 : ', arr)
arr=['我', '愛', '你']
print('陣列排序前 : ', arr)
bubble_sort(arr)
print('陣列排序後 : ', arr)
執行結果如下 :
D:\test\python>python bubble_sort_3.py
陣列排序前 : ['f', 'e', 'd', 'c', 'b', 'a']
第 1 次排序結果 :['e', 'd', 'c', 'b', 'a', 'f']
第 2 次排序結果 :['d', 'c', 'b', 'a', 'e', 'f']
第 3 次排序結果 :['c', 'b', 'a', 'd', 'e', 'f']
第 4 次排序結果 :['b', 'a', 'c', 'd', 'e', 'f']
第 5 次排序結果 :['a', 'b', 'c', 'd', 'e', 'f']
第 6 次排序結果 :['a', 'b', 'c', 'd', 'e', 'f']
陣列排序後 : ['a', 'b', 'c', 'd', 'e', 'f']
陣列排序前 : ['我', '愛', '你']
第 1 次排序結果 :['愛', '你', '我']
第 2 次排序結果 :['你', '愛', '我']
第 3 次排序結果 :['你', '愛', '我']
陣列排序後 : ['你', '愛', '我']
["我", "愛", "你"] 的 unicode 分別為 ['\u6211', '\u611b', '\u4f60'], '你' 的 unicode 值最小, '我' 最大, 因此排序後變成 ['你', '愛', '我'].
參考 :
# About Python's built in sort() method
# Python List 的 sort 與 sorted 排序用法教學與範例
# https://www.ifreesite.com/unicode-ascii-ansi.htm
沒有留言 :
張貼留言