文章目录
冒泡排序（Bubble Sort）选择排序（Selection Sort）插入排序（Insertion Sort）快速排序（Quick Sort）归并排序（Merge Sort）堆排序（Heap Sort）计数排序（Counting Sort）基数排序（Radix Sort）桶排序（Bucket Sort）希尔排序（Shell Sort）二分查找（Binary Search）线性查找（Linear Search）广度优先搜索（BFS）深度优先搜索（DFS）Dijkstra算法A*算法拓扑排序（Topological Sort）Kruskal算法Prim算法Floyd-Warshall算法贝尔曼-福特算法最大子数组和（Kadane's Algorithm）最长公共子序列（Longest Common Subsequence）编辑距离（Edit Distance）背包问题（Knapsack Problem）最长上升子序列（Longest Increasing Subsequence）汉诺塔问题（Tower of Hanoi）N皇后问题（N-Queens Problem）Rat in a Maze图的颜色问题（Graph Coloring Problem）约瑟夫斯问题（Josephus Problem）集合划分问题（Partition Problem）字符串匹配（KMP算法）
冒泡排序（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 = 10print(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 = 10print(linear_search(arr, x))广度优先搜索（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 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 sysdef 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 PriorityQueuedef 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 defaultdictdef 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 sysdef 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_indexdef 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 = 5parent = 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 = 5E = 8graph = [ [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 = 50n = 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 = 4tower_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 Truedef 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 Falsedef 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 = 4solve_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 Falsedef 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 Falsedef 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 Truedef 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] = 0def 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 = 3graph_coloring(graph, m)约瑟夫斯问题（Josephus Problem）
约瑟夫斯问题涉及找到最后一个幸存者的位置。
def josephus(n, k): if n == 1: return 0 else: return (josephus(n - 1, k) + k) % n# 示例n = 7k = 3print("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 += 1def 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)