冒泡排序（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算法
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*算法
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）
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算法
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算法
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算法
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）
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）
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）
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）
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）
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
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算法）
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)