开发者必须掌握的十个核心算法

本文将系统梳理开发者最常用的十大算法，并为每项算法配合生活/工业案例和Python代码示例进行说明。

1. “分而治之的排队”对应快速排序 (Quick Sort)

• 生活例子：体育老师安排学生排队时，先任意选出一名学生作为基准，让较矮者站在左侧、较高者站在右侧，再对左右两部分分别重复这一过程，直至所有人排列有序。
• 面试/工程关注点：平均时间复杂度 $O(n\log n)$。

def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)# 示例：[3, 6, 8, 10, 1, 2, 1] -> [1, 1, 2, 3, 6, 8, 10]

2. 二分查找 (Binary Search) —— “翻字典的艺术”

• 生活例子：在英语字典里找“Zebra”。你先翻到中间，发现是“M”，于是排除前半部分，在后半部分继续对折翻找。
• 前提：数组必须是有序的。

def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target: return midelif arr[mid] < target: low = mid + 1else: high = mid - 1return -1

3. 双指针 (Two Pointers) —— “相向而行的搜索”

• 生活例子：判断一串字母是不是回文（如“level”）。一个手指指开头，一个手指指结尾，同时向中间靠拢，对比字母是否一样。
• 应用：有效减少循环层数，将 $O(n^2)$ 降为 $O(n)$。

def is_palindrome(s):left, right = 0, len(s) - 1while left < right:if s[left] != s[right]: return Falseleft += 1right -= 1return True

4. 滑动窗口 (Sliding Window) —— “摄像机的平移”

• 生活例子：计算一周内连续3天的最高总气温。你拿一个3天的“窗口”，先算1-3号，然后向右滑一下，算2-4号，减去1号加上4号，效率极高。
• 应用：处理连续子数组、子串问题。

def max_sum_subarray(arr, k):n = len(arr)if n < k: return 0window_sum = sum(arr[:k])max_val = window_sumfor i in range(n - k):window_sum = window_sum - arr[i] + arr[i + k] # 滑动：减去左边，加上右边max_val = max(max_val, window_sum)return max_val

5. 广度优先搜索 (BFS) —— “水滴扩散”

• 生活例子：你向平静的湖面丢一颗石头。水波是一层一层向外扩散的。最先到达对岸的波纹就是“最短路径”。
• 应用：社交网络找“一度好友”、“二度好友”。

from collections import dequedef bfs(graph, start):visited = set([start])queue = deque([start])while queue:node = queue.popleft()print(node, end=" ")for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)# graph = {'A': ['B', 'C'], 'B': ['D'], ...}

6. 深度优先搜索 (DFS) —— “走迷宫”

• 生活例子：进迷宫后，遇到分岔口就选一条路走到底。直到撞墙了，才退回到上一个路口试另一条路。
• 应用：任务调度、寻找所有路径。

def dfs(graph, node, visited=None):if visited is None: visited = set()visited.add(node)print(node, end=" ")for neighbor in graph[node]:if neighbor not in visited:dfs(graph, neighbor, visited)

7. 迪杰斯特拉算法 (Dijkstra) —— “导航选路”

• 生活例子：导航系统在地图上找从A地到B地的耗时最短路径。它会优先考察离起点“成本最低”的邻近节点。
• 核心：使用优先队列维护最小成本。

import heapqdef dijkstra(graph, start):pq = [(0, start)] # (距离, 节点)distances = {node: float('inf') for node in graph}distances[start] = 0while pq:curr_dist, curr_node = heapq.heappop(pq)if curr_dist > distances[curr_node]: continuefor neighbor, weight in graph[curr_node].items():dist = curr_dist + weightif dist < distances[neighbor]:distances[neighbor] = distheapq.heappush(pq, (dist, neighbor))return distances

8. 动态规划 (Dynamic Programming) —— “记笔记求最优”

• 生活例子：爬楼梯问题。你想知道爬到第10级有多少种走法。你只要知道第9级和第8级的走法之和。为了不重复计算，你把1级、2级...的结果记在笔记本上。
• 本质：状态转移 + 结果缓存。

def climb_stairs(n):if n <= 2: return ndp = [0] * (n + 1)dp[1], dp[2] = 1, 2for i in range(3, n + 1):dp[i] = dp[i-1] + dp[i-2] # 状态转移return dp[n]

9. 贪心算法 (Greedy) —— “找零钱”

• 生活例子：收银员找零。如果要找67元，会先给50元的，再给10元的，再给5元的，最后给2个1元的。每次都选当前能选的最大面值。
• 注意：贪心不一定能得到全局最优解，但效率极高。

def coin_change_greedy(coins, amount):coins.sort(reverse=True) # 面值大的在前count = 0for coin in coins:count += amount // coinamount %= coinreturn count if amount == 0 else -1

10. 回溯算法 (Backtracking) —— “密码锁试错”

• 生活例子：你在解数独。在空格填一个3，发现后面填不下去了，赶紧擦掉，回来重新填一个4。这种“撤销重来”的过程就是回溯。
• 应用：求解所有组合、子集、棋盘问题。

def backtrack(path, choices):if not choices: # 满足条件print(path)returnfor i in range(len(choices)):# 做选择path.append(choices[i])# 递归backtrack(path, choices[:i] + choices[i+1:])# 撤销选择（这就是回溯的核心）path.pop()

最后的专业建议

学习算法时，不要死记代码，要记**“场景触发词”**：

1. 看到“有序、找值” -> 使用二分。
2. 看到“最短、层级” -> 使用BFS。
3. 回溯适用于“全部排列、所有可能”。
4. 滑动窗口对应“子数组、连续区间”。
5. 动态规划处理“最优、最大收益、重叠子问题”。