十個經典算法的 Python 實現
算法是編程世界的基石，對于Python初學者來說，掌握一些經典算法不僅能夠提升編程技能，還能幫助理解問題解決的邏輯。下面，我們將一步步探索并用Python實現這些算法，從基礎到進階，讓你的編程之旅更加精彩。
1. 二分查找
概念：在有序數組中查找目標值，每次比較中間元素，縮小搜索范圍。
示例代碼：
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # 如果沒找到返回-1
arr = [2, 3, 4, 10, 40]
target = 10
print("Element is present at index", binary_search(arr, target))解釋：通過不斷將搜索區間分為兩半，直到找到目標或區間為空。
2. 冒泡排序
概念：重復遍歷要排序的數列，比較相鄰元素，如果順序錯誤就交換它們。
示例代碼：
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)解釋：每一輪遍歷讓最大的元素“冒泡”到最后。
3. 快速排序
概念：選擇一個基準值，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄繼續進行排序。
示例代碼：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)解釋：遞歸地把小于基準值的元素和大于基準值的元素分開。
4. 插入排序
概念：將未排序序列中的數據依次插入到已排序序列中的適當位置。
示例代碼：
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array is:", sorted_arr)解釋：逐步構建有序序列，適合小數據量排序。
5. 選擇排序
概念：每次從未排序的序列中找到最小（大）的元素，存放到排序序列的起始（末尾）位置。
示例代碼：
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)解釋：每輪尋找最小值并移動到序列前端。
6. 鏈表反轉
概念：將鏈表的指向反向，頭節點變成尾節點，尾節點變成頭節點。
示例代碼：
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def reverse_list(head):
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
# 創建鏈表: 1->2->3
head = Node(1, Node(2, Node(3)))
reversed_head = reverse_list(head)
print("Reversed list:", end=" ")
while reversed_head:
print(reversed_head.data, end=" -> ")
reversed_head = reversed_head.next解釋：通過改變節點的next指針來實現反轉。
7. 動態規劃 - 最長公共子序列
概念：找到兩個字符串中最長的相同子序列。
示例代碼：
def lcs(X, Y):
m, n = len(X), len(Y)
L = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS is", lcs(X, Y))解釋：利用二維數組記錄子問題的解，自底向上計算最長公共子序列長度。
8. 深度優先搜索（DFS）
概念：訪問圖或樹中的節點，盡可能深地搜索，訪問完當前節點的所有鄰接節點后回溯。
示例代碼（圖的DFS）：
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbour in graph[node]:
if neighbour not in visited:
dfs(graph, neighbour, visited)
graph = {'0': ['1', '2'],
'1': ['0', '3', '4'],
'2': ['0'],
'3': ['1'],
'4': ['1']}
dfs(graph, '0')解釋：遞歸地訪問節點及其鄰居，用集合記錄已訪問節點避免循環。
9. 廣度優先搜索（BFS）
概念：從根節點開始，訪問最近的鄰接節點，然后訪問下一層的節點。
示例代碼（圖的BFS）：
from collections import deque
def bfs(graph, root):
visited = set()
queue = deque([root])
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
graph = {'0': ['1', '2'],
'1': ['0', '3', '4'],
'2': ['0'],
'3': ['1'],
'4': ['1']}
bfs(graph, '0')解釋：使用隊列保證按層次訪問節點。
10. 斐波那契數列
概念：每一項都是前兩項之和，通常從0和1開始。
示例代碼（遞歸與迭代）：
# 遞歸
def fib_recursive(n):
if n <= 1:
return n
else:
return (fib_recursive(n-1) + fib_recursive(n-2))
# 迭代
def fib_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a
print("Fibonacci at position 10 using recursion:", fib_recursive(10))
print("Fibonacci at position 10 using iteration:", fib_iterative(10))解釋：遞歸直觀但效率低，迭代效率高且內存占用少。
優化與應用場景
1. 二分查找的擴展
應用場景：適用于有序列表的快速查找，常見于數據庫索引、文件系統搜索等。
優化：可以設計為迭代或遞歸形式，考慮邊界條件的優化，如在鏈表中的實現需要額外的輔助結構。
2. 排序算法的性能對比
快速排序通常在平均情況下最快，但在最壞情況下的時間復雜度為O(n^2)。
歸并排序雖然穩定，但需要額外的存儲空間，時間復雜度始終為O(n log n)。
插入排序在小數據集或幾乎有序的數據集中表現良好，適合局部排序的優化場景。
3. 動態規劃與記憶化
LCS問題展示了動態規劃的核心思想，通過表格記錄子問題的解來避免重復計算。
優化：對于遞歸實現，可以通過緩存（記憶化）避免重復計算，減少時間復雜度。
4. 圖搜索算法的比較
DFS適用于尋找路徑、拓撲排序、連通性檢查。
BFS更適合尋找最短路徑問題，如在無權圖中尋找兩節點間的最短路徑。
優化：在大規模圖中，考慮使用并行處理或A*搜索等高級算法以提高效率。
5. 斐波那契數列的高效實現
矩陣快速冪：對于大數字的斐波那契數，可以利用數學中的矩陣乘法進行指數級優化。
空間優化：迭代方法已經很高效，但可以進一步優化，比如僅用兩個變量替換數組，節省內存。
實戰案例分析
案例：旅行商問題(TSP)的啟發式解決方案
旅行商問題是一個經典的組合優化問題，目標是找到訪問每個城市一次并返回起點的最短路徑。雖然這是一個NP難問題，但可以使用啟發式算法如遺傳算法、模擬退火或貪心算法找到近似解。
示例代碼（簡化版貪心算法）：
def tsp_greedy(cities, start=0):
unvisited = set(range(len(cities)))
path = [start]
total_distance = 0
while unvisited:
last_city = path[-1]
nearest_city = min(unvisited, key=lambda city: cities[last_city][city])
total_distance += cities[last_city][nearest_city]
path.append(nearest_city)
unvisited.remove(nearest_city)
# Return to start
total_distance += cities[path[-1]][start]
path.append(start)
return path, total_distance
# 假設cities是一個二維列表，表示城市間的距離
cities = [[0, 20, 15, 25], [20, 0, 30, 35], [15, 30, 0, 30], [25, 35, 30, 0]]
shortest_path, shortest_distance = tsp_greedy(cities)
print("Shortest Path:", shortest_path)
print("Distance:", shortest_distance)分析：雖然貪心算法在TSP中可能不會得到最優解，但它簡單且快速，適合快速生成可行解，對于教學和理解啟發式算法非常有用。
