程序员必须掌握哪些算法？
文章目录
1. 引言
一个程序员一生中可能会邂逅各种各样的算法，但总有那么几种，是作为一个程序员一定会遇见且大概率需要掌握的算法。今天就来聊聊这些十分重要的"必抓！"算法吧~
作为程序员，了解和掌握各种算法对于解决各种计算机科学问题至关重要。以下是几个常见而重要的算法。
下表汇总了本文将要介绍的 7 个核心算法，涵盖所属类别、典型应用场景与复杂度信息，方便读者快速建立整体认知：
| 算法名称 | 所属类别 | 典型应用场景 | 平均时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | 排序 | 小规模数据排序、教学演示 | O(n²) | O(1) |
| 快速排序 | 排序 | 大规模数据排序、系统库排序函数 | O(n log n) | O(log n) |
| 二分搜索 | 搜索 | 有序数组中的快速查找 | O(log n) | O(1) |
| Dijkstra 算法 | 图 | 非负权图中的单源最短路径（如导航、路由） | O((V + E) log V) | O(V) |
| 0-1 背包问题 | 动态规划 | 资源分配、投资组合、装载优化 | O(n × capacity) | O(n × capacity) |
| 活动选择问题 | 贪心 | 会议室排期、任务调度 | O(n log n) | O(n) |
| KMP 算法 | 字符串匹配 | 文本检索、关键词匹配、DNA 序列比对 | O(n + m) | O(m) |
下面是本文 7 个核心算法的分类总览图，帮助读者快速建立整体认知：
2. 排序算法
排序算法用于将一组数据按照一定的顺序进行排列。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。
下表对比了常见排序算法的时间复杂度与空间复杂度：
| 排序算法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
下面是冒泡排序的算法流程示意图：
下面给出冒泡排序和快速排序的 Python 实现，并附上复杂度说明：
冒泡排序
def bubble_sort(arr):
"""
冒泡排序
时间复杂度：最好 O(n)，平均 O(n²)，最坏 O(n²)
空间复杂度：O(1)
"""
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 若本轮无交换，说明已有序，提前结束
if not swapped:
break
return arr
# 示例
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
快速排序
def quick_sort(arr):
"""
快速排序
时间复杂度：最好 O(n log n)，平均 O(n log n)，最坏 O(n²)
空间复杂度：O(log n)（递归调用栈）
"""
if len(arr) <= 1:
return arr
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([64, 34, 25, 12, 22, 11, 90]))
下面是快速排序的分治流程示意图：
3. 搜索算法
搜索算法用于在数据集中查找特定的元素或解决特定的问题。常见的搜索算法包括线性搜索、二分搜索、广度优先搜索、深度优先搜索等。
下面给出二分搜索的 Python 实现，并附上复杂度说明：
二分搜索
def binary_search(arr, target):
"""
二分搜索
适用条件：数组必须是有序的（升序或降序）
时间复杂度：O(log n)
空间复杂度：O(1)
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 未找到
# 示例（数组必须有序）
sorted_arr = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(sorted_arr, 25)) # 输出: 3
print(binary_search(sorted_arr, 100)) # 输出: -1
下面是二分搜索的查找流程示意图：
4. 图算法
图算法用于解决与图相关的问题，比如最短路径问题、最小生成树问题和网络流问题等。常见的图算法包括 Dijkstra 算法、Bellman-Ford 算法、Kruskal 算法、Prim 算法和 Floyd-Warshall 算法等。
下面给出 Dijkstra 算法的 Python 实现，使用邻接表表示图，并通过优先队列（最小堆）优化，附上复杂度说明：
Dijkstra 算法
import heapq
def dijkstra(graph, start):
"""
Dijkstra 最短路径算法（优先队列优化）
适用条件：图中边的权重必须为非负值
时间复杂度：O((V + E) log V)，其中 V 为顶点数，E 为边数
空间复杂度：O(V)
"""
# 初始化距离字典，起点距离为 0，其余顶点为无穷大
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 优先队列（最小堆），存储 (距离, 顶点)
pq = [(0, start)]
while pq:
current_dist, current = heapq.heappop(pq)
# 若当前距离大于已记录的最短距离，则跳过
if current_dist > distances[current]:
continue
# 遍历当前顶点的所有邻接顶点
for neighbor, weight in graph[current].items():
distance = current_dist + weight
# 若找到更短路径，则更新并加入优先队列
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# 示例：使用邻接表表示图
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}
}
# 运行示例：计算从 A 出发到各顶点的最短距离
print(dijkstra(graph, 'A'))
# 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
下面是 Dijkstra 算法的执行流程示意图：
5. 动态规划算法
动态规划算法用于解决具有重叠子问题性质的问题，在这种问题中，可以通过将其分解为较小的子问题来有效地解决。
常见的动态规划算法包括背包问题、最长公共子序列问题和最优矩阵链乘法等。
下面给出经典的 0-1 背包问题的 Python 实现，包含状态转移方程说明，并附上复杂度说明：
0-1 背包问题
def knapsack(weights, values, capacity):
"""
0-1 背包问题（动态规划）
状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])
其中 dp[i][j] 表示前 i 件物品在容量为 j 的背包中能获得的最大价值
时间复杂度：O(n * capacity)，其中 n 为物品数量
空间复杂度：O(n * capacity)，可优化为 O(capacity)
"""
n = len(weights)
# dp[i][j] 表示前 i 件物品放入容量为 j 的背包的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
# 放得下：取「不放」与「放」的较大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
else:
# 放不下：只能继承前 i-1 件物品的结果
dp[i][j] = dp[i - 1][j]
return dp[n][capacity]
# 示例：物品重量与价值
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
# 运行示例
print(knapsack(weights, values, capacity))
# 输出: 7（选择重量 2 和 3 的物品，价值 3 + 4 = 7）
6. 贪心算法
贪心算法通过在每个阶段都做出当前最优选择来解决问题。
尽管贪心算法通常无法获得全局最优解，但它们经常用于解决一些特定类型的问题，如活动选择问题和霍夫曼编码问题等。
下面给出经典的活动选择问题的 Python 实现，包含问题描述、算法思路与复杂度说明：
活动选择问题
def activity_selection(start, finish):
"""
活动选择问题（贪心算法）
问题描述：给定 n 个活动，每个活动 i 有开始时间 start[i] 和结束时间 finish[i]，
同一时间只能进行一个活动，求能参加的最多活动数量。
算法思路：按结束时间升序排序，每次选择结束最早且与已选活动不冲突的活动，
从而为后续活动留下尽可能多的时间。
时间复杂度：O(n log n)（排序），若已按结束时间排序则为 O(n)
空间复杂度：O(n)（存储所选活动）
"""
n = len(start)
# 按结束时间升序排序（若输入未排序）
activities = sorted(zip(start, finish), key=lambda x: x[1])
selected = [activities[0]] # 第一个活动必选
last_finish = activities[0][1]
for i in range(1, n):
# 若当前活动开始时间不早于上一个已选活动的结束时间，则选择
if activities[i][0] >= last_finish:
selected.append(activities[i])
last_finish = activities[i][1]
return selected
# 示例：活动编号 0~5，对应 (开始时间, 结束时间)
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
# 运行示例
result = activity_selection(start, finish)
print("选择的活动（开始, 结束）：", result)
print("最多可参加的活动数量：", len(result))
# 输出: 选择的活动（开始, 结束）： [(1, 2), (3, 4), (5, 7), (8, 9)]
# 最多可参加的活动数量： 4
7. 其他重要算法
此外，还有许多其他重要的算法，如字符串匹配算法（如 KMP 算法、Boyer-Moore 算法）、压缩算法（如哈夫曼压缩、LZW 压缩）、图像处理算法（如边缘检测算法、图像分割算法）等。
下面给出 KMP 字符串匹配算法的 Python 实现，包含 next 数组的构建过程与复杂度说明：
KMP 字符串匹配算法
def build_next(pattern):
"""
构建 next 数组（部分匹配表）
next[i] 表示 pattern[:i] 的最长相等前后缀长度
时间复杂度：O(m)，其中 m 为模式串长度
"""
m = len(pattern)
next_arr = [0] * m
j = 0 # 当前最长相等前后缀长度
for i in range(1, m):
# 若失配，则回退到上一个最长相等前后缀位置
while j > 0 and pattern[i] != pattern[j]:
j = next_arr[j - 1]
# 若匹配，则最长相等前后缀长度加 1
if pattern[i] == pattern[j]:
j += 1
next_arr[i] = j
return next_arr
def kmp_search(text, pattern):
"""
KMP 字符串匹配算法
算法思路：利用 next 数组在失配时跳过已匹配的前缀，避免回溯主串指针
时间复杂度：O(n + m)，其中 n 为主串长度，m 为模式串长度
空间复杂度：O(m)（存储 next 数组）
"""
n, m = len(text), len(pattern)
if m == 0:
return 0
next_arr = build_next(pattern)
j = 0 # 模式串指针
for i in range(n):
# 失配时，利用 next 数组回退模式串指针
while j > 0 and text[i] != pattern[j]:
j = next_arr[j - 1]
# 匹配成功，模式串指针前进
if text[i] == pattern[j]:
j += 1
# 完全匹配，返回主串中的起始下标
if j == m:
return i - m + 1
return -1 # 未找到
# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
# 运行示例
print("next 数组：", build_next(pattern))
print("匹配起始下标：", kmp_search(text, pattern))
# 输出: next 数组： [0, 0, 1, 2, 0, 1, 2, 3, 4]
# 匹配起始下标： 10
8. 算法对比与选型指南
面对不同的业务场景，选择合适的算法往往比实现算法本身更重要。下表汇总了本文 7 个核心算法的适用场景、优缺点与不适用场景，帮助读者快速做出决策：
| 算法名称 | 适用场景 | 优点 | 缺点 | 不适用场景 |
|---|---|---|---|---|
| 冒泡排序 | 小规模数据排序、教学演示 | 实现简单、稳定、原地排序 | 平均 O(n²) 效率低 | 大规模数据排序 |
| 快速排序 | 大规模数据排序、系统库排序函数 | 平均 O(n log n) 效率高、原地排序 | 最坏 O(n²)、不稳定、递归占用栈空间 | 数据基本有序或对稳定性有要求 |
| 二分搜索 | 有序数组中的快速查找 | O(log n) 极快、空间 O(1) | 要求数组必须有序 | 无序数组、频繁插入删除的动态数据集 |
| Dijkstra 算法 | 非负权图中的单源最短路径（导航、路由） | 可求出到所有顶点的最短路径、配合堆优化效率高 | 不能处理负权边 | 含负权边的图（应改用 Bellman-Ford） |
| 0-1 背包问题 | 资源分配、投资组合、装载优化 | 可求得精确最优解、思路通用 | O(n × capacity) 复杂度较高 | 物品可分割（应改用贪心）、容量极大时 |
| 活动选择问题 | 会议室排期、任务调度 | 思路简单、O(n log n) 高效 | 仅适用于满足贪心选择性质的问题 | 需要全局最优且不满足贪心性质的问题 |
| KMP 算法 | 文本检索、关键词匹配、DNA 序列比对 | O(n + m) 线性时间、主串指针不回溯 | 需额外 O(m) 空间构建 next 数组 | 模式串极短、单次匹配（朴素匹配即可） |
下面是一张算法选型流程图，根据问题类型与关键条件（数据规模、是否有序、是否含负权边）引导读者快速锁定合适的算法：
说明：流程图从「问题类型」出发，依次结合数据规模、是否有序、是否含负权边等关键条件进行分支判断，最终落到具体的算法选择；其中「组合优化问题」若满足贪心选择性质（如活动选择）可优先用贪心，否则用动态规划保证全局最优。
下面是一张平均时间复杂度对比柱状图，直观展示 7 个核心算法的复杂度差异（纵轴为相对耗时量级，数值越大表示耗时越高）：
说明：图中柱高表示各算法平均时间复杂度的相对量级（非精确数值）。其中二分搜索 O(log n) 最快，冒泡排序 O(n²) 最慢；快速排序与活动选择均为 O(n log n)，Dijkstra 为 O((V + E) log V)，KMP 为 O(n + m)，0-1 背包为 O(n × capacity)。需要注意的是，不同算法的输入规模含义不同（如 n、V、E、capacity、m），柱状图仅用于直观感受量级差异，实际选型还需结合具体问题规模与约束条件。
选型建议
- 数据量小时选冒泡排序：当数据规模很小（如几十个元素）且对稳定性有要求时，冒泡排序实现简单、代码直观，足够胜任。
- 大规模数据排序选快速排序：面对海量数据，快速排序平均 O(n log n) 的性能优势明显，是绝大多数系统库排序函数的默认选择。
- 有序数组用二分搜索：只要数据是有序且静态的，二分搜索 O(log n) 的查找效率远高于线性扫描，是查找场景的首选。
- 非负权图用 Dijkstra：在导航、路由等非负权图场景中，Dijkstra 配合优先队列能在 O((V + E) log V) 内求出单源最短路径；若图中存在负权边，则应改用 Bellman-Ford 算法。
- 组合优化问题用动态规划：当问题具有重叠子问题与最优子结构性质（如 0-1 背包）时，动态规划能保证求得全局最优解。
- 满足贪心性质的问题用贪心算法：活动选择这类满足贪心选择性质的问题，贪心算法能以最低的复杂度快速得到最优解。
- 字符串匹配用 KMP：在长文本中反复匹配模式串时，KMP 的 O(n + m) 线性复杂度能避免朴素匹配的回溯开销。
小结：选型时先判断问题类型（排序/搜索/图/优化/匹配），再结合数据规模、是否有序、是否含负权边等约束条件，即可快速锁定合适的算法。
9. 综合实战案例：城市交通调度系统
前面我们分别介绍了排序、搜索、图、动态规划、贪心和字符串匹配 6 大类共 7 个核心算法。但在真实业务中，这些算法往往不是孤立使用的，而是需要组合起来解决一个完整的问题。下面我们以「城市交通调度系统」为例，展示如何将本文的 7 个算法协同应用。
9.1 业务场景与算法映射
假设某城市需要调度一批出租车完成乘客的出行请求，系统需要依次解决以下子问题：
| 业务子问题 | 使用的算法 | 作用 |
|---|---|---|
| 按出发时间整理请求 | 快速排序 | 将请求按时间排序，便于后续处理 |
| 在有序请求中快速定位某条记录 | 二分搜索 | 快速查找指定时间段的请求 |
| 计算司机到乘客的最短路径 | Dijkstra 算法 | 在路网图中求最短行驶距离 |
| 为司机分配载客容量 | 0-1 背包问题 | 在车辆容量限制下选择最优载客组合 |
| 安排司机接单顺序 | 活动选择问题 | 在时间冲突下安排最多接单任务 |
| 校验乘客目的地名称 | KMP 算法 | 在地址库中快速匹配目的地关键词 |
9.2 完整 Python 实现
import heapq
# ---------- 1. 快速排序：按出发时间整理请求 ----------
def quick_sort(arr):
"""快速排序，按出发时间升序排列请求"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x[0] < pivot[0]]
middle = [x for x in arr if x[0] == pivot[0]]
right = [x for x in arr if x[0] > pivot[0]]
return quick_sort(left) + middle + quick_sort(right)
# ---------- 2. 二分搜索：在有序请求中定位某条记录 ----------
def binary_search(arr, target_time):
"""二分搜索，在按时间排序的请求中查找指定出发时间"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid][0] == target_time:
return mid
elif arr[mid][0] < target_time:
left = mid + 1
else:
right = mid - 1
return -1
# ---------- 3. Dijkstra 算法：计算司机到乘客的最短路径 ----------
def dijkstra(graph, start):
"""Dijkstra 最短路径算法（优先队列优化）"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_dist, current = heapq.heappop(pq)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# ---------- 4. 0-1 背包问题：在车辆容量限制下选择最优载客组合 ----------
def knapsack(weights, values, capacity):
"""0-1 背包问题（动态规划），选择价值最高的乘客组合"""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][capacity]
# ---------- 5. 活动选择问题：安排司机接单顺序 ----------
def activity_selection(start, finish):
"""活动选择问题（贪心算法），在时间冲突下安排最多接单任务"""
activities = sorted(zip(start, finish), key=lambda x: x[1])
selected = [activities[0]]
last_finish = activities[0][1]
for i in range(1, len(start)):
if activities[i][0] >= last_finish:
selected.append(activities[i])
last_finish = activities[i][1]
return selected
# ---------- 6. KMP 算法：校验乘客目的地名称 ----------
def build_next(pattern):
"""构建 next 数组（部分匹配表）"""
m = len(pattern)
next_arr = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = next_arr[j - 1]
if pattern[i] == pattern[j]:
j += 1
next_arr[i] = j
return next_arr
def kmp_search(text, pattern):
"""KMP 字符串匹配算法，在地址库中匹配目的地关键词"""
n, m = len(text), len(pattern)
if m == 0:
return 0
next_arr = build_next(pattern)
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = next_arr[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
return i - m + 1
return -1
# ---------- 主流程：城市交通调度系统 ----------
def traffic_dispatch_system():
print("=" * 50)
print("城市交通调度系统 - 综合实战")
print("=" * 50)
# 1. 原始请求列表：(出发时间, 目的地, 乘客人数, 预估收益)
raw_requests = [
(8, "中央车站", 2, 50),
(6, "机场", 3, 80),
(9, "科技园区", 1, 30),
(7, "市中心", 4, 100),
(5, "火车站", 2, 60),
]
# 2. 快速排序：按出发时间整理请求
sorted_requests = quick_sort(raw_requests)
print("\n[1] 快速排序 - 按出发时间整理请求：")
for req in sorted_requests:
print(f" 出发时间 {req[0]:>2} 点 -> {req[1]}（{req[2]} 人，预估收益 {req[3]} 元）")
# 3. 二分搜索：查找出发时间为 7 点的请求
target_time = 7
idx = binary_search(sorted_requests, target_time)
print(f"\n[2] 二分搜索 - 查找出发时间 {target_time} 点的请求：")
if idx != -1:
req = sorted_requests[idx]
print(f" 找到：{req[1]}（{req[2]} 人，预估收益 {req[3]} 元）")
else:
print(" 未找到该时间段的请求")
# 4. Dijkstra 算法：计算司机从「调度中心」到各乘客上车点的最短距离
road_graph = {
'调度中心': {'中央车站': 5, '机场': 12, '火车站': 8},
'中央车站': {'调度中心': 5, '市中心': 3, '科技园区': 6},
'机场': {'调度中心': 12, '火车站': 10},
'火车站': {'调度中心': 8, '机场': 10, '市中心': 4},
'市中心': {'中央车站': 3, '火车站': 4, '科技园区': 2},
'科技园区': {'中央车站': 6, '市中心': 2},
}
distances = dijkstra(road_graph, '调度中心')
print("\n[3] Dijkstra 算法 - 从调度中心到各上车点的最短距离：")
for dest, dist in distances.items():
if dest != '调度中心':
print(f" 到 {dest}：{dist} 公里")
# 5. 0-1 背包问题：车辆容量为 4 人，选择收益最高的乘客组合
passenger_counts = [req[2] for req in sorted_requests]
revenues = [req[3] for req in sorted_requests]
capacity = 4
max_revenue = knapsack(passenger_counts, revenues, capacity)
print(f"\n[4] 0-1 背包问题 - 车辆容量 {capacity} 人时的最大收益：")
print(f" 最大收益：{max_revenue} 元")
# 6. 活动选择问题：安排司机在时间冲突下接单
start_times = [req[0] for req in sorted_requests]
finish_times = [req[0] + 2 for req in sorted_requests] # 假设每单耗时 2 小时
selected = activity_selection(start_times, finish_times)
print("\n[5] 活动选择问题 - 时间不冲突的接单安排：")
for s, f in selected:
print(f" 出发 {s} 点 -> 结束 {f} 点")
# 7. KMP 算法：校验目的地名称是否在地址库中
address_db = "中央车站,机场,火车站,市中心,科技园区"
print("\n[6] KMP 算法 - 校验目的地名称：")
for req in sorted_requests:
dest = req[1]
pos = kmp_search(address_db, dest)
status = "地址有效" if pos != -1 else "地址无效"
print(f" {dest}：{status}（匹配位置 {pos}）")
print("\n" + "=" * 50)
print("调度系统运行完毕！")
print("=" * 50)
# 运行综合实战案例
traffic_dispatch_system()
9.3 运行结果
==================================================
城市交通调度系统 - 综合实战
==================================================
[1] 快速排序 - 按出发时间整理请求：
出发时间 5 点 -> 火车站（2 人，预估收益 60 元）
出发时间 6 点 -> 机场（3 人，预估收益 80 元）
出发时间 7 点 -> 市中心（4 人，预估收益 100 元）
出发时间 8 点 -> 中央车站（2 人，预估收益 50 元）
出发时间 9 点 -> 科技园区（1 人，预估收益 30 元）
[2] 二分搜索 - 查找出发时间 7 点的请求：
找到：市中心（4 人，预估收益 100 元）
[3] Dijkstra 算法 - 从调度中心到各上车点的最短距离：
到 中央车站：5 公里
到 机场：12 公里
到 火车站：8 公里
到 市中心：8 公里
到 科技园区：10 公里
[4] 0-1 背包问题 - 车辆容量 4 人时的最大收益：
最大收益：140 元
[5] 活动选择问题 - 时间不冲突的接单安排：
出发 5 点 -> 结束 7 点
出发 7 点 -> 结束 9 点
出发 9 点 -> 结束 11 点
[6] KMP 算法 - 校验目的地名称：
火车站：地址有效（匹配位置 4）
机场：地址有效（匹配位置 3）
市中心：地址有效（匹配位置 8）
中央车站：地址有效（匹配位置 0）
科技园区：地址有效（匹配位置 11）
==================================================
调度系统运行完毕！
==================================================
9.4 案例小结
通过这个综合实战案例可以看到，一个真实的业务系统往往需要多种算法协同配合：
- 快速排序负责将无序的请求数据整理为有序结构，为后续的二分搜索奠定基础；
- 二分搜索在有序数据上实现 O(log n) 的快速定位；
- Dijkstra 算法解决路网中的最短路径规划问题；
- 0-1 背包问题在容量约束下求得最优收益组合；
- 活动选择问题用贪心策略在时间冲突下安排最多任务；
- KMP 算法在线性时间内完成字符串匹配校验。
这正是算法学习的价值所在——理解每种算法的适用场景与复杂度特性，才能在真实业务中做出正确的选型与组合。
10. 常见面试题与易错点
掌握了 7 个核心算法的原理与实现后，面试中往往还会考察对算法细节的理解与边界情况的处理。下面针对每个算法各设计 1 道典型面试题，包含题目描述、考察点与易错提示，并给出简要解答思路。
10.1 冒泡排序
题目描述：给定一个数组，用冒泡排序将其升序排列，并说明在什么情况下冒泡排序的时间复杂度可以优化到 O(n)。
考察点：冒泡排序的基本实现、提前终止优化、最好/最坏时间复杂度。
易错提示：忘记设置 swapped 标志位，导致已有序数组仍执行完整 O(n²) 循环；内层循环边界写成 n - 1 而非 n - 1 - i，造成多余比较。
解答思路：每轮比较相邻元素并交换逆序对，若某一轮没有任何交换，说明数组已有序，可提前结束。当输入数组本身有序时，第一轮即无交换，时间复杂度为 O(n)。
10.2 快速排序
题目描述：快速排序在最坏情况下时间复杂度为 O(n²)，请说明触发最坏情况的条件，并给出一种避免方法。
考察点：快速排序的分治思想、基准元素选择对复杂度的影响。
易错提示：误以为快速排序最坏情况是「数据量很大」；忽略基准选择策略（如固定取首元素）在数据基本有序时会导致极度不平衡的划分。
解答思路：当每次划分都极度不平衡（如基准恰好是最大或最小值）时触发最坏情况，常见于数据基本有序且固定取首元素为基准。可通过随机选取基准、三数取中法或洗牌预处理来避免，使期望复杂度稳定在 O(n log n)。
10.3 二分搜索
题目描述：在有序数组 [1, 3, 5, 7, 9, 11, 13] 中查找目标值 7，写出二分搜索过程，并说明循环终止条件。
考察点：二分搜索的区间维护、left/right 指针更新、循环不变量。
易错提示：mid 计算写成 (left + right) // 2 在极端大数下可能溢出（Python 无此问题，但其他语言需注意）；更新边界时写成 left = mid 或 right = mid 导致死循环；忘记处理未找到返回 -1 的情况。
解答思路：维护 [left, right] 闭区间，mid = (left + right) // 2。若 arr[mid] == target 返回 mid；若 arr[mid] < target 则 left = mid + 1，否则 right = mid - 1。循环条件为 left <= right，退出时返回 -1。本题中 7 位于下标 3。
10.4 Dijkstra 算法
题目描述：Dijkstra 算法为什么不能处理含负权边的图？请举例说明。
考察点：Dijkstra 的贪心策略本质、负权边导致贪心失效的原因。
易错提示：只回答「因为算法假设非负权」而不举例；混淆 Dijkstra 与 Bellman-Ford 的适用场景。
解答思路：Dijkstra 每次从优先队列中弹出当前距离最小的顶点并标记为已确定，其正确性依赖于「已确定顶点的最短路径不会再被更新」这一性质。若存在负权边，可能出现「先经过一个较大正权路径到达某顶点，再通过负权边绕回更短」的情况，导致已确定的距离被推翻。例如 A→B 权 5、A→C 权 2、C→B 权 -3，从 A 出发 Dijkstra 会先确定 C（距离 2），再确定 B（距离 5），但实际 A→C→B 距离为 -1，比 5 更短。因此含负权边时应改用 Bellman-Ford。
10.5 0-1 背包问题
题目描述：0-1 背包与完全背包的区别是什么？0-1 背包的状态转移方程如何推导？
考察点：动态规划的状态定义、状态转移方程、两类背包问题的差异。
易错提示：混淆 0-1 背包（每件物品最多选一次）与完全背包（每件物品可无限选）；忘记 dp[i][j] 中 i 表示前 i 件物品、j 表示容量；内层循环方向写错导致物品被重复选取。
解答思路：0-1 背包每件物品只能选 0 次或 1 次，状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])，其中 dp[i][j] 表示前 i 件物品在容量 j 下的最大价值。完全背包则允许重复选取，内层循环需正序遍历。0-1 背包若用一维数组优化，内层循环必须倒序遍历，避免覆盖上一轮结果。
10.6 活动选择问题
题目描述：给定若干活动的开始与结束时间，贪心算法为什么按「结束时间最早」选择而不是「开始时间最早」或「持续时间最短」？
考察点：贪心选择性质的证明思路、反例构造能力。
易错提示：凭直觉回答「结束早留的时间多」而不给出反例；混淆活动选择与区间调度问题的变体。
解答思路：按结束时间最早选择，能保证为剩余活动留下尽可能多的可用时间，且该选择一定包含在某个最优解中（贪心选择性质）。反例：活动 A（1, 10）、B（2, 3）、C（3, 4），若按开始时间最早选 A，则只能选 1 个；按结束时间最早选 B、C，可选 2 个。按持续时间最短也可能选到冲突的组合，无法保证最优。
10.7 KMP 算法
题目描述：KMP 算法中 next 数组的含义是什么？为什么失配时主串指针不回溯？
考察点：next 数组（部分匹配表）的语义、KMP 避免回溯的原理。
易错提示：把 next 数组理解为「前缀函数」却说不清具体含义；失配时错误地回退主串指针；构建 next 数组时边界条件处理错误。
解答思路：next[i] 表示模式串 pattern[:i] 的最长相等前后缀长度。当主串与模式串在位置 j 失配时，模式串指针回退到 next[j-1]，主串指针 i 不回溯，因为已匹配部分的后缀与模式串前缀相同，无需重新比较。这样主串只需扫描一遍，总时间复杂度为 O(n + m)。
8. 总结
需要强调的是，具体需要掌握哪些算法取决于程序员所从事的领域和项目需求。因此，不同的程序员可能会更加专注于某些特定类型的算法，并对它们进行更深入的学习和研究。
一站式 AI 云服务平台
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)