python典型算法

### Python 中常见典型算法及其示例 #### 排序算法 快速排序是一种高效的排序方法，其核心思想是通过分治法来递归地将数组分为较小的部分并分别处理。以下是基于 Python 的快速排序实现： ```python 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) ``` 该函数利用列表推导式构建小于、等于和大于基准值的子列表，并最终返回拼接后的结果[^1]。 #### 查找算法 二分查找适用于有序数据集中的目标值定位操作。它通过对中间位置元素与目标值比较逐步缩小范围完成搜索过程。 ```python def binary_search(sorted_list, target): low, high = 0, len(sorted_list)-1 while low <= high: mid = (low + high) // 2 guess = sorted_list[mid] if guess == target: return mid elif guess > target: high = mid - 1 else: low = mid + 1 return None ``` 此代码片段展示了如何在一个已排序列表 `sorted_list` 上执行二分查找以找到指定的目标值 `target`。 #### 动态规划 斐波那契数列是一个经典的动态规划案例，其中每一项都由前两项之和定义。 ```python def fibonacci(n): fib_sequence = [0, 1] for i in range(2, n+1): next_val = fib_sequence[i-1] + fib_sequence[i-2] fib_sequence.append(next_val) return fib_sequence[n] ``` 上述程序计算第n个斐波那契数值的同时存储了整个序列以便后续可能的需求使用。 #### 贪婪算法 硬币找零问题是贪婪策略的一个应用实例，在这个问题里我们试图找出最少数量的钱币组合成给定金额。 ```python def coin_change(coins, amount): coins.sort(reverse=True) count = 0 for coin in coins: if amount >= coin: num_coins = amount // coin count += num_coins amount -= num_coins * coin if amount == 0: break return count if amount == 0 else -1 ``` 这里展示了一个简单的贪心算法解决不同面额货币兑换问题的方法。 #### 图遍历算法 广度优先搜索(BFS)用于探索图结构的所有节点，通常借助队列辅助实现逐层访问机制。 ```python from collections import deque def bfs(graph, start_node): visited = set() queue = deque([start_node]) while queue: node = queue.popleft() if node not in visited: visited.add(node) neighbors = graph[node] queue.extend(neighbors - visited) return visited ``` 这段脚本实现了BFS功能，能够从起始顶点出发按层次顺序依次访问连通区域内的其他结点。