1. 排序算法

(1) 冒泡排序（Bubble Sort）

原理：
冒泡排序是一种简单的排序算法，它通过重复遍历列表，比较相邻的元素并交换它们的位置，直到整个列表有序为止。每一轮遍历会将最大的元素“冒泡”到列表末尾。

代码实现：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 每次遍历时，最后i个元素已排序完成，无需再比较
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

时间复杂度：

• 最坏情况：O(n²)（当列表完全逆序）
• 平均情况：O(n²)
• 最好情况：O(n)（如果列表已经有序，可以通过优化提前终止）

优化方法：
添加一个标志位，如果某一轮没有发生任何交换，说明列表已经有序，可以直接退出循环。

---

(2) 快速排序（Quick Sort）

原理：
快速排序是一种分治法（Divide and Conquer）的经典应用。它选择一个基准元素（pivot），将数组分为两个子数组：一部分小于基准值，另一部分大于基准值。然后对这两个子数组递归地进行快速排序。

代码实现：

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)

时间复杂度：

• 最坏情况：O(n²)（当每次划分极不平衡时）
• 平均情况：O(n log n)

优化方法：
随机选择基准值或三数取中法，避免最坏情况的发生。

---

(3) 归并排序（Merge Sort）

原理：
归并排序也是分治法的一种。它将数组分成两半，分别对两半进行排序，然后将排好序的两半合并成一个有序数组。

代码实现：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    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
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

时间复杂度：

• 最坏情况：O(n log n)
• 平均情况：O(n log n)

优点：
稳定排序，适合链表结构等应用场景。

---

2. 查找算法

(1) 线性查找（Linear Search）

原理：
线性查找是最基本的查找方式，从头开始逐个检查元素，直到找到目标元素或遍历完整个列表。

代码实现：

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

时间复杂度：

• 最坏情况：O(n)
• 平均情况：O(n)

适用场景：
无序列表或数据量较小的情况。

---

(2) 二分查找（Binary Search）

原理：
二分查找适用于有序列表。它通过不断缩小搜索范围，将目标值与中间元素比较，若目标值小于中间元素，则在左半部分继续查找；否则在右半部分查找。

代码实现：

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

时间复杂度：

• 最坏情况：O(log n)
• 平均情况：O(log n)

适用场景：
有序列表中的高效查找。

---

3. 图算法

(1) 深度优先搜索（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)

时间复杂度：

• O(V + E)，其中 V 是顶点数，E 是边数。

---

(2) 广度优先搜索（BFS）

原理：
广度优先搜索按层遍历图，首先访问起始节点的所有邻居，然后再访问邻居的邻居，依此类推。

代码实现：

from collections import deque

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

时间复杂度：

• O(V + E)

---

4. 动态规划算法

背包问题（Knapsack Problem）

原理：
动态规划是一种解决复杂问题的方法，通常用于具有重叠子问题和最优子结构的问题。背包问题是经典的动态规划问题之一，目标是在容量限制下最大化物品价值。

代码实现：

def knapsack(weights, values, capacity):
    n = len(values)
    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(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

时间复杂度：

• O(n * capacity)