PYTHON 常用算法 33个

冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一。它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，如果它们的顺序错误。

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

# 示例
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

选择排序（Selection Sort）

选择排序的工作原理是不断地从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 示例
print(selection_sort([64, 25, 12, 22, 11]))

插入排序（Insertion Sort）

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

# 示例
print(insertion_sort([12, 11, 13, 5, 6]))

快速排序（Quick Sort）

快速排序是一种分治算法，它选择一个基准元素，分区操作使得比基准元素小的元素放在左边，比基准元素大的元素放在右边，然后递归地对两边进行排序。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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)

# 示例
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))

归并排序（Merge Sort）

归并排序是一种分治算法，首先将数组分成两个小数组，分别进行排序，然后将排好序的子数组合并成一个有序的数组。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

# 示例
print(merge_sort([12, 11, 13, 5, 6, 7]))

堆排序（Heap Sort）

堆排序是一种基于堆数据结构的比较排序算法。

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

# 示例
print(heap_sort([12, 11, 13, 5, 6, 7]))

计数排序（Counting Sort）

计数排序适用于排序范围有限的整数数组。

def counting_sort(arr):
    max_val = max(arr)
    m = max_val + 1
    count = [0] * m
             
    for a in arr:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            arr[i] = a
            i += 1
    return arr

# 示例
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

基数排序（Radix Sort）

基数排序是一种非比较整数排序算法，通过按位分配和排序来处理数字。

def counting_sort_exp(arr, exp1):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(0, n):
        index = arr[i] // exp1
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp1
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(0, len(arr)):
        arr[i] = output[i]

def radix_sort(arr):
    max1 = max(arr)
    exp = 1
    while max1 // exp > 0:
        counting_sort_exp(arr, exp)
        exp *= 10
    return arr

# 示例
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

桶排序（Bucket Sort）

桶排序是另一种基于分布的排序算法，适用于均匀分布的数组。

def bucket_sort(arr):
    bucket = []

    for i in range(len(arr)):
        bucket.append([])

    for j in arr:
        index_b = int(10 * j)
        bucket[index_b].append(j)

    for i in range(len(arr)):
        bucket[i] = sorted(bucket[i])

    k = 0
    for i in range(len(arr)):
        for j in range(len(bucket[i])):
            arr[k] = bucket[i][j]
            k += 1
    return arr

# 示例
print(bucket_sort([0.897, 0.565, 0.656, 0.123, 0.665, 0.343]))

希尔排序（Shell Sort）

希尔排序是插入排序的一种更高效的改进版本，通过初始使用大间隔的插入排序来减少数据量。

def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

# 示例
print(shell_sort([12, 34, 54, 2, 3]))

二分查找（Binary Search）

二分查找用于在有序数组中查找元素，通过反复将搜索范围缩小一半来找到目标元素。

def binary_search(arr, x):
    l = 0
    r = len(arr) - 1

    while l <= r:
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
    return -1

# 示例
arr = [2, 3, 4, 10, 40]
x = 10
print(binary_search(arr, x))

线性查找（Linear Search）

线性查找是最简单的查找算法，通过遍历数组找到目标元素。

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# 示例
arr = [2, 3, 4, 10, 40]
x = 10
print(linear_search(arr, x))

广度优先搜索（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 neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

# 示例
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'C': ['G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}
bfs(graph, 'A')

深度优先搜索（DFS）

深度优先搜索用于遍历或搜索树或图的节点。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start, end=" ")

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

# 示例
graph = {
    'A': set(['B', 'C']),
    'B': set(['A', 'D', 'E']),
    'C': set(['A', 'F']),
    'D': set(['B']),
    'E': set(['B', 'F']),
    'F': set(['C', 'E'])
}
dfs(graph, 'A')

Dijkstra算法

Dijkstra算法用于查找加权图中从单个顶点到其他顶点的最短路径。

import sys

def dijkstra(graph, start):
    shortest_paths = {start: (None, 0)}
    current_node = start
    visited = set()

    while current_node is not None:
        visited.add(current_node)
        destinations = graph[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node, weight in destinations.items():
            weight = weight_to_current_node + weight
            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)

        next_destinations = {node: shortest_paths[node] for node in shortest_paths if node not in visited}
        if not next_destinations:
            return shortest_paths

        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])

# 示例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
start = 'A'
print(dijkstra(graph, start))

A*算法

A*算法用于在加权图中查找从起点到目标的最短路径。

from queue import PriorityQueue

def heuristic(a, b):
    return abs(b[0] - a[0]) + abs(b[1] - a[1])

def a_star(graph, start, goal):
    pq = PriorityQueue()
    pq.put((0, start))
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while not pq.empty():
        current = pq.get()[1]

        if current == goal:
            break

        for next in graph[current]:
            new_cost = cost_so_far[current] + graph[current][next]
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(goal, next)
                pq.put((priority, next))
                came_from[next] = current

    return came_from, cost_so_far

# 示例
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'C': 1, 'D': 6},
    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 4},
    'D': {'B': 6, 'C': 2, 'E': 1},
    'E': {'C': 4, 'D': 1}
}
start = 'A'
goal = 'E'
came_from, cost_so_far = a_star(graph, start, goal)
print(came_from)
print(cost_so_far)

拓扑排序（Topological Sort）

拓扑排序用于有向无环图（DAG）中的顶点排序。

from collections import defaultdict

def topological_sort_util(v, visited, stack, graph):
    visited[v] = True

    for i in graph[v]:
        if not visited[i]:
            topological_sort_util(i, visited, stack, graph)

    stack.insert(0, v)

def topological_sort(graph):
    visited = {i: False for i in graph}
    stack = []

    for i in graph:
        if not visited[i]:
            topological_sort_util(i, visited, stack, graph)

    return stack

# 示例
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
print(topological_sort(graph))

Kruskal算法

Kruskal算法用于查找加权无向图的最小生成树。

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal_mst(self):
        result = []
        i = 0
        e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 示例
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print(g.kruskal_mst())

Prim算法

Prim算法用于查找加权无向图的最小生成树。

import sys

def min_key(key, mst_set, V):
    min = sys.maxsize
    for v in range(V):
        if key[v] < min and mst_set[v] == False:
            min = key[v]
            min_index = v
    return min_index

def prim_mst(graph, V):
    key = [sys.maxsize] * V
    parent = [None] * V
    key[0] = 0
    mst_set = [False] * V
    parent[0] = -1

    for cout in range(V):
        u = min_key(key, mst_set, V)
        mst_set[u] = True

        for v in range(V):
            if graph[u][v] and mst_set[v] == False and key[v] > graph[u][v]:
                key[v] = graph[u][v]
                parent[v] = u

    return parent

# 示例
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
V = 5
parent = prim_mst(graph, V)
for i in range(1, V):
    print(parent[i], "-", i, "\t", graph[i][parent[i]])

Floyd-Warshall算法

Floyd-Warshall算法用于查找所有顶点对之间的最短路径。

INF = float('inf')

def floyd_warshall(graph):
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
    V = len(graph)

    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# 示例
graph = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
]
print(floyd_warshall(graph))

贝尔曼-福特算法

贝尔曼-福特算法用于查找带负权重的加权图中从单个顶点到其他顶点的最短路径。

def bellman_ford(graph, V, E, src):
    dist = [float("Inf")] * V
    dist[src] = 0

    for _ in range(V - 1):
        for u, v, w in graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in graph:
        if dist[u] != float("Inf") and dist[u] + w < dist[v]:
            print("Graph contains negative weight cycle")
            return

    return dist

# 示例
V = 5
E = 8
graph = [
    [0, 1, -1],
    [0, 2, 4],
    [1, 2, 3],
    [1, 3, 2],
    [1, 4, 2],
    [3, 2, 5],
    [3, 1, 1],
    [4, 3, -3]
]
print(bellman_ford(graph, V, E, 0))

最大子数组和（Kadane’s Algorithm）

Kadane’s算法用于查找具有最大和的连续子数组。

def kadane(arr):
    max_so_far = arr[0]
    max_ending_here = arr[0]

    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

# 示例
print(kadane([1, -3, 2, 1, -1]))

最长公共子序列（Longest Common Subsequence）

LCS用于查找两个字符串的最长公共子序列。

def lcs(X, Y):
    m = len(X)
    n = 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(lcs(X, Y))

编辑距离（Edit Distance）

编辑距离用于计算两个字符串之间转换的最少操作数。

def edit_distance(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[0 for x in range(n+1)] for x in range(m+1)]

    for i in range(m+1):
        for j in range(n+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])

    return dp[m][n]

# 示例
str1 = "sunday"
str2 = "saturday"
print(edit_distance(str1, str2))

背包问题（Knapsack Problem）

0/1背包问题用于在不超过背包容量的情况下选择物品以获得最大价值。

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x 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 wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    return K[n][W]

# 示例
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

最长上升子序列（Longest Increasing Subsequence）

LIS用于查找最长的严格上升子序列。

def lis(arr):
    n = len(arr)
    lis = [1]*n

    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j]+1

    maximum = 0
    for i in range(n):
        maximum = max(maximum, lis[i])

    return maximum

# 示例
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(lis(arr))

汉诺塔问题（Tower of Hanoi）

汉诺塔问题是经典的递归问题，涉及移动圆盘。

def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
    if n == 1:
        print("Move disk 1 from rod", from_rod, "to rod", to_rod)
        return
    tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
    print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
    tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)

# 示例
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')

N皇后问题（N-Queens Problem）

N皇后问题涉及在N x N的棋盘上放置N个皇后，使得它们彼此之间不会攻击。

def print_solution(board):
    for i in board:
        print(" ".join(str(x) for x in i))

def is_safe(board, row, col, n):
    for i in range(col):
        if board[row][i] == 1:
            return False

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    for i, j in zip(range(row, n, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True

def solve_nq_util(board, col, n):
    if col >= n:
        return True

    for i in range(n):
        if is_safe(board, i, col, n):
            board[i][col] = 1
            if solve_nq_util(board, col + 1, n):
                return True
            board[i][col] = 0
    return False

def solve_nq(n):
    board = [[0 for j in range(n)] for i in range(n)]

    if not solve_nq_util(board, 0, n):
        print("Solution does not exist")
        return False

    print_solution(board)
    return True

# 示例
n = 4
solve_nq(n)

Rat in a Maze

Rat in a Maze问题是经典的回溯问题，涉及找到迷宫的所有可能路径。

def is_safe(maze, x, y, n):
    if x >= 0 and x < n and y >= 0 and y < n and maze[x][y] == 1:
        return True
    return False

def solve_maze_util(maze, x, y, sol, n):
    if x == n - 1 and y == n - 1 and maze[x][y] == 1:
        sol[x][y] = 1
        return True

    if is_safe(maze, x, y, n):
        if sol[x][y] == 1:
            return False
        sol[x][y] = 1

        if solve_maze_util(maze, x + 1, y, sol, n):
            return True

        if solve_maze_util(maze, x, y + 1, sol, n):
            return True

        if solve_maze_util(maze, x - 1, y, sol, n):
            return True

        if solve_maze_util(maze, x, y - 1, sol, n):
            return True

        sol[x][y] = 0
        return False

def solve_maze(maze):
    n = len(maze)
    sol = [[0 for j in range(n)] for i in range(n)]

    if not solve_maze_util(maze, 0, 0, sol, n):
        print("Solution does not exist")
        return False

    print_solution(sol)
    return True

# 示例
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]
solve_maze(maze)

图的颜色问题（Graph Coloring Problem）

图的颜色问题涉及为图的顶点着色，使得相邻顶点不具有相同颜色。

def is_safe(v, graph, color, c):
    for i in range(len(graph)):
        if graph[v][i] == 1 and color[i] == c:
            return False
    return True

def graph_coloring_util(graph, m, color, v):
    if v == len(graph):
        return True

    for c in range(1, m + 1):
        if is_safe(v, graph, color, c):
            color[v] = c
            if graph_coloring_util(graph, m, color, v + 1):
                return True
            color[v] = 0

def graph_coloring(graph, m):
    color = [0] * len(graph)
    if not graph_coloring_util(graph, m, color, 0):
        print("Solution does not exist")
        return False

    print("Solution exists: ", color)
    return True

# 示例
graph = [
    [0, 1, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 0]
]
m = 3
graph_coloring(graph, m)

约瑟夫斯问题（Josephus Problem）

约瑟夫斯问题涉及找到最后一个幸存者的位置。

def josephus(n, k):
    if n == 1:
        return 0
    else:
        return (josephus(n - 1, k) + k) % n

# 示例
n = 7
k = 3
print("The chosen place is ", josephus(n, k))

集合划分问题（Partition Problem）

集合划分问题涉及将给定的集合划分为两个子集，使得它们的和相等。

def is_subset_sum(arr, n, sum):
    subset = [[False for i in range(sum + 1)] for i in range(n + 1)]

    for i in range(n + 1):
        subset[i][0] = True

    for i in range(1, sum + 1):
        subset[0][i] = False

    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if j < arr[i - 1]:
                subset[i][j] = subset[i - 1][j]
            if j >= arr[i - 1]:
                subset[i][j] = (subset[i - 1][j] or subset[i - 1][j - arr[i - 1]])

    return subset[n][sum]

def find_partition(arr, n):
    sum = 0
    for i in range(n):
        sum += arr[i]
    if sum % 2 != 0:
        return False

    return is_subset_sum(arr, n, sum // 2)

# 示例
arr = [3, 1, 5, 9, 12]
n = len(arr)
if find_partition(arr, n) == True:
    print("Can be divided into two subsets of equal sum")
else:
    print("Cannot be divided into two subsets of equal sum")

字符串匹配（KMP算法）

KMP算法用于在文本中查找给定的模式字符串。

def KMPSearch(pat, txt):
    M = len(pat)
    N = len(txt)

    lps = [0]*M
    j = 0

    computeLPSArray(pat, M, lps)

    i = 0
    while i < N:
        if pat[j] == txt[i]:
            i += 1
            j += 1

        if j == M:
            print("Found pattern at index " + str(i-j))
            j = lps[j-1]

        elif i < N and pat[j] != txt[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

def computeLPSArray(pat, M, lps):
    length = 0
    lps[0] = 0
    i = 1

    while i < M:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length-1]
            else:
                lps[i] = 0
                i += 1

# 示例
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)