python常用的算法

以下是常用的算法及其详细介绍，包括排序算法、查找算法、基础算法和图算法，同时我也会提到每种数据结构的特性、优缺点及使用场景，并给出示例。

一、排序算法

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它通过重复遍历要排序的数列，比较每对相邻元素并交换它们的位置，使较大的元素逐渐“冒泡”到数列的末尾。

特性：

逐一比较相邻元素，并将较大的元素向后移动。

最坏时间复杂度：O(n²)

最佳时间复杂度：O(n)（当数组已经有序时）

优缺点：

优点：实现简单，适用于小规模数据。

缺点：效率低下，特别是在大规模数据情况下。

示例：

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]  

# 示例  
arr = [64, 34, 25, 12, 22, 11, 90]  
bubble_sort(arr)  
print("排序后的数组:", arr)

2. 选择排序（Selection Sort）

特性：

每次选择最小元素，并将其放到已排序数组的末尾。

最坏时间复杂度：O(n²)

优缺点：

优点：简单易懂，原地排序。

缺点：同样，在大规模数据时效率低下。

示例：

def selection_sort(arr):  
    n = len(arr)  
    for i in range(n):  
        # 假设当前 i 位置是最小值  
        min_idx = i  
        for j in range(i+1, n):  
            if arr[j] < arr[min_idx]:  
                min_idx = j  
        # 交换找到的最小值和当前 i 位置的值  
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  

# 示例  
arr = [64, 25, 12, 22, 11]  
selection_sort(arr)  
print("排序后的数组:", arr)

3. 快速排序（Quick Sort）

特性：

选择一个"基准"元素，将数组分割为两个子数组，再递归对这两个子数组进行排序。

最坏时间复杂度：O(n²)（当数组已经有序时）

最好时间复杂度：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)  

# 示例  
arr = [3, 6, 8, 10, 1, 2, 1]  
sorted_arr = quick_sort(arr)  
print("排序后的数组:", sorted_arr)

4. 归并排序（Merge Sort）

特性：

使用分治法，将数组分解为子数组，递归排序后再合并。

时间复杂度：O(n log n)

优缺点：

优点：稳定排序，适合大的数据集。

缺点：额外空间复杂度较高。

示例：

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  

# 示例  
arr = [38, 27, 43, 3, 9, 82, 10]  
sorted_arr = merge_sort(arr)  
print("排序后的数组:", sorted_arr)

二、查找算法

1. 线性查找（Linear Search）

特性：

顺序遍历数组中的每个元素。

时间复杂度：O(n)

优缺点：

优点：可以用于未排序的数据。

缺点：效率低下。

示例：

def linear_search(arr, target):  
    for i in range(len(arr)):  
        if arr[i] == target:  
            return i  
    return -1  

# 示例  
arr = [10, 20, 30, 40, 50]  
target = 30  
index = linear_search(arr, target)  
print("目标元素的索引:", index)

2. 二分查找（Binary Search）

特性：

在已排序数组中，通过对半查找来定位目标元素。

时间复杂度：O(log n)

优缺点：

优点：效率高，只适用于已排序的数据。

缺点：实现复杂些。

示例：

def binary_search(arr, target):  
    left, right = 0, len(arr) - 1  
    while left <= right:  
        mid = left + (right - left) // 2  # 找到中间索引  
        if arr[mid] == target:  
            return mid  
        elif arr[mid] < target:  
            left = mid + 1  
        else:  
            right = mid - 1  
    return -1  

# 示例  
arr = [2, 3, 4, 10, 40]  
target = 10  
index = binary_search(arr, target)  
print("目标元素的索引:", index)

三、基础算法

1. 递归（Recursion）

特性：

问题的解由小问题的解构成，函数调用自身。

优缺点：

优点：代码简洁，逻辑清晰。

缺点：可能导致栈溢出，效率低于迭代。

示例（阶乘计算）：

def factorial(n):  
    if n == 0 or n == 1:  # 基本情况  
        return 1  
    else:  
        return n * factorial(n - 1)  # 递归调用  

# 示例  
print("5 的阶乘:", factorial(5))

2. 动态规划（Dynamic Programming）

特性：

用于解决具有重叠子问题和最优子结构的问题。

通过保存中间结果避免重复计算。

优缺点：

优点：高效解决多种问题。

缺点：实现复杂，需额外空间存储中间结果。

示例（斐波那契数列）：

def fibonacci(n, memo={}):  
    if n in memo:  # 记忆化  
        return memo[n]  
    if n <= 1:  
        return n  
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)  
    return memo[n]  

# 示例  
print("第10个斐波那契数:", fibonacci(10))

四、图算法

1. 深度优先搜索（Depth-First Search, DFS）

特性：

从一个节点开始，沿着节点的深度探索。

优缺点：

优点：实现简单，用于解决某些特殊问题。

缺点：可能导致栈溢出。

示例：

def dfs(graph, start, visited=None):  
    if visited is None:  
        visited = set()  
    visited.add(start)  
    print(start, end=" ")  # 访问节点  
    for neighbor in graph[start]:  
        if neighbor not in visited:  
            dfs(graph, neighbor, visited)  

# 示例  
graph = {  
    'A': ['B', 'C'],  
    'B': ['D', 'E'],  
    'C': ['F'],  
    'D': [],  
    'E': [],  
    'F': []  
}  
print("深度优先搜索结果:")  
dfs(graph, 'A')

2. 广度优先搜索（Breadth-First Search, BFS）

特性：

从一个节点开始，逐层探索邻接节点。

优缺点：

优点：找到最短路径（在无权图中）。

缺点：需要更多的空间存储队列。

示例：

from collections import deque  

def bfs(graph, start):  
    visited = set()  
    queue = deque([start])  # 使用双端队列实现队列  
    while queue:  
        vertex = queue.popleft()  # 访问队列的左端  
        if vertex not in visited:  
            print(vertex, end=" ")  
            visited.add(vertex)  
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)  

# 示例  
print("\n广度优先搜索结果:")  
bfs(graph, 'A')

3. 最短路径算法（Dijkstra算法）

特性：

用于寻找一个节点到其他所有节点的最短路径。

时间复杂度：O(V²)（V为节点数，使用优先队列可降至O(E log V)）

优缺点：

优点：处理带权图的最短路径问题。

缺点：无法处理负权边。

示例：

import heapq  

def dijkstra(graph, start):  
    # 初始化距离字典  
    distances = {vertex: float('infinity') for vertex in graph}  
    distances[start] = 0  
    priority_queue = [(0, start)]  # (距离, 节点)  
    
    while priority_queue:  
        current_distance, current_vertex = heapq.heappop(priority_queue)  

        # 如果当前距离大于已知距离，跳过  
        if current_distance > distances[current_vertex]:  
            continue  

        for neighbor, weight in graph[current_vertex].items():  
            distance = current_distance + weight  
            
            # 仅在找到更短的距离时更新优先队列和最短路径  
            if distance < distances[neighbor]:  
                distances[neighbor] = distance  
                heapq.heappush(priority_queue, (distance, neighbor))  
    
    return distances  

# 示例图  
graph = {  
    'A': {'B': 1, 'C': 4},  
    'B': {'A': 1, 'C': 2, 'D': 5},  
    'C': {'A': 4, 'B': 2, 'D': 1},  
    'D': {'B': 5, 'C': 1}  
}  

print("\n从 A 到所有其他节点的最短路径:")  
print(dijkstra(graph, 'A'))

其他算法和数据结构

1. 哈希表 (Hash Table)

哈希表是一种用键值对存储数据的结构，支持快速的插入、查找和删除。

特性

时间复杂度：O(1)（平均）

空间复杂度：O(n)

使用场景：快速查找

示例

# 示例：使用字典作为哈希表
hash_table = {}

# 插入数据
hash_table['apple'] = 1
hash_table['banana'] = 2

# 查找数据
print("apple 的值:", hash_table.get('apple'))  # 输出 1

2. 树 (Tree)

树是一种非线性数据结构，由节点组成，适合表示层级关系。

特性

时间复杂度：O(log n)（在平衡树中）

空间复杂度：O(n)

使用场景：表示层级结构，如文件系统等

3. 堆 (Heap)

堆是一种特殊的树形数据结构，用于实现优先队列。

特性

时间复杂度：插入 O(log n)，查找 O(1)

空间复杂度：O(n)

使用场景：任务调度、图算法等

4. AVL树 (AVL Tree)

AVL树是自平衡的二叉搜索树，确保插入和删除操作的复杂度保持在 O(log n)。

5. 红黑树 (Red-Black Tree)

红黑树是一种自平衡的二叉搜索树，允许快速的插入、删除和查找操作。

作者：蜡笔小新星