### Python 中常见的算法列表 Python 是一种功能强大且灵活的编程语言，广泛应用于算法设计与实现。以下是 Python 中常见的算法分类及其具体实现示例： #### 1. 排序算法 排序算法是计算机科学中最基础的一类算法，用于将数据按照特定顺序排列。 ##### (1) 冒泡排序 冒泡排序通过多次比较和交换来将最大的元素逐步移动到列表末尾。 ```python def bubble_sort(li): for i in range(len(li)-1): exchange = False for j in range(len(li)-1-i): if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] exchange = True if not exchange: return ``` 冒泡排序的时间复杂度为 \(O(n^2)\)[^4]。 ##### (2) 快速排序 快速排序是一种分治策略的排序算法，通过选择基准值将数组分为两部分并递归排序。 ```python def quick_sort(data, left, right): if left < right: mid = partition(data, left, right) quick_sort(data, left, mid-1) quick_sort(data, mid+1, right) def partition(li, left, right): tmp = li[left] while left < right: while left < right and li[right] >= tmp: right -= 1 li[left] = li[right] while left < right and li[left] <= tmp: left += 1 li[right] = li[left] li[left] = tmp return left ``` 快速排序的平均时间复杂度为 \(O(n \log n)\)[^5]。 ##### (3) 归并排序 归并排序也是一种分治算法，通过递归地将数组分成两半并合并已排序的部分。 ```python def merge_sort(li, low, high): if low < high: mid = (low + high) // 2 merge_sort(li, low, mid) merge_sort(li, mid+1, high) merge(li, low, mid, high) def merge(li, low, mid, high): i, j = low, mid+1 temp = [] while i <= mid and j <= high: if li[i] < li[j]: temp.append(li[i]) i += 1 else: temp.append(li[j]) j += 1 while i <= mid: temp.append(li[i]) i += 1 while j <= high: temp.append(li[j]) j += 1 li[low:high+1] = temp ``` 归并排序的时间复杂度为 \(O(n \log n)\)[^1]。 #### 2. 搜索算法 搜索算法用于在数据结构中查找特定目标。 ##### (1) 二分查找 二分查找适用于有序数组，通过不断缩小搜索范围来定位目标值。 ```python def binary_search(li, target): low, high = 0, len(li) - 1 while low <= high: mid = (low + high) // 2 if li[mid] == target: return mid elif li[mid] < target: low = mid + 1 else: high = mid - 1 return -1 ``` 二分查找的时间复杂度为 \(O(\log n)\)[^6]。 #### 3. 贪心算法 贪心算法通过在每个步骤中选择局部最优解来解决优化问题。 ```python def fractional_knapsack(value, weight, capacity): items = [(v / w, v, w) for v, w in zip(value, weight)] items.sort(reverse=True) total_value = 0.0 remaining_capacity = capacity for unit_value, v, w in items: if w <= remaining_capacity: total_value += v remaining_capacity -= w else: total_value += unit_value * remaining_capacity break return total_value ``` 贪心算法适用于分数背包问题等场景[^7]。 #### 4. 动态规划 动态规划通过将问题分解为子问题并存储中间结果来避免重复计算。 ```python def fibonacci(n): if n <= 1: return n dp = [0] * (n+1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] ``` 动态规划适用于斐波那契数列、最长公共子序列等问题[^8]。 #### 5. 图算法 图算法用于解决图结构中的路径、连通性等问题。 ##### (1) 广度优先搜索 (BFS) 广度优先搜索从起始节点开始逐层扩展，直到找到目标节点。 ```python from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: node = queue.popleft() print(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) ``` ##### (2) 深度优先搜索 (DFS) 深度优先搜索从起始节点开始深入探索，直到无法继续时回溯。 ```python def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) ``` #### 6. 字符串匹配算法 字符串匹配算法用于查找一个字符串是否包含另一个字符串。 ##### (1) KMP 算法 KMP 算法通过构建前缀表来避免不必要的回溯。 ```python def kmp(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 lps lps = build_lps(pattern) i = j = 0 while i < len(text): if text[i] == pattern[j]: i += 1 j += 1 if j == len(pattern): return i - j elif i < len(text) and text[i] != pattern[j]: if j != 0: j = lps[j-1] else: i += 1 return -1 ``` #### 7. 分治算法 分治算法通过将问题分解为更小的子问题来解决。 ##### (1) 最大子数组和 使用分治法求解最大子数组和。 ```python def max_subarray_divide_and_conquer(nums, left, right): if left == right: return nums[left] mid = (left + right) // 2 left_max = max_subarray_divide_and_conquer(nums, left, mid) right_max = max_subarray_divide_and_conquer(nums, mid+1, right) cross_max = max_crossing_sum(nums, left, mid, right) return max(left_max, right_max, cross_max) def max_crossing_sum(nums, left, mid, right): sum_left = float('-inf') current_sum = 0 for i in range(mid, left-1, -1): current_sum += nums[i] if current_sum > sum_left: sum_left = current_sum sum_right = float('-inf') current_sum = 0 for i in range(mid+1, right+1): current_sum += nums[i] if current_sum > sum_right: sum_right = current_sum return sum_left + sum_right ```