十個(gè)經(jīng)典算法的 Python 實(shí)現(xiàn)
算法是編程世界的基石，對(duì)于Python初學(xué)者來(lái)說(shuō)，掌握一些經(jīng)典算法不僅能夠提升編程技能，還能幫助理解問(wèn)題解決的邏輯。下面，我們將一步步探索并用Python實(shí)現(xiàn)這些算法，從基礎(chǔ)到進(jìn)階，讓你的編程之旅更加精彩。
1. 二分查找
概念：在有序數(shù)組中查找目標(biāo)值，每次比較中間元素，縮小搜索范圍。
示例代碼：
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 # 如果沒(méi)找到返回-1
arr = [2, 3, 4, 10, 40]
target = 10
print("Element is present at index", binary_search(arr, target))解釋：通過(guò)不斷將搜索區(qū)間分為兩半，直到找到目標(biāo)或區(qū)間為空。
2. 冒泡排序
概念：重復(fù)遍歷要排序的數(shù)列，比較相鄰元素，如果順序錯(cuò)誤就交換它們。
示例代碼：
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. 快速排序
概念：選擇一個(gè)基準(zhǔn)值，通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序。
示例代碼：
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)解釋：遞歸地把小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素分開(kāi)。
4. 插入排序
概念：將未排序序列中的數(shù)據(jù)依次插入到已排序序列中的適當(dāng)位置。
示例代碼：
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)解釋：逐步構(gòu)建有序序列，適合小數(shù)據(jù)量排序。
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)解釋：每輪尋找最小值并移動(dòng)到序列前端。
6. 鏈表反轉(zhuǎn)
概念：將鏈表的指向反向，頭節(jié)點(diǎn)變成尾節(jié)點(diǎn)，尾節(jié)點(diǎn)變成頭節(jié)點(diǎn)。
示例代碼：
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
# 創(chuàng)建鏈表: 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解釋：通過(guò)改變節(jié)點(diǎn)的next指針來(lái)實(shí)現(xiàn)反轉(zhuǎn)。
7. 動(dòng)態(tài)規(guī)劃 - 最長(zhǎng)公共子序列
概念：找到兩個(gè)字符串中最長(zhǎng)的相同子序列。
示例代碼：
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))解釋：利用二維數(shù)組記錄子問(wèn)題的解，自底向上計(jì)算最長(zhǎng)公共子序列長(zhǎng)度。
8. 深度優(yōu)先搜索（DFS）
概念：訪問(wèn)圖或樹(shù)中的節(jié)點(diǎn)，盡可能深地搜索，訪問(wèn)完當(dāng)前節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)后回溯。
示例代碼（圖的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')解釋：遞歸地訪問(wèn)節(jié)點(diǎn)及其鄰居，用集合記錄已訪問(wèn)節(jié)點(diǎn)避免循環(huán)。
9. 廣度優(yōu)先搜索（BFS）
概念：從根節(jié)點(diǎn)開(kāi)始，訪問(wèn)最近的鄰接節(jié)點(diǎn)，然后訪問(wèn)下一層的節(jié)點(diǎn)。
示例代碼（圖的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')解釋：使用隊(duì)列保證按層次訪問(wèn)節(jié)點(diǎn)。
10. 斐波那契數(shù)列
概念：每一項(xiàng)都是前兩項(xiàng)之和，通常從0和1開(kāi)始。
示例代碼（遞歸與迭代）：
# 遞歸
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))解釋：遞歸直觀但效率低，迭代效率高且內(nèi)存占用少。
優(yōu)化與應(yīng)用場(chǎng)景
1. 二分查找的擴(kuò)展
應(yīng)用場(chǎng)景：適用于有序列表的快速查找，常見(jiàn)于數(shù)據(jù)庫(kù)索引、文件系統(tǒng)搜索等。
優(yōu)化：可以設(shè)計(jì)為迭代或遞歸形式，考慮邊界條件的優(yōu)化，如在鏈表中的實(shí)現(xiàn)需要額外的輔助結(jié)構(gòu)。
2. 排序算法的性能對(duì)比
快速排序通常在平均情況下最快，但在最壞情況下的時(shí)間復(fù)雜度為O(n^2)。
歸并排序雖然穩(wěn)定，但需要額外的存儲(chǔ)空間，時(shí)間復(fù)雜度始終為O(n log n)。
插入排序在小數(shù)據(jù)集或幾乎有序的數(shù)據(jù)集中表現(xiàn)良好，適合局部排序的優(yōu)化場(chǎng)景。
3. 動(dòng)態(tài)規(guī)劃與記憶化
LCS問(wèn)題展示了動(dòng)態(tài)規(guī)劃的核心思想，通過(guò)表格記錄子問(wèn)題的解來(lái)避免重復(fù)計(jì)算。
優(yōu)化：對(duì)于遞歸實(shí)現(xiàn)，可以通過(guò)緩存（記憶化）避免重復(fù)計(jì)算，減少時(shí)間復(fù)雜度。
4. 圖搜索算法的比較
DFS適用于尋找路徑、拓?fù)渑判?、連通性檢查。
BFS更適合尋找最短路徑問(wèn)題，如在無(wú)權(quán)圖中尋找兩節(jié)點(diǎn)間的最短路徑。
優(yōu)化：在大規(guī)模圖中，考慮使用并行處理或A*搜索等高級(jí)算法以提高效率。
5. 斐波那契數(shù)列的高效實(shí)現(xiàn)
矩陣快速冪：對(duì)于大數(shù)字的斐波那契數(shù)，可以利用數(shù)學(xué)中的矩陣乘法進(jìn)行指數(shù)級(jí)優(yōu)化。
空間優(yōu)化：迭代方法已經(jīng)很高效，但可以進(jìn)一步優(yōu)化，比如僅用兩個(gè)變量替換數(shù)組，節(jié)省內(nèi)存。
實(shí)戰(zhàn)案例分析
案例：旅行商問(wèn)題(TSP)的啟發(fā)式解決方案
旅行商問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，目標(biāo)是找到訪問(wèn)每個(gè)城市一次并返回起點(diǎn)的最短路徑。雖然這是一個(gè)NP難問(wèn)題，但可以使用啟發(fā)式算法如遺傳算法、模擬退火或貪心算法找到近似解。
示例代碼（簡(jiǎn)化版貪心算法）：
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
# 假設(shè)cities是一個(gè)二維列表，表示城市間的距離
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中可能不會(huì)得到最優(yōu)解，但它簡(jiǎn)單且快速，適合快速生成可行解，對(duì)于教學(xué)和理解啟發(fā)式算法非常有用。
