Python 基础算法详解与示例

基础算法是编程面试和工程实践的核心。本文按类别详细介绍 Python 中常用的基础算法，每个算法都给出原理、步骤、代码实现、复杂度分析及应用场景，帮助你系统掌握。

---

一、排序算法

排序是将无序序列按特定顺序（升序/降序）排列的过程。

1. 快速排序（Quick Sort）

原理：分治策略。选择一个基准值（pivot），将数组分成两部分：小于基准的放左边，大于基准的放右边，然后递归地对左右子数组排序。

步骤：

1. 选择基准（如中间元素）。
2. 分区：比基准小的放左边，大的放右边，相等的放中间。
3. 递归地对左半部分和右半部分重复上述过程。

Python 实现（简洁版）：

def quicksort(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 quicksort(left) + middle + quicksort(right)

原地快排（节省空间）：

def quicksort_inplace(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort_inplace(arr, low, pi-1)
        quicksort_inplace(arr, pi+1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

• 时间复杂度：平均 O(n log n)，最坏 O(n²)（已排序且每次选最左/右为基准时）
• 空间复杂度：O(log n)（递归栈）
• 稳定性：不稳定（相同元素可能交换位置）

应用：通用排序，尤其适合大规模数据；Python 内置 sorted 底层是 Timsort，但快排思想常用。

2. 归并排序（Merge Sort）

原理：分治法。将数组分成两半，分别排序，再合并两个有序子数组。

步骤：

1. 若数组长度 ≤1，返回。
2. 将数组从中间切分为左、右两半。
3. 递归对左半排序，对右半排序。
4. 合并两个有序数组。

Python 实现：

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

• 时间复杂度：O(n log n)（稳定）
• 空间复杂度：O(n)（需要额外数组）
• 稳定性：稳定

应用：需要稳定排序的场景，外部排序（数据太大无法一次性装入内存）。

3. 内置排序

• sorted(arr)：返回新列表，不改变原数组。
• arr.sort()：原地排序，改变原数组。
• 底层是 Timsort（归并+插入的混合体），时间复杂度 O(n log n)，稳定。

---

二、搜索算法

1. 二分查找（Binary Search）

原理：在有序数组中，通过重复将查找范围减半来定位目标值。

步骤：

1. 初始化左右指针 left=0, right=len(arr)-1。
2. 当 left <= right：
   • 计算中间位置 mid = (left+right)//2。
   • 若 arr[mid] == target，返回 mid。
   • 若 arr[mid] < target，则 left = mid+1。
   • 否则 right = mid-1。
3. 若未找到，返回 -1。

Python 实现：

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

递归版本：

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid+1, right)
    else:
        return binary_search_recursive(arr, target, left, mid-1)

• 时间复杂度：O(log n)
• 空间复杂度：迭代 O(1)，递归 O(log n)（栈）

应用：有序数组查找、查找插入位置、求平方根等。

2. 线性搜索

适用于无序或小规模数据：

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

• 时间复杂度：O(n)

---

三、双指针与滑动窗口

1. 双指针（Two Pointers）

原理：使用两个指针（通常从两端或同向移动）遍历数组，减少时间复杂度。

经典问题：有序数组的两数之和。

def two_sum_sorted(nums, target):
    left, right = 0, len(nums)-1
    while left < right:
        cur_sum = nums[left] + nums[right]
        if cur_sum == target:
            return [left, right]
        elif cur_sum < target:
            left += 1
        else:
            right -= 1
    return []

其他应用：反转数组、移除元素、三数之和等。

2. 滑动窗口（Sliding Window）

原理：维护一个窗口（子数组或子串），通过移动窗口左右边界来求解最优子结构问题。

经典问题：最长无重复字符子串长度。

def length_of_longest_substring(s: str) -> int:
    left = 0
    char_set = set()
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

应用：子数组和、最小覆盖子串、字符串排列等。

---

四、递归与回溯

1. 递归（Recursion）

三要素：

• 终止条件
• 递推公式
• 返回值

示例：计算斐波那契数列。

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

优化：记忆化递归（动态规划）。

2. 回溯（Backtracking）

原理：通过递归尝试所有可能的路径，当发现当前路径不可能得到解时，回退到上一步（撤销选择）。

模板：

def backtrack(路径, 选择列表):
    if 满足结束条件:
        记录结果
        return
    for 选择 in 选择列表:
        做选择
        backtrack(新路径, 新选择列表)
        撤销选择

示例：全排列。

def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    backtrack([], [False]*len(nums))
    return res

应用：组合总和、子集、N皇后、括号生成等。

---

五、动态规划（Dynamic Programming）

核心思想：将复杂问题分解为子问题，记录子问题的解（DP 表），避免重复计算。

步骤：

1. 定义状态（DP 数组的含义）。
2. 找到状态转移方程。
3. 初始化边界条件。
4. 确定遍历顺序。
5. 返回最终结果。

示例1：爬楼梯

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a+b
    return b

• 状态：dp[i] 表示到达第 i 阶的方法数。
• 转移方程：dp[i] = dp[i-1] + dp[i-2]。

示例2：最长递增子序列（LIS）

def lengthOfLIS(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

• 时间复杂度 O(n²)，可优化为 O(n log n) 用贪心+二分。

示例3：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):
        w = weights[i-1]
        v = values[i-1]
        for c in range(1, capacity+1):
            if c < w:
                dp[i][c] = dp[i-1][c]
            else:
                dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v)
    return dp[n][capacity]

空间优化为一维数组：

dp = [0]*(capacity+1)
for i in range(n):
    for c in range(capacity, weights[i]-1, -1):
        dp[c] = max(dp[c], dp[c-weights[i]] + values[i])

应用：背包问题、编辑距离、最长公共子序列、股票交易等。

---

六、贪心算法

原理：每一步都做出当前看起来最优的选择，期望最终达到全局最优。贪心不一定保证全局最优，需证明贪心选择性质。

经典问题：分发饼干。

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1
    return child

其他应用：活动选择、区间调度、霍夫曼编码、硬币找零（特定面额）。

---

七、哈希表与计数

哈希表提供 O(1) 的平均查找、插入、删除。

Python 实现：dict（映射）、set（集合）、collections.Counter（计数器）。

示例：两数之和（无序数组）。

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

示例：字符频率统计。

from collections import Counter
s = "hello"
counter = Counter(s)  # Counter({'l':2, 'h':1, 'e':1, 'o':1})

应用：查找重复元素、字母异位词分组、LRU 缓存等。

---

八、图论基础

1. 广度优先搜索（BFS）

原理：使用队列，层层向外扩展，适合求最短路径（无权图）。

from collections import deque

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

2. 深度优先搜索（DFS）

原理：使用栈或递归，一条路走到黑再回溯。

def dfs_recursive(node, visited, graph):
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(neighbor, visited, graph)

应用：拓扑排序、连通分量、路径查找、迷宫问题。

---

九、链表操作

链表节点定义：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

反转链表（迭代法）

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

检测环（快慢指针）

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

---

十、二叉树基础

节点定义：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

前序遍历（递归）

def preorder(root):
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

层序遍历（BFS）

def levelOrder(root):
    if not root:
        return []
    res, queue = [], [root]
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res

应用：二叉搜索树验证、最近公共祖先、树的深度等。

---

十一、复杂度速查表

算法	时间复杂度	空间复杂度	稳定性
快速排序	O(n log n) 平均	O(log n)	不稳定
归并排序	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(1)	不稳定
二分查找	O(log n)	O(1)	-
线性查找	O(n)	O(1)	-
双指针（滑动窗口）	O(n)	O(1)	-
回溯	O(2ⁿ) 或 O(n!)	O(n)	-
动态规划	O(n²) 或 O(nW)	O(n) 或 O(W)	-
BFS/DFS	O(V+E)	O(V)	-

---

十二、刷题建议与常用 Python 技巧

1. 刷题顺序：

   • 第一阶段：数组、字符串、哈希表、双指针。
   • 第二阶段：递归、回溯、贪心、动态规划基础。
   • 第三阶段：二叉树、图、高级 DP。

2. Python 技巧：

   • 使用 enumerate 同时获取索引和值。
   • 列表推导式简化循环。
   • collections.deque 实现高效队列。
   • heapq 实现堆（优先队列）。
   • 使用 functools.lru_cache 实现记忆化递归。
   • 设置递归深度：sys.setrecursionlimit(10**6)。

3. 练习平台：LeetCode（推荐《HOT 100》）、牛客网、Codeforces。

掌握上述算法并能手写 Python 实现，足以应对绝大多数基础算法面试题。对于更高级的内容（如字符串匹配、线段树、并查集等），可根据需要深入。