Python 所有算法汇总：从基础到高级的完整指南
摘要
本文系统性地汇总了 Python 中常用的算法，涵盖数据结构、排序、搜索、图论、动态规划、字符串处理、数学算法等多个领域。每个算法都配有核心思想、Python 实现代码和应用场景说明，旨在为开发者提供一个全面的算法参考手册。
1. 数据结构基础算法
1.1 数组与列表操作
最大子数组和（Kadane算法）
def max_subarray_sum(nums): max_current = max_global = nums[0] for i in range(1, len(nums)): max_current = max(nums[i], max_current + nums[i]) max_global = max(max_global, max_current) return max_global 示例 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] print(max_subarray_sum(nums)) # 输出: 6数组旋转
def rotate_array(nums, k): n = len(nums) k %= n nums[:] = nums[-k:] + nums[:-k] 示例 arr = [1, 2, 3, 4, 5, 6, 7] rotate_array(arr, 3) print(arr) # 输出: [5, 6, 7, 1, 2, 3, 4]1.2 链表算法
反转链表
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head): prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev检测链表环（Floyd判圈算法）
def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False1.3 栈与队列
括号匹配
def is_valid_parentheses(s): stack = [] mapping = {')': '(', ']': '[', '}': '{'} for char in s: if char in mapping.values(): stack.append(char) elif char in mapping: if not stack or stack[-1] != mapping[char]: return False stack.pop() return not stack 示例 print(is_valid_parentheses("()[]{}")) # True print(is_valid_parentheses("([)]")) # False2. 排序算法
2.1 比较排序
快速排序
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)归并排序
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result2.2 非比较排序
计数排序
def counting_sort(arr): if not arr: return [] max_val = max(arr) count = [0] * (max_val + 1) for num in arr: count[num] += 1 result = [] for i in range(len(count)): result.extend([i] * count[i]) return result3. 搜索算法
3.1 二分查找
def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -13.2 深度优先搜索（DFS）
def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start, end=' ') for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) 示例图 graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } dfs(graph, 'A') # 输出: A B D E F C3.3 广度优先搜索（BFS）
from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=' ') for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) bfs(graph, 'A') # 输出: A B C D E F4. 图论算法
4.1 最短路径
Dijkstra算法
import heapq def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 pq = [(0, start)] while pq: current_dist, current_node = heapq.heappop(pq) if current_dist > distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance = current_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(pq, (distance, neighbor)) return distances</code></pre> 4.2 最小生成树 Prim算法 def prim_mst(graph): import heapq mst = [] visited = set() start_node = list(graph.keys())[0] visited.add(start_node) edges = [(weight, start_node, to) for to, weight in graph[start_node].items()] heapq.heapify(edges) while edges: weight, frm, to = heapq.heappop(edges) if to not in visited: visited.add(to) mst.append((frm, to, weight)) for next_to, next_weight in graph[to].items(): if next_to not in visited: heapq.heappush(edges, (next_weight, to, next_to)) return mst</code></pre> 5. 动态规划 5.1 背包问题 0-1背包 def knapsack_01(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, capacity + 1): if weights[i-1] <= w: dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]]) else: dp[i][w] = dp[i-1][w] return dp[n][capacity]</code></pre> 5.2 最长公共子序列（LCS） def longest_common_subsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n]</code></pre> 6. 字符串算法 6.1 KMP模式匹配 def kmp_search(text, pattern): def build_lps(pattern): lps = [0] * len(pattern) length = 0 i = 1 while i < len(pattern): if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length-1] else: lps[i] = 0 i += 1 return lps lps = build_lps(pattern) i = j = 0 while i < len(text): if pattern[j] == text[i]: i += 1 j += 1 if j == len(pattern): return i - j elif i < len(text) and pattern[j] != text[i]: if j != 0: j = lps[j-1] else: i += 1 return -1</code></pre> 6.2 字符串编辑距离 def edit_distance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]</code></pre> 7. 数学算法 7.1 素数筛选 def sieve_of_eratosthenes(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False p = 2 while p * p <= n: if is_prime[p]: for i in range(p * p, n + 1, p): is_prime[i] = False p += 1 return [i for i in range(2, n + 1) if is_prime[i]] 7.2 最大公约数（欧几里得算法） def gcd(a, b): while b: a, b = b, a % b return a def lcm(a, b): return abs(a * b) // gcd(a, b) 8. 贪心算法 8.1 活动选择问题 def activity_selection(start, finish): activities = list(zip(start, finish)) activities.sort(key=lambda x: x[1]) selected = [activities[0]] last_finish = activities[0][1] for i in range(1, len(activities)): if activities[i][0] >= last_finish: selected.append(activities[i]) last_finish = activities[i][1] return selected</code></pre> 9. 回溯算法 9.1 N皇后问题 def solve_n_queens(n): def is_safe(board, row, col): for i in range(row): if board[i] == col or board[i] - i == col - row or board[i] + i == col + row: return False return True def backtrack(row, board, result): if row == n: result.append(board[:]) return for col in range(n): if is_safe(board, row, col): board[row] = col backtrack(row + 1, board, result) board[row] = -1 result = [] board = [-1] * n backtrack(0, board, result) return result</code></pre> 10. 分治算法 10.1 最近点对问题 import math def closest_pair(points): def distance(p1, p2): return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) def brute_force(points): min_dist = float('inf') pair = None n = len(points) for i in range(n): for j in range(i+1, n): dist = distance(points[i], points[j]) if dist < min_dist: min_dist = dist pair = (points[i], points[j]) return min_dist, pair def closest_split_pair(px, py, delta): mid_x = px[len(px)//2][0] sy = [p for p in py if mid_x - delta <= p[0] <= mid_x + delta] best = delta best_pair = None for i in range(len(sy)): for j in range(i+1, min(i+7, len(sy))): dist = distance(sy[i], sy[j]) if dist < best: best = dist best_pair = (sy[i], sy[j]) return best, best_pair def closest_pair_rec(px, py): if len(px) <= 3: return brute_force(px) mid = len(px) // 2 qx = px[:mid] rx = px[mid:] qy = [p for p in py if p[0] <= px[mid][0]] ry = [p for p in py if p[0] > px[mid][0]] d1, pair1 = closest_pair_rec(qx, qy) d2, pair2 = closest_pair_rec(rx, ry) delta = min(d1, d2) d3, pair3 = closest_split_pair(px, py, delta) if d3 < delta: return d3, pair3 elif d1 < d2: return d1, pair1 else: return d2, pair2 px = sorted(points, key=lambda p: p[0]) py = sorted(points, key=lambda p: p[1]) return closest_pair_rec(px, py)</code></pre> 总结 本文汇总了 Python 中常用的十大类算法，涵盖了从基础数据结构操作到高级图论和动态规划的完整知识体系。每个算法都提供了清晰的 Python 实现和简要说明，可以作为算法学习和面试准备的参考资料。在实际应用中，应根据具体问题选择合适的算法，并考虑时间复杂度和空间复杂度的平衡。