Python算法入门教程

算法是计算机科学的核心，是解决问题的步骤和方法。本文将介绍常见的 Python 算法，帮助你掌握算法思维和实现技巧。

算法概述

算法是一组有穷的规则，用于解决特定问题。一个好的算法应具备：

• 正确性：能正确解决问题
• 可读性：易于理解和维护
• 效率：时间复杂度和空间复杂度低
• 健壮性：能处理异常情况

排序算法

冒泡排序

冒泡排序通过重复遍历列表，比较相邻元素并交换位置：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        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

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

选择排序

选择排序每次从未排序部分选出最小元素放到已排序部分末尾：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

快速排序

快速排序采用分治思想，通过选择基准元素将数组分成两部分：

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([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

归并排序

归并排序将数组分成两半，分别排序后合并：

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

查找算法

线性查找

线性查找逐个检查数组元素：

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

arr = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(arr, 25))  # 2

二分查找

二分查找要求数组有序，每次将搜索范围缩小一半：

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

arr = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(arr, 25))  # 3

递归算法

递归是函数调用自身的编程技巧。

阶乘计算

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

斐波那契数列

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

print(fibonacci(10))  # 55

# 优化：使用记忆化
memo = {}
def fib_memo(n):
    if n in memo:
        return memo[n]

动态规划

动态规划将复杂问题分解为子问题，保存子问题的解避免重复计算。

背包问题

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

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

最长公共子序列

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)].
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs('ABCBDAB', 'BDCAB'))  # 4

图算法

广度优先搜索

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited

graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E']}

深度优先搜索

def dfs(graph, start, visited=None):
    if visited is None:
        visited = []
    visited.append(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

print(dfs(graph, 'A'))

算法复杂度分析

算法复杂度分为时间复杂度和空间复杂度：

算法	平均时间复杂度	空间复杂度
冒泡排序	O(n²)	O(1)
选择排序	O(n²)	O(1)
快速排序	O(n log n)	O(log n)
归并排序	O(n log n)	O(n)
二分查找	O(log n)	O(1)

总结

本文介绍了常见的 Python 算法：

• 排序算法：冒泡排序、选择排序、快速排序、归并排序
• 查找算法：线性查找、二分查找
• 递归算法：阶乘、斐波那契数列
• 动态规划：背包问题、最长公共子序列
• 图算法：广度优先搜索、深度优先搜索

算法学习是一个循序渐进的过程，建议多做练习，理解每种算法的原理和适用场景。