算法练习项目

1. 冒泡排序

目标：排序算法入门，理解基本排序原理

def bubble_sort(arr):
    """冒泡排序 - 逐一比较相邻元素"""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            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]))
# 输出: [11, 12, 22, 25, 34, 64, 90]

知识点：双重循环、相邻比较、优化提前终止

---

2. 二分查找

目标：掌握高效搜索算法，时间复杂度 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

# 测试
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))   # 输出: 3
print(binary_search(arr, 4))   # 输出: -1

知识点：左右指针、区间缩小、对数时间复杂度

---

3. 快速排序

目标：分治法经典应用，平均 O(n log 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)

# 测试
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# 输出: [1, 1, 2, 3, 6, 8, 10]

知识点：分治思想、基准点选择、递归实现

---

4. 归并排序

目标：实现分治法经典排序算法

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

# 测试
data = [38, 27, 43, 3, 9, 82, 10]
print(f"排序前: {data}")
print(f"排序后: {merge_sort(data)}")

知识点：分治法、递归、列表合并

---

5. 动态规划 - 背包问题

目标：实现 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(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    # 回溯找出选了哪些物品
    result = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            result.append(i - 1)
            w -= weights[i - 1]
    
    return dp[n][capacity], result

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

max_value, items = knapsack(weights, values, capacity)
print(f"最大价值: {max_value}")
print(f"选择物品索引: {items}")

知识点：动态规划、二维 DP 表、回溯路径

---

6. 广度优先搜索（BFS）

目标：实现图的 BFS 遍历和最短路径

from collections import deque

def bfs(graph, start, target):
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        if node == target:
            return path
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None

# 图的邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E', 'G'],
    'G': ['F']
}

path = bfs(graph, 'A', 'G')
print(f"最短路径: {' → '.join(path)}")
print(f"路径长度: {len(path) - 1}")

知识点：BFS、队列、邻接表、最短路径