算法与数据结构入门教程

🎯 本教程面向零基础学习者，用通俗易懂的中文讲解计算机科学中最核心的知识——数据结构与算法。所有内容均为原创，配有图解说明和 Python 代码示例。

---

目录

1. 什么是数据结构与算法？
2. 时间复杂度：如何衡量算法的好坏
3. 线性数据结构
   • 3.1 数组（Array）
   • 3.2 链表（Linked List）
   • 3.3 栈（Stack）
   • 3.4 队列（Queue）
4. 哈希表（Hash Table）
5. 树形数据结构
   • 5.1 二叉树（Binary Tree）
   • 5.2 堆（Heap）
6. 图（Graph）
7. 排序算法
8. 搜索算法
9. 动态规划（Dynamic Programming）
10. 经典题目解析
11. 学习建议

---

1. 什么是数据结构与算法？

数据结构是组织和存储数据的方式。想象你整理衣柜：可以把衣服按季节叠放（数组），也可以按类型挂起来（链表）。不同的整理方式决定了你找衣服的效率。

算法是解决特定问题的一系列步骤。就像菜谱——"番茄炒蛋"的步骤就是一个算法。

两者的关系：数据结构是"容器"，算法是"操作容器的方法"。选对了数据结构，算法才能高效运行。

---

2. 时间复杂度：如何衡量算法的好坏

2.1 什么是时间复杂度？

时间复杂度用来描述算法运行时间随数据量增长的变化趋势，用 大 O 表示法（Big O Notation）表示。

核心思想：我们不关心具体执行了多少毫秒，只关心数据量 n 增大时，运行时间增长的"量级"。

2.2 常见时间复杂度（从快到慢）

复杂度	名称	举例	n=1000 时大约操作次数
O(1)	常数	数组按下标访问	1
O(log n)	对数	二分查找	10
O(n)	线性	遍历数组	1,000
O(n log n)	线性对数	快速排序	10,000
O(n²)	平方	冒泡排序	1,000,000
O(2ⁿ)	指数	暴力穷举所有子集	天文数字

2.3 图解：复杂度增长曲线

时间
 ↑
 │                                    ╱ O(2ⁿ)
 │                                  ╱
 │                                ╱
 │                             ╱  O(n²)
 │                          ╱
 │                       ╱
 │                   ╱        O(n log n)
 │               ╱      ╱
 │           ╱      ╱      O(n)
 │       ╱      ╱     ╱
 │   ╱      ╱    ╱        O(log n)
 │ ╱     ╱   ╱         ────────── O(1)
 └──────────────────────────────────→ n (数据量)

2.4 如何分析时间复杂度？

规则：

• 只看最高次项：3n² + 2n + 1 → O(n²)
• 去掉常数系数：5n → O(n)
• 嵌套循环相乘：外层 n 次，内层 n 次 → O(n²)

# O(n) —— 单层循环
def sum_list(arr):
    total = 0
    for num in arr:    # 执行 n 次
        total += num
    return total

# O(n²) —— 嵌套循环
def print_pairs(arr):
    for i in arr:          # 执行 n 次
        for j in arr:      # 每次再执行 n 次
            print(i, j)    # 总共 n × n = n² 次

---

3. 线性数据结构

线性数据结构中的元素按顺序排列，每个元素最多有一个前驱和一个后继。

3.1 数组（Array）

概念

数组是最基础的数据结构，它在内存中占据连续的空间，通过下标（索引） 直接访问元素。

图解

下标:    0     1     2     3     4
       ┌─────┬─────┬─────┬─────┬─────┐
       │  10 │  20 │  30 │  40 │  50 │
       └─────┴─────┴─────┴─────┴─────┘
       内存地址连续：1000  1004  1008  1012  1016

       arr[2] = 30    ← 直接通过下标访问，O(1)

核心操作与复杂度

操作	时间复杂度	说明
访问元素	O(1)	直接用下标定位
查找元素	O(n)	需要遍历
尾部插入	O(1)	直接放到末尾
中间插入	O(n)	需要移动后续元素
中间删除	O(n)	需要移动后续元素

代码示例

# Python 中的列表（list）本质上就是动态数组
arr = [10, 20, 30, 40, 50]

# 访问 —— O(1)
print(arr[2])       # 输出: 30

# 查找 —— O(n)
index = arr.index(30)  # 输出: 2

# 尾部插入 —— O(1)
arr.append(60)       # [10, 20, 30, 40, 50, 60]

# 中间插入 —— O(n)
arr.insert(1, 15)    # [10, 15, 20, 30, 40, 50, 60]

# 删除 —— O(n)
arr.pop(2)           # 删除下标为2的元素 → [10, 15, 30, 40, 50, 60]

优缺点

• ✅ 优点：随机访问快 O(1)，缓存友好（连续内存）
• ❌ 缺点：插入/删除慢 O(n)，大小固定（静态数组）

---

3.2 链表（Linked List）

概念

链表由一系列节点（Node） 组成，每个节点包含数据和指向下一个节点的指针。节点在内存中可以不连续存放。

图解：单链表

 ┌───┬──┐    ┌───┬──┐    ┌───┬──┐    ┌───┬──────┐
 │ 1 │ ──→ │ 2 │ ──→ │ 3 │ ──→ │ 4 │ NULL │
 └───┴──┘    └───┴──┘    └───┴──┘    └───┴──────┘
  head                                tail

 每个节点 = [数据 | next指针]

图解：链表 vs 数组

数组（连续存储）:
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │   ← 内存连续，按下标直接跳转
└────┴────┴────┴────┴────┘

链表（分散存储）:
┌────┐   ┌────┐   ┌────┐   ┌────┐
│ 10 │   │ 30 │   │ 20 │   │ 40 │   ← 内存不连续
└──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘
   │↗       │↗       │↗       │↗
   通过指针串联，必须沿链遍历

核心操作与复杂度

操作	时间复杂度	说明
访问第 k 个	O(k)	需要从头遍历
查找元素	O(n)	需要遍历
头部插入	O(1)	改变 head 指针即可
中间插入	O(n)	先找到位置
头部删除	O(1)	改变 head 指针即可
中间删除	O(n)	先找到前一个节点

代码示例

class ListNode:
    """链表节点"""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    """单链表"""
    def __init__(self):
        self.head = None

    def prepend(self, val):
        """头部插入 —— O(1)"""
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node

    def append(self, val):
        """尾部插入 —— O(n)"""
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def find(self, val):
        """查找元素 —— O(n)"""
        curr = self.head
        while curr:
            if curr.val == val:
                return True
            curr = curr.next
        return False

    def delete(self, val):
        """删除第一个匹配的节点 —— O(n)"""
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            return
        curr = self.head
        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
                return
            curr = curr.next

    def display(self):
        """打印链表"""
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.val))
            curr = curr.next
        print(" → ".join(elements) + " → NULL")

# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.display()   # 0 → 1 → 2 → 3 → NULL
ll.delete(2)
ll.display()   # 0 → 1 → 3 → NULL

优缺点

• ✅ 优点：插入/删除快 O(1)（已知位置时），动态大小
• ❌ 缺点：不支持随机访问，额外指针开销

---

3.3 栈（Stack）

概念

栈是一种后进先出（LIFO） 的数据结构。想象一摞盘子——你只能从最上面放（入栈）和取（出栈）。

图解

    入栈 ↑       出栈 ↑
         │            │
    ┌─────────┐
    │   TOP   │  ← 最后放入的元素，最先取出
    ├─────────┤
    │    3    │
    ├─────────┤
    │    2    │
    ├─────────┤
    │    1    │  ← 最先放入的元素，最后取出
    └─────────┘

核心操作与复杂度

操作	时间复杂度	说明
push（入栈）	O(1)	放到栈顶
pop（出栈）	O(1)	取出栈顶
peek/top（查看栈顶）	O(1)	只看不取

代码示例

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        """入栈"""
        self.items.append(val)

    def pop(self):
        """出栈"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.items.pop()

    def peek(self):
        """查看栈顶"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())    # 3（最后放入的最先取出）
print(stack.peek())   # 2
print(stack.pop())    # 2

经典应用：括号匹配

def is_valid_parentheses(s: str) -> bool:
    """
    LeetCode 20: 有效的括号
    判断括号字符串是否有效：()[]{}
    """
    stack = Stack()
    mapping = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in mapping:
            # 遇到右括号，检查栈顶是否匹配
            if stack.is_empty() or stack.pop() != mapping[char]:
                return False
        else:
            # 遇到左括号，入栈
            stack.push(char)

    return stack.is_empty()

# 测试
print(is_valid_parentheses("()[]{}"))   # True
print(is_valid_parentheses("([)]"))     # False
print(is_valid_parentheses("{[]}"))     # True

---

3.4 队列（Queue）

概念

队列是一种先进先出（FIFO） 的数据结构。就像排队买奶茶——先来的先买到。

图解

  出队 ←                           ← 入队
         ┌────┬────┬────┬────┬────┐
         │  1 │  2 │  3 │  4 │  5 │
         └────┴────┴────┴────┴────┘
         先出                       后进
         front                      rear

核心操作与复杂度

操作	时间复杂度	说明
enqueue（入队）	O(1)	放到队尾
dequeue（出队）	O(1)	从队头取
peek（查看队头）	O(1)	只看不取

代码示例

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, val):
        """入队"""
        self.items.append(val)

    def dequeue(self):
        """出队"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.items.popleft()

    def peek(self):
        """查看队头"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# 使用示例
q = Queue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")
print(q.dequeue())  # A（先入先出）
print(q.dequeue())  # B

经典应用：用栈实现队列

class MyQueue:
    """
    LeetCode 232: 用栈实现队列
    思路：用两个栈，一个负责入队，一个负责出队
    """
    def __init__(self):
        self.stack_in = []   # 入队栈
        self.stack_out = []  # 出队栈

    def push(self, x):
        self.stack_in.append(x)

    def pop(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

    def peek(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out[-1]

    def empty(self):
        return not self.stack_in and not self.stack_out

---

4. 哈希表（Hash Table）

概念

哈希表通过哈希函数将键（key）映射到数组的某个位置，从而实现近乎 O(1) 的查找。它是"键值对"存储的核心。

图解：哈希表工作原理

Key: "apple"  →  哈希函数  →  下标 2
Key: "banana" →  哈希函数  →  下标 5
Key: "cherry" →  哈希函数  →  下标 1

存储结构:
下标:   0      1        2         3      4        5
     ┌─────┬────────┬─────────┬─────┬─────┬─────────┐
     │     │ cherry │  apple  │     │     │ banana  │
     └─────┴────────┴─────────┴─────┴─────┴─────────┘

图解：哈希冲突与链地址法

当两个不同的 key 映射到同一个下标时，就发生了哈希冲突。常见解决方法是链地址法——每个位置挂一个链表。

Key: "apple"  →  下标 2
Key: "grape"  →  下标 2   （冲突！）

下标 2:
┌─────────┐    ┌─────────┐
│ "apple" │ →  │ "grape" │ → NULL
└─────────┘    └─────────┘

核心操作与复杂度

操作	平均时间	最坏时间	说明
插入	O(1)	O(n)	最坏情况：所有 key 冲突
查找	O(1)	O(n)	同上
删除	O(1)	O(n)	同上

代码示例

class SimpleHashTable:
    """简单的哈希表实现（链地址法处理冲突）"""
    def __init__(self, size=16):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        """哈希函数"""
        return hash(key) % self.size

    def put(self, key, value):
        """插入/更新键值对"""
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新
                return
        bucket.append((key, value))  # 新增

    def get(self, key):
        """根据 key 查找 value"""
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        """删除键值对"""
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return
        raise KeyError(key)

# 使用示例
ht = SimpleHashTable()
ht.put("name", "Alice")
ht.put("age", 25)
print(ht.get("name"))   # Alice
print(ht.get("age"))    # 25

经典应用：两数之和

def two_sum(nums: list, target: int) -> list:
    """
    LeetCode 1: 两数之和
    找到数组中和为目标值的两个数的下标

    思路：用哈希表记录已遍历的数字及其下标
    时间复杂度: O(n)
    """
    seen = {}  # 哈希表：值 → 下标

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

# 测试
print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2]

---

5. 树形数据结构

5.1 二叉树（Binary Tree）

概念

二叉树是每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。

图解：二叉树的基本结构

            1           ← 根节点（root）
           / \
          2   3         ← 深度 1
         / \   \
        4   5   6       ← 深度 2（叶子节点：4, 5, 6）

术语:
- 根节点: 1（最顶层的节点）
- 叶子节点: 4, 5, 6（没有子节点的节点）
- 深度: 从根到该节点的边数
- 高度: 从该节点到最远叶子的边数
- 子树: 以某个节点为根的树

图解：二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树：左子树所有节点 < 根节点 < 右子树所有节点。

            8
           / \
          3   10
         / \    \
        1   6    14
           / \   /
          4   7 13

查找 7 的过程:
8 → 7 < 8，走左边 → 3
3 → 7 > 3，走右边 → 6
6 → 7 > 6，走右边 → 7   ✓ 找到了！

代码示例

class TreeNode:
    """二叉树节点"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# ---- 构建二叉树 ----
#        1
#       / \
#      2   3
#     / \
#    4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# ---- 三种遍历方式 ----

def preorder(root):
    """前序遍历：根 → 左 → 右"""
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """中序遍历：左 → 根 → 右"""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    """后序遍历：左 → 右 → 根"""
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def level_order(root):
    """层序遍历（BFS）：逐层从左到右"""
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

print(preorder(root))   # [1, 2, 4, 5, 3]
print(inorder(root))    # [4, 2, 5, 1, 3]
print(postorder(root))  # [4, 5, 2, 3, 1]
print(level_order(root)) # [1, 2, 3, 4, 5]

经典应用：二叉树的最大深度

def max_depth(root: TreeNode) -> int:
    """
    LeetCode 104: 二叉树的最大深度
    思路：递归，最大深度 = max(左子树深度, 右子树深度) + 1
    时间复杂度: O(n)，空间复杂度: O(h)，h 为树高
    """
    if not root:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return max(left_depth, right_depth) + 1

---

5.2 堆（Heap）

概念

堆是一种特殊的完全二叉树：

• 最大堆：每个节点 ≥ 其子节点（堆顶是最大值）
• 最小堆：每个节点 ≤ 其子节点（堆顶是最小值）

图解：最大堆

            90
           /  \
         80    70
        / \   / \
      50  60 65  30
     / \
    20  40

性质: 父节点 ≥ 子节点
     90 ≥ 80, 90 ≥ 70
     80 ≥ 50, 80 ≥ 60
     ...

图解：堆的数组表示

完全二叉树可以用数组紧凑存储，不需要指针：

树:         90
           /  \
         80    70
        / \   / \
      50  60 65  30

数组: [90, 80, 70, 50, 60, 65, 30]
下标:  0   1   2   3   4   5   6

对于下标 i 的节点:
- 左子节点: 2i + 1
- 右子节点: 2i + 2
- 父节点:   (i - 1) // 2

核心操作与复杂度

操作	时间复杂度	说明
查看堆顶	O(1)	直接取数组第一个元素
插入	O(log n)	上浮操作，最多交换树的高度次
删除堆顶	O(log n)	下沉操作
建堆	O(n)	自底向上调整

代码示例

import heapq

# Python 内置 heapq 模块（最小堆）
nums = [5, 3, 8, 1, 9, 2]

# 建堆 —— O(n)
heapq.heapify(nums)
print(nums)  # [1, 3, 2, 5, 9, 8]（堆的数组形式）

# 插入 —— O(log n)
heapq.heappush(nums, 0)
print(nums)  # [0, 3, 1, 5, 9, 8, 2]

# 弹出最小值 —— O(log n)
smallest = heapq.heappop(nums)
print(smallest)  # 0

# 取前 k 个最小值
print(heapq.nsmallest(3, nums))  # [1, 2, 3]

手写最大堆

class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        """插入元素（上浮）"""
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        """弹出最大值（下沉）"""
        if not self.heap:
            raise IndexError("堆为空")
        # 交换堆顶和堆尾
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        max_val = self.heap.pop()
        if self.heap:
            self._sift_down(0)
        return max_val

    def _sift_up(self, i):
        """上浮：与父节点比较，比父节点大就交换"""
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] > self.heap[parent]:
                self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
                i = parent
            else:
                break

    def _sift_down(self, i):
        """下沉：与较大的子节点交换"""
        n = len(self.heap)
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            if largest != i:
                self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
                i = largest
            else:
                break

# 使用示例
h = MaxHeap()
for val in [5, 3, 8, 1, 9]:
    h.push(val)
print(h.heap)     # [9, 5, 8, 1, 3]
print(h.pop())    # 9
print(h.pop())    # 8

---

6. 图（Graph）

概念

图由顶点（Vertex） 和边（Edge） 组成，用来表示事物之间的关系。

图解：图的分类

无向图:                 有向图:
  A --- B               A → B
  |   / |               ↑   ↓
  |  /  |               D ← C
  C --- D

带权图:
  A --5-- B
  |       |
  3       2
  |       |
  C --7-- D

表示: A到B的边权重为5，A到C的边权重为3...

图的存储方式

邻接矩阵

图:     A --- B
        |   /
        |  /
        C

邻接矩阵:     A  B  C
          A [ 0  1  1 ]
          B [ 1  0  1 ]
          C [ 1  1  0 ]

1 表示有边，0 表示无边

邻接表

图:     A --- B
        |   /
        |  /
        C

邻接表:
A → [B, C]
B → [A, C]
C → [A, B]

代码示例

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.adj = defaultdict(list)  # 邻接表

    def add_edge(self, u, v, directed=False):
        """添加边"""
        self.adj[u].append(v)
        if not directed:
            self.adj[v].append(u)

    def bfs(self, start):
        """广度优先搜索（BFS）—— 层层推进"""
        visited = set()
        queue = deque([start])
        visited.add(start)
        result = []

        while queue:
            node = queue.popleft()
            result.append(node)
            for neighbor in self.adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return result

    def dfs(self, start):
        """深度优先搜索（DFS）—— 一路走到底"""
        visited = set()
        result = []

        def _dfs(node):
            visited.add(node)
            result.append(node)
            for neighbor in self.adj[node]:
                if neighbor not in visited:
                    _dfs(neighbor)

        _dfs(start)
        return result

# 使用示例
g = Graph()
#     A --- B
#     |   / |
#     |  /  |
#     C --- D
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")

print(g.bfs("A"))  # ['A', 'B', 'C', 'D']
print(g.dfs("A"))  # ['A', 'B', 'C', 'D']（顺序可能不同）

图解：BFS vs DFS

图:     1 --- 2
        |   / |
        |  /  |
        3 --- 4

BFS 从 1 出发（用队列）:
第1步: 访问 1，入队 [1]
第2步: 出队 1，访问邻居 2,3 → 队列 [2, 3]
第3步: 出队 2，访问邻居 4   → 队列 [3, 4]
第4步: 出队 3，邻居已访问    → 队列 [4]
第5步: 出队 4，邻居已访问    → 队列 []
结果: 1 → 2 → 3 → 4（逐层扩展）

DFS 从 1 出发（用栈/递归）:
第1步: 访问 1
第2步: 走到 2
第3步: 走到 3
第4步: 走到 4
第5步: 回溯
结果: 1 → 2 → 3 → 4（一路深入）

最短路径：Dijkstra 算法

import heapq

def dijkstra(graph, start):
    """
    Dijkstra 最短路径算法
    graph: {节点: [(邻居, 权重), ...]}
    返回: 从 start 到所有节点的最短距离
    时间复杂度: O((V + E) log V)
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (距离, 节点)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

# 示例
graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('A', 4), ('C', 2), ('D', 5)],
    'C': [('A', 1), ('B', 2), ('D', 8)],
    'D': [('B', 5), ('C', 8)],
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 3, 'C': 1, 'D': 8}

---

7. 排序算法

7.1 冒泡排序（Bubble Sort）

思路

反复比较相邻元素，把大的"冒泡"到末尾。

图解

原始: [5, 3, 8, 1, 2]

第1轮（把最大值冒泡到末尾）:
  [5, 3, 8, 1, 2]  → 比较 5,3 → 交换 → [3, 5, 8, 1, 2]
  [3, 5, 8, 1, 2]  → 比较 5,8 → 不换  → [3, 5, 8, 1, 2]
  [3, 5, 8, 1, 2]  → 比较 8,1 → 交换 → [3, 5, 1, 8, 2]
  [3, 5, 1, 8, 2]  → 比较 8,2 → 交换 → [3, 5, 1, 2, 8] ✓

第2轮:
  [3, 5, 1, 2, 8]  → ... → [3, 1, 2, 5, 8] ✓

第3轮:
  [3, 1, 2, 5, 8]  → ... → [1, 2, 3, 5, 8] ✓

已排序: [1, 2, 3, 5, 8]

代码

def bubble_sort(arr):
    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([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

时间复杂度：O(n²)（最坏/平均），O(n)（最好，已有序时） 空间复杂度：O(1)

---

7.2 快速排序（Quick Sort）

思路

选一个基准值（pivot），把数组分成两部分：比基准小的放左边，比基准大的放右边，然后递归排序两部分。

图解

原始: [5, 3, 8, 1, 2]
选择 pivot = 5

分区:
  比5小: [3, 1, 2]
  等于:  [5]
  比5大: [8]

递归:
  排序 [3, 1, 2] → pivot=3 → [1,2] [3] [] → [1, 2, 3]
  排序 [8] → [8]

合并: [1, 2, 3] + [5] + [8] = [1, 2, 3, 5, 8]

代码

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)

print(quick_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

时间复杂度：O(n log n)（平均），O(n²)（最坏，已排序时） 空间复杂度：O(log n)

---

7.3 归并排序（Merge Sort）

思路

将数组不断一分为二，直到每部分只有一个元素，然后合并有序的子数组。

图解

         [5, 3, 8, 1, 2]
        /                 \
    [5, 3, 8]          [1, 2]
    /       \           /   \
  [5, 3]    [8]       [1]   [2]
  /   \
[5]   [3]

--- 开始合并（每一步都是有序合并）---

  [3, 5]    [8]       [1]   [2]
    \       /           \   /
    [3, 5, 8]          [1, 2]
        \                 /
       [1, 2, 3, 5, 8]

代码

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

print(merge_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

时间复杂度：O(n log n)（所有情况都一样） 空间复杂度：O(n)

---

排序算法对比

算法	平均时间	最坏时间	空间	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	✅ 稳定
快速排序	O(n log n)	O(n²)	O(log n)	❌ 不稳定
归并排序	O(n log n)	O(n log n)	O(n)	✅ 稳定

稳定性：相同值的元素排序后相对顺序不变。

---

8. 搜索算法

8.1 二分查找（Binary Search）

思路

在有序数组中，每次取中间值与目标比较，将搜索范围缩小一半。

图解

有序数组: [1, 3, 5, 7, 9, 11, 13, 15]
目标: 11

第1步: left=0, right=7, mid=3
  arr[3]=7 < 11 → 搜索右半边
  [1, 3, 5, 7, 9, 11, 13, 15]
                    ↑ mid

第2步: left=4, right=7, mid=5
  arr[5]=11 == 11 → 找到了！返回 5
  [1, 3, 5, 7, 9, 11, 13, 15]
                       ↑ mid ✓

代码

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  # 未找到

# 测试
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 11))  # 5
print(binary_search(arr, 6))   # -1

经典应用：搜索插入位置

def search_insert(nums: list, target: int) -> int:
    """
    LeetCode 35: 搜索插入位置
    如果目标值存在于数组中，返回其索引；
    否则返回它应该被插入的位置。
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

print(search_insert([1, 3, 5, 6], 5))  # 2
print(search_insert([1, 3, 5, 6], 2))  # 1
print(search_insert([1, 3, 5, 6], 7))  # 4

---

9. 动态规划（Dynamic Programming）

概念

动态规划（DP）是一种通过将大问题分解为重叠子问题来求解的方法。核心思想：

1. 最优子结构：大问题的最优解包含子问题的最优解
2. 重叠子问题：子问题会被重复计算
3. 状态转移方程：描述子问题之间的关系

解题步骤

1. 定义状态（dp[i] 代表什么）
2. 写出状态转移方程
3. 确定初始条件
4. 确定遍历顺序
5. 返回结果

经典例题 1：斐波那契数列

图解：递归 vs 动态规划

递归计算 fib(5)（大量重复计算）:

              fib(5)
             /      \
          fib(4)    fib(3)      ← fib(3) 被算了两次
         /    \     /    \
      fib(3) fib(2) fib(2) fib(1)
      /   \
   fib(2) fib(1)

动态规划（自底向上，无重复）:
dp[0]=0, dp[1]=1
dp[2] = dp[1] + dp[0] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5

代码

def fib(n: int) -> int:
    """
    LeetCode 509: 斐波那契数
    递归（慢）: O(2^n)
    动态规划（快）: O(n)
    """
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fib(10))  # 55

---

经典例题 2：爬楼梯

问题

每次可以爬 1 或 2 个台阶，到达第 n 阶有多少种方法？

图解

到达第 n 阶的方法 = 到达第 (n-1) 阶的方法 + 到达第 (n-2) 阶的方法
因为：最后一步要么从 n-1 跨 1 步，要么从 n-2 跨 2 步

dp[1] = 1    (1)
dp[2] = 2    (1+1, 2)
dp[3] = 3    (1+1+1, 1+2, 2+1)
dp[4] = 5    (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
dp[5] = 8    ...

本质就是斐波那契数列！

代码

def climb_stairs(n: int) -> int:
    """
    LeetCode 70: 爬楼梯
    状态转移: dp[i] = dp[i-1] + dp[i-2]
    时间: O(n), 空间: O(1)
    """
    if n <= 2:
        return n

    a, b = 1, 2  # 滚动变量，节省空间
    for _ in range(3, n + 1):
        a, b = b, a + b

    return b

print(climb_stairs(5))  # 8

---

经典例题 3：最长递增子序列（LIS）

问题

找到数组中最长的严格递增子序列的长度。

图解

arr = [10, 9, 2, 5, 3, 7, 101, 18]

dp[i] = 以 arr[i] 结尾的最长递增子序列长度

i=0: arr[0]=10   dp[0]=1            (只有自己)
i=1: arr[1]=9    dp[1]=1            (9<10，接不上)
i=2: arr[2]=2    dp[2]=1            (2<9,2<10)
i=3: arr[3]=5    dp[3]=dp[2]+1=2    (2→5)
i=4: arr[4]=3    dp[4]=dp[2]+1=2    (2→3)
i=5: arr[5]=7    dp[5]=dp[4]+1=3    (2→3→7 或 2→5→7)
i=6: arr[6]=101  dp[6]=dp[5]+1=4    (2→5→7→101)
i=7: arr[7]=18   dp[7]=dp[5]+1=4    (2→3→7→18)

dp = [1, 1, 1, 2, 2, 3, 4, 4]
答案: max(dp) = 4

代码

def length_of_lis(nums: list) -> int:
    """
    LeetCode 300: 最长递增子序列
    时间: O(n²), 空间: O(n)
    """
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # 每个元素至少长度为1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

---

经典例题 4：背包问题（0-1 背包）

问题

有 n 件物品，每件有重量和价值。背包容量为 W，每件物品只能选一次，求最大价值。

图解

物品:  重量  价值
  A     2     3
  B     3     4
  C     4     5
  D     5     6

背包容量 W = 8

dp[i][w] = 前 i 件物品、容量为 w 时的最大价值

        容量 w →
        0  1  2  3  4  5  6  7  8
  0件 [ 0  0  0  0  0  0  0  0  0 ]
  A   [ 0  0  3  3  3  3  3  3  3 ]
  B   [ 0  0  3  4  4  7  7  7  7 ]
  C   [ 0  0  3  4  5  7  8  9  9 ]
  D   [ 0  0  3  4  5  7  8  9 10 ]

答案: 10（选 B(3,4) + D(5,6) = 重量8, 价值10）

代码

def knapsack(weights, values, capacity):
    """
    0-1 背包问题
    时间: O(n × W), 空间: O(n × W)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不选第 i 件物品
            dp[i][w] = dp[i - 1][w]
            # 选第 i 件物品（如果装得下）
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack(weights, values, 8))  # 10

---

10. 经典题目解析

题目 1：反转链表（LeetCode 206）

难度：⭐⭐（简单）

思路：用三个指针（prev, curr, next）逐个翻转指针方向。

原始: 1 → 2 → 3 → 4 → 5 → NULL

翻转过程:
NULL ← 1    2 → 3 → 4 → 5 → NULL
     prev  curr

NULL ← 1 ← 2    3 → 4 → 5 → NULL
          prev  curr

NULL ← 1 ← 2 ← 3    4 → 5 → NULL
               prev  curr

... 最终:
NULL ← 1 ← 2 ← 3 ← 4 ← 5
                         ↑ 新的 head

def reverse_list(head):
    """LeetCode 206: 反转链表"""
    prev = None
    curr = head
    while curr:
        next_node = curr.next  # 保存下一个
        curr.next = prev       # 翻转指针
        prev = curr            # prev 前进
        curr = next_node       # curr 前进
    return prev  # prev 就是新的头节点

---

题目 2：有效的括号（LeetCode 20）

难度：⭐⭐（简单）

思路：遇到左括号入栈，遇到右括号检查栈顶是否匹配。

def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}

    for c in s:
        if c in mapping:
            if not stack or stack[-1] != mapping[c]:
                return False
            stack.pop()
        else:
            stack.append(c)

    return len(stack) == 0

---

题目 3：合并两个有序链表（LeetCode 21）

难度：⭐⭐（简单）

def merge_two_lists(l1, l2):
    """LeetCode 21: 合并两个有序链表"""
    dummy = ListNode(0)  # 哨兵节点
    curr = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    curr.next = l1 or l2  # 剩余部分直接接上
    return dummy.next

---

题目 4：最大子数组和（LeetCode 53）

难度：⭐⭐⭐（中等）

思路：动态规划，dp[i] 表示以 nums[i] 结尾的最大子数组和。

dp[i] = max(nums[i], dp[i-1] + nums[i])
含义：要么自己单独成为一段，要么接在前面的子数组后面

def max_sub_array(nums):
    """
    LeetCode 53: 最大子数组和
    Kadane's Algorithm
    时间: O(n), 空间: O(1)
    """
    max_sum = curr_sum = nums[0]

    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)

    return max_sum

print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
# 子数组 [4, -1, 2, 1] 的和最大

---

题目 5：二叉树的层序遍历（LeetCode 102）

难度：⭐⭐⭐（中等）

def level_order(root):
    """
    LeetCode 102: 二叉树的层序遍历
    BFS + 队列
    """
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

---

11. 学习建议

学习路线图

第1阶段（基础）          第2阶段（进阶）         第3阶段（高级）
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ 数组          │    │ 二叉树        │    │ 图算法        │
│ 链表          │    │ 堆/优先队列    │    │ 并查集        │
│ 栈/队列       │    │ 哈希表进阶     │    │ 字符串算法     │
│ 基础排序      │→   │ 二分查找      │→   │ 动态规划进阶   │
│ 基础搜索      │    │ 递归/回溯     │    │ 贪心算法       │
│ 时间复杂度    │    │ 基础DP        │    │ 高级数据结构   │
└──────────────┘    └──────────────┘    └──────────────┘

刷题建议

1. 先理解原理，再写代码：不要急于刷题，先把每个数据结构的特性搞清楚
2. 手动模拟：在纸上画图模拟算法执行过程
3. 分类刷题：按数据结构/算法类型刷，不要随机刷
4. 重复练习：隔几天重做做过的题，确保真正掌握
5. 总结模板：每类题型总结出通用的解题模板

推荐刷题顺序（LeetCode）

阶段	题目	关键词
入门	#1, #20, #21, #53, #70, #104, #206	数组、链表、栈、树、DP基础
进阶	#35, #102, #121, #141, #142, #200, #236	二分、BFS/DFS、双指针
提高	#3, #15, #33, #56, #114, #300, #322	滑动窗口、区间、背包

常见解题技巧

技巧	适用场景	经典题目
双指针	数组/链表遍历	#15, #141
滑动窗口	连续子数组	#3, #209
哈希表	快速查找/计数	#1, #49
二分查找	有序数组	#35, #33
BFS/DFS	树/图遍历	#102, #200
动态规划	最优化问题	#53, #300, #322
回溯	组合/排列/子集	#46, #78
单调栈	下一个更大/更小元素	#496, #739

---

总结

本教程涵盖了数据结构与算法的核心知识点：

类别	内容
线性结构	数组、链表、栈、队列
哈希结构	哈希表
树形结构	二叉树、二叉搜索树、堆
图形结构	图的表示、BFS、DFS、Dijkstra
排序算法	冒泡、快速、归并
搜索算法	二分查找
算法思想	动态规划、贪心、回溯

记住：数据结构与算法不是死记硬背，而是理解思想 + 反复练习。每学一个新概念，就动手写代码实现它，然后用经典题目来巩固。坚持下去，你一定能掌握这些核心技能！

---

📅 本教程由 AI 原创编写，最后更新：2026年5月28日