什麼是算法？
算法（Algorithm）：一個計算過程，解決問題的方法。
輸入→算法→輸出
時間複雜度
時間複雜度：用來評估算法運作效率的一個東西。
print('Hello World') #假如說這行代碼運作時間是一個機關O(1) for i in range(n): # 這段代碼的時間是O(n),因為執行了n次
print('Hello World') for i in range(n): # 這段代碼是O(n*n),因為在執行了n*n次
for j in range(n):
print('Hello World') for i in range(n): #這代碼是O(n*n*n),執行了n的立方次
for j in range(n):
for k in range(n):
print('Hello World') 小結：
時間複雜度是用來估計算法運作時間的一個式子（機關）。
一般來說，時間複雜度高的算法比複雜度低的算法慢。
常見的時間複雜度（按效率排序）：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
不常見的時間複雜度（看看就好）
O(n!) O(2n) O(nn) … 空間複雜度
空間複雜度：用來評估算法記憶體占用大小的一個式子
空間換時間：分給它一些空間或記憶體，讓它運作速度更快
遞歸
遞歸的兩個特點：
1.調用自身
2.有結束條件
def func(x):
if x>0:
print(x)
func(x-1)
print(4)
# 列印結果 4 3 2 1
#因為先列印再遞歸 def func(x):
if x > 0:
func(x-1)
print(x)
func(4)
# 列印結果 1 2 3 4
# 因為先遞歸，再列印 列印 抱着抱着抱着抱着抱着我的小鯉魚的我的我的我的我的我
def test(n):
if n == 0:
print("我的小鯉魚", end='')
else:
print("抱着", end='')
test(n-1)
print("的我", end='')
test(5)
# 尾遞歸 漢諾塔問題
t = 0
def hanoi(n, A, B, C):
global t
if n > 0:
hanoi(n-1, A, C, B)
t += 1
print("%s -> %s" % (A, C))
hanoi(n-1, B, A, C)
# hanoi(8,'A','B','C') # 8表示8層 A B C 參數不能變
# print(t) 清單查找
清單查找：從清單中查找指定元素
輸入：清單、待查找元素
輸出：元素下标或未查找到元素
順序查找
順序查找：從清單第一個元素開始，順序進行搜尋，直到找到為止。
二分查找：從有序清單的候選區data[0:n]開始，通過對待查找的值與候選區中間值的比較，可以使候選區減少一半。
有序清單，清單的元素值随着索引值的增加而增加：
簡單版二分查找
def bin_search(li, val): # li是傳入的清單 val是要查找的值
low = 0 # low是起始的索引值
high = len(li) - 1 # high是末尾的索引值
while low <= high: # 滿足起始索引小于末尾索引的條件就執行循環
mid = (low + high) // 2 # mid是清單的中間數的索引
if li[mid] == val: # 正好找到要查找的值的索引
return mid
elif li[mid] < val: # 中間數的值小于被查找的值
low = mid + 1 # 說明val在中間數的右邊
else:
high = mid - 1 # 說明val在中間數的左邊 遞歸版的二分查找 這是尾遞歸
def bin_search_rec(data_set, value, low, high):
if low <= high:
mid = (low + high) // 2
if data_set[mid] == value:
return mid
elif data_set[mid] > value:
return bin_search_rec(data_set, value, low, mid - 1)
else:
return bin_search_rec(data_set, value, mid + 1, high)
else:
return 清單排序
清單排序：将無序清單變成有序清單
輸入：無序清單
輸出：有序清單
順序：升序與倒序
排序low B 三人組;
冒泡排序 其次最多 O(n*n)
選擇排序 O(n*n)
插入排序
排序niu B 三人組：
快速排序 用得最多
堆排序 最難的
歸并排序
冒泡排序
冒泡排序：兩層周遊，相鄰的兩個值，如果左邊的數大于右邊的數，則交換位置。
li = [1, 2, 1, 3, 1, 4, 5, 4, 6, 7, 6, 8, 4, 5, 3, 2]
def bubble_sort(li):
for i in range(len(li)-1, 0, -1):
for k in range(i):
if li[k] > li[k+1]:
li[k], li[k+1] = li[k+1], li[k]
return li
print(bubble_sort(li)) 選擇排序
選擇排序：周遊一趟記錄最小的數，放到第一位。再周遊剩下的數，找的最小的數，繼續放置。
關鍵點：無序區和最小數的位置。
li = [1, 2, 1, 3, 1, 4, 5, 4, 6, 7, 6, 8, 4, 5, 3, 2]
def select_sort(li):
for i in range(len(li) - 1): # 總趟數可以是len(li)次，也可以是len(li)-1次，因為倒數第二趟結束的時候，清單已經排序完成。
# i表示趟數，也表示無序區的第一個數
min_loc = i #
for j in range(i+1, len(li)):
if li[j] < li[min_loc]: # 每趟都把最小的數放到無序區第一個位置
min_loc = j
li[min_loc], li[i] = li[i], li[min_loc] # 有序區會多一個數，無序區會少一個數。接下來下一趟開始
return li
print(select_sort(li)) 插入排序：
清單被分為有序區和無序區兩個部分。最初有序區隻有一個元素。
每次從無序區選擇一個元素，插入到有序區的位置，直到無序區變空。
代碼關鍵點：如何找到無序區數，如何插到有序區中。
li = [1, 2, 1, 3, 1, 4, 5, 4, 6, 7, 6, 8, 4, 5, 3, 2]
def insert_sort(li):
for i in range(1,len(li)): # 無序區的範圍，第一次無序區隻有清單的第一個數，是以無序區範圍就是range(1,len(li))
# i表示摸到的牌的位置
tem = li[i]
j = i - 1 # j表示有序區的最後面的一個數，j也表示有序區用來和i進小紅比較的數
# 如果有序區的這個用來比較的值比tem大，則用索引為j-1的值繼續比較.
# 如果tem這個值比有序區的所有數都小，這是索引是-1，表示找到位置，并退出while循環并插入
while j >= 0 and li[j] > tem:
li[j+1], li[j] = li[j], li[j+1] # 把tem的值往j的位置移
j -= 1 # 往前看
# 如果有序區的數比tem小，表示找到位置，就插入
li[j+1] = tem
return li
print(insert_sort(li)) 插入排序優化：應用二分查找來尋找插入點（并沒有什麼卵用）
快速排序
快速排序：取一個元素p（第一個元素），使元素p歸位，清單被p元素分為兩部分，左邊都比p小，右邊都比p大，然後遞歸完成排序。
li = [1, 2, 1, 3, 1, 4, 5, 4, 6, 7, 6, 8, 4, 5, 3, 2]
def partition(li, left, right):
tem = li[left] # 第一次取第一個元素left = 0
while left < right: # 清單裡至少兩個元素才滿足這個條件
while left < right and li[right] >= tem: # 從右邊邊找小于tem的數
right -= 1 # 如果不小于，繼續找
li[left], li[right] = li[right], li[left] # 找到比tem小的數，挪到左邊
while left < right and li[left] <= tem: # 從左邊找比tem大的數
left += 1
li[right], li[left] = li[left], li[right]
li[left] = tem
return left # 這裡傳回left和right是一樣的
def quick_sort(li, left, right):
if left < right: # 清單裡至少兩個元素才滿足這個條件
mid = partition(li, left, right)
quick_sort(li, left, mid-1) # 遞歸
quick_sort(li, mid+1, right) # 遞歸
return 111
quick_sort(li, 0, len(li)-1)
print(li) 快排的最壞情況：清單是倒序的[9,8,7,6,5,4,3,2,1,0]
堆排序
樹是一種資料結構 比如：目錄結構
樹是一種可以遞歸定義的資料結構
樹是由n個節點組成的集合：
如果n=0，那這是一棵空樹；
如果n>0，那存在1個節點作為樹的根節點，其他節點可以分為m個集合，每個集合本身又是一棵樹。
一些概念
根節點：沒有父節點的是根節點
葉子節點：沒有子節點的是葉子節點
樹的深度（高度）：幾層就是幾
樹的度：就是他有幾個節點(A有6個節點，度就是6。j的是2。f的是3。整個樹的度，就是最大的度。)
孩子節點/父節點：A是B的父節點，B是A的孩子節點
子樹：任何一個節點和它的孩子節點就是一個子樹，沒有孩子節點他也是一個樹。
二叉樹：度不超過2的樹（節點最多有兩個叉）
B是A的左孩子，C是A的右孩子
滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。
完全二叉樹：葉節點隻能出現在最下層和次下層，并且最下面一層的結點都集中在該層最左邊的若幹位置的二叉樹。
二叉樹的存儲方式
鍊式存儲方式
順序存儲方式（清單）
大根堆：一棵完全二叉樹，滿足任一節點都比其孩子節點大
小根堆：一棵完全二叉樹，滿足任一節點都比其孩子節點小
堆未完待續。。。。。。
歸并排序
假設現在的清單分兩段有序，如何将其合成為一個有序清單
分别從兩個有序的片段取值，按從小到大的順序取值。先比較兩個片段的最小值，誰小就取出來。
是以順序是1-2-3-4-5-6，将6取出來後，右邊的片段沒值了，就将左邊剩下的片段一次性取出來7-8-9。
然後就組合成一個新的有序清單了。
這種操作稱為一次歸并
def merge(li, low, mid, high): # high是右邊片段最後一個數的索引
li_tem = []
i = low # low是左邊片段第一個數的索引
j = mid + 1 # mid是左邊片段最大的數的索引
while i <= mid and j <= high: # 如果左右兩個片段都有值，就繼續取值。隻要其中一個片段沒值，就跳出循環。
if li[i] < li[j]: # 如果左邊片段的最小值小于右邊的最小值
li_tem.append(li[i]) # 就将最小的那個值取出來放到一個清單中。
i += 1 # 然後繼續比較剩下的最小值
else: # 反之，就是右邊的最小值小于左邊的最小值
li_tem.append(li[j])
j += 1 # 然後繼續比較剩下的最小值
# 跳出第一個while循環的條件是：如果左邊的片段取完了，其索引i不小于mid了
# 如果右邊的片段取完了，其索引j就不小于high了
# 下面的兩個while循環隻可能有一個執行
while i <= mid: # 這裡是左偏片段還有值
li_tem.append(li[i])
i += 1 # 繼續添加到清單中
while j <= high: # 這裡是右邊片段還有值
li_tem.append(li[j])
j += 1 # 繼續添加到清單中
li[low:high+1] = li_tem # 将li_tem copy給li
li = [2, 5, 7, 8, 9, 1, 3, 4, 6]
merge(li, 0, 4, len(li)-1)
print(li) 如果不是兩端有序清單怎麼用歸并，加上遞歸就可以了。
先把清單分解，然後合并。下半段的每一步操作都是一個歸并。
歸并排序
def merge(li, low, mid, high): # high是右邊片段最後一個數的索引
li_tem = []
i = low # low是左邊片段第一個數的索引
j = mid + 1 # mid是左邊片段最大的數的索引
while i <= mid and j <= high: # 如果左右兩個片段都有值，就繼續取值。隻要其中一個片段沒值，就跳出循環。
if li[i] < li[j]: # 如果左邊片段的最小值小于右邊的最小值
li_tem.append(li[i]) # 就将最小的那個值取出來放到一個清單中。
i += 1 # 然後繼續比較剩下的最小值
else: # 反之，就是右邊的最小值小于左邊的最小值
li_tem.append(li[j])
j += 1 # 然後繼續比較剩下的最小值
# 跳出第一個while循環的條件是：如果左邊的片段取完了，其索引i不小于mid了
# 如果右邊的片段取完了，其索引j就不小于high了
# 下面的兩個while循環隻可能有一個執行
while i <= mid: # 這裡是左偏片段還有值
li_tem.append(li[i])
i += 1 # 繼續添加到清單中
while j <= high: # 這裡是右邊片段還有值
li_tem.append(li[j])
j += 1 # 繼續添加到清單中
li[low:high+1] = li_tem
def merge_sort(li, low, high):
if low < high: # 保證清單至少有兩個元素
mid = (low + high) // 2 # 取中間數的索引
merge_sort(li, low, mid) # 将左邊的通過遞歸程式設計有序清單
merge_sort(li, mid+1, high) # 将右邊的通過遞歸程式設計有序清單
merge(li, low, mid, high) # 将左右兩個片段合并成一個有序清單
li = [2, 5, 7, 8, 9, 1, 3, 4, 6, 10]
merge_sort(li, 0, len(li)-1)
print(li) niu B 三人組總結
三種排序算法的時間複雜度都是O(nlogn)
一般情況下，就運作時間而言：
快速排序<歸并排序<堆排序
三種排序算法的缺點：
快速排序：極端情況下，排序效率低
歸并排序：需要額外的記憶體開銷
堆排序：在快的排序算法中相對較慢
希爾排序 待續。。。。。。
計數排序 待續。。。。。。