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 = nextdef reverse_list(head):prev = Nonecurrent = headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn 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 False

1.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("()[]{}"))  # Trueprint(is_valid_parentheses("([)]"))    # False

2. 排序算法

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 = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result

2.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 result

3. 搜索算法

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 -1

3.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 C

3.3 广度优先搜索（BFS）

 

from collections import dequedef 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 F

4. 图论算法

4.1 最短路径

Dijkstra算法

 

import heapqdef dijkstra(graph, start):distances = {node: float('inf') for node in graph}distances[start] = 0pq = [(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 lpslps = build_lps(pattern)i = j = 0while 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 += 1return -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] = ifor j in range(n + 1):    dp[0][j] = jfor 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] = Falsep = 2while p * p <= n:if is_prime[p]:for i in range(p * p, n + 1, p):is_prime[i] = Falsep += 1return [i for i in range(2, n + 1) if is_prime[i]]7.2 最大公约数（欧几里得算法）def gcd(a, b):while b:a, b = b, a % breturn adef 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 orboard[i] + i == col + row:return Falsereturn Truedef backtrack(row, board, result):if row == n:result.append(board[:])returnfor col in range(n):if is_safe(board, row, col):board[row] = colbacktrack(row + 1, board, result)board[row] = -1result = []board = [-1] * nbacktrack(0, board, result)return result</code></pre>10. 分治算法10.1 最近点对问题import mathdef 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 = Nonen = 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 = distpair = (points[i], points[j])return min_dist, pairdef 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 = deltabest_pair = Nonefor 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 = distbest_pair = (sy[i], sy[j])return best, best_pairdef closest_pair_rec(px, py):if len(px) <= 3:return brute_force(px)mid = len(px) // 2qx = 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, pair3elif d1 < d2:return d1, pair1else:return d2, pair2px = 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 实现和简要说明，可以作为算法学习和面试准备的参考资料。在实际应用中，应根据具体问题选择合适的算法，并考虑时间复杂度和空间复杂度的平衡。

以上就是“Python 所有算法汇总：从基础到高级的完整指南”的详细内容，想要了解更多Python教程欢迎持续关注编程学习网。