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 数组	模式串极短、单次匹配（朴素匹配即可）

下面是一张算法选型流程图，根据问题类型与关键条件（数据规模、是否有序、是否含负权边）引导读者快速锁定合适的算法：

说明：流程图从「问题类型」出发，依次结合数据规模、是否有序、是否含负权边等关键条件进行分支判断，最终落到具体的算法选择；其中「组合优化问题」若满足贪心选择性质（如活动选择）可优先用贪心，否则用动态规划保证全局最优。

选型建议

• 数据量小时选冒泡排序：当数据规模很小（如几十个元素）且对稳定性有要求时，冒泡排序实现简单、代码直观，足够胜任。
• 大规模数据排序选快速排序：面对海量数据，快速排序平均 O(n log n) 的性能优势明显，是绝大多数系统库排序函数的默认选择。
• 有序数组用二分搜索：只要数据是有序且静态的，二分搜索 O(log n) 的查找效率远高于线性扫描，是查找场景的首选。
• 非负权图用 Dijkstra：在导航、路由等非负权图场景中，Dijkstra 配合优先队列能在 O((V + E) log V) 内求出单源最短路径；若图中存在负权边，则应改用 Bellman-Ford 算法。
• 组合优化问题用动态规划：当问题具有重叠子问题与最优子结构性质（如 0-1 背包）时，动态规划能保证求得全局最优解。
• 满足贪心性质的问题用贪心算法：活动选择这类满足贪心选择性质的问题，贪心算法能以最低的复杂度快速得到最优解。
• 字符串匹配用 KMP：在长文本中反复匹配模式串时，KMP 的 O(n + m) 线性复杂度能避免朴素匹配的回溯开销。

小结：选型时先判断问题类型（排序/搜索/图/优化/匹配），再结合数据规模、是否有序、是否含负权边等约束条件，即可快速锁定合适的算法。

8. 总结

需要强调的是，具体需要掌握哪些算法取决于程序员所从事的领域和项目需求。因此，不同的程序员可能会更加专注于某些特定类型的算法，并对它们进行更深入的学习和研究。