python中常用的算法

Python中常用的算法包括但不限于：排序算法、搜索算法、图算法、动态规划、数据结构操作等。以下是几个常见算法的简单示例：

1. 排序算法：

   • 冒泡排序
   • 插入排序
   • 选择排序
   • 快速排序
   • 合并排序
   • 堆排序

# 快速排序示例
def quicksort(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 quicksort(left) + middle + quicksort(right)
 
arr = [3,6,8,10,1,2,1]
print(quicksort(arr))  # 输出: [1, 1, 2, 3, 6, 8, 10]

2. 搜索算法：

   • 线性搜索
   • 二分搜索（前提是数组已排序）

# 二分搜索示例
def binary_search(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return True
        elif arr[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return False
 
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 6
print(binary_search(arr, x))  # 输出: True

3. 图算法：

   • 深度优先搜索（DFS）
   • 广度优先搜索（BFS）
   • Dijkstra算法（单源最短路径）
   • 最小生成树算法（Prim/Kruskal）

# 深度优先搜索示例（DFS）
from collections import deque
 
def dfs(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(set(graph[vertex]) - visited)
    return visited
 
# 使用DFS的图示例
graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}
 
print(dfs(graph, 'A'))  # 输出: {'A', 'C', 'B', 'E', 'F', 'D'}

4. 动态规划：

   • 0-1背包问题
   • 最长子序列问题

# 0-1背包问题示例
def knapsack(weight, value, n, W):
    K = [[0 for w in range(W+1)] for i in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif weight[i-1] <= w:
                K[i][w] = max(K[i-1][w], K[i-1][w-weight[i-1]] + value[i-1])
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
 
# 使用动态规划解决0-1背包问题的示例
weights = [2, 1, 3]
values = [4,