一、排序算法：基础中的基石

排序算法是计算机科学中最基础且应用最广泛的算法类别，其性能直接影响数据处理的效率。以下三种排序算法是理解其他复杂算法的基础。

1. 快速排序（Quick Sort）

快速排序采用分治思想，通过选取基准值（pivot）将数组划分为小于和大于基准值的两部分，递归处理子数组。其平均时间复杂度为O(n log n)，但最坏情况下（如已排序数组）会退化为O(n²)。实现时需注意基准值的选择策略（如三数取中法）以避免极端情况。

def quick_sort(arr):
    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)

2. 归并排序（Merge Sort）

归并排序通过递归将数组拆分为最小单元后合并，保证每次合并操作的时间复杂度为O(n)。其稳定性和O(n log n)的时间复杂度使其适用于大规模数据排序，但需要O(n)的额外空间。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

3. 堆排序（Heap Sort）

堆排序利用二叉堆结构，首先构建最大堆（或最小堆），然后反复提取堆顶元素并调整堆结构。其时间复杂度稳定为O(n log n)，且不需要额外空间，但实际运行中因缓存不友好可能略慢于快速排序。

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

二、搜索算法：定位目标的核心

搜索算法是解决”是否存在”或”如何找到”问题的关键工具，其效率直接影响系统响应速度。

4. 二分查找（Binary Search）

二分查找要求数据必须有序，通过每次将搜索范围减半来快速定位目标。其时间复杂度为O(log n)，但需注意边界条件的处理（如左闭右开区间）。

def binary_search(arr, target):
    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

5. 深度优先搜索（DFS）

DFS通过递归或栈结构遍历图或树的所有节点，适用于寻找连通分量或路径问题。实现时需注意标记已访问节点以避免重复处理。

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. 广度优先搜索（BFS）

BFS使用队列结构按层级遍历节点，适用于最短路径问题（如无权图）。其空间复杂度为O(V)，需注意队列的入队出队操作。

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

三、图论算法：解决复杂网络问题

图论算法是处理网络结构问题的核心，包括路径查找、最小生成树等。

7. Dijkstra算法

Dijkstra算法用于解决带权有向图的单源最短路径问题，通过优先队列选择当前最短路径节点。其时间复杂度为O((V+E) log V)，适用于非负权边图。

import heapq
def dijkstra(graph, start):
    heap = [(0, start)]
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    while heap:
        (dist, current) = heapq.heappop(heap)
        if dist > distances[current]:
            continue
        for neighbor, weight in graph[current].items():
            distance = dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

8. Kruskal算法

Kruskal算法通过贪心策略构建最小生成树，按权值从小到大选择边并避免形成环。需使用并查集（Union-Find）数据结构高效检测环。

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[y_root] = x_root
def kruskal(graph):
    edges = []
    for u in graph:
        for v, w in graph[u].items():
            edges.append((w, u, v))
    edges.sort()
    uf = UnionFind(len(graph))
    mst = []
    for w, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, w))
    return mst

四、动态规划：优化重复计算

动态规划通过存储子问题解避免重复计算，适用于具有最优子结构性质的问题。

9. 斐波那契数列（递归转动态规划）

递归实现斐波那契数列的时间复杂度为O(2^n)，通过动态规划可优化至O(n)。

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]

10. 0-1背包问题

0-1背包问题要求在给定容量下选择物品使总价值最大，需使用二维数组存储中间状态。

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

五、算法选择与优化策略

数据规模分析：小规模数据（n<100）可优先选择简单算法（如插入排序），大规模数据需选择O(n log n)算法。
空间复杂度权衡：堆排序比归并排序更节省空间，但实际运行可能更慢。
稳定性需求：归并排序和插入排序是稳定排序，适用于需要保持原始顺序的场景。
并行化潜力：归并排序和快速排序易于并行化，可结合多线程提升性能。

掌握这十种算法的设计思想与实现细节，能帮助开发者在面对复杂问题时快速选择最优解法。实际开发中，建议通过LeetCode等平台进行针对性练习，同时结合具体业务场景优化算法实现。

数据结构与算法：十大经典算法解析与实现