python常用算法

# 示例代码：快速排序算法（Quick Sort）

def quick_sort(arr):
    # 如果数组长度小于等于1，直接返回数组（递归终止条件）
    if len(arr) <= 1:
        return arr
    else:
        # 选择基准元素
        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)

# 示例代码：二分查找算法（Binary Search）

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
    # 如果未找到目标值，返回-1
    return -1

# 示例代码：深度优先搜索（DFS）

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    # 标记当前节点为已访问
    visited.add(start)
    print(start)
    # 遍历相邻节点
    for next_node in graph[start] - visited:
        dfs(graph, next_node, visited)
    return visited

# 示例代码：广度优先搜索（BFS）

from collections import deque

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

# 示例代码：动态规划求解斐波那契数列

def fibonacci(n, memo={}):
    # 检查是否已经计算过该值
    if n in memo:
        return memo[n]
    # 基本情况
    if n <= 2:
        return 1
    # 递归计算并存储结果
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

# 示例代码：冒泡排序（Bubble Sort）

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

解释说明：

1. 快速排序（Quick Sort）：

   • 快速排序是一种基于分治思想的排序算法。它通过选择一个基准元素，将数组分为三部分：小于基准的元素、等于基准的元素和大于基准的元素，然后递归地对左右两部分进行排序。

2. 二分查找（Binary Search）：

   • 二分查找适用于已排序的数组。它通过不断缩小查找范围来高效地找到目标值。每次查找时，将查找范围减半，直到找到目标值或确定不存在。

3. 深度优先搜索（DFS）：

   • DFS 是一种用于遍历图或树的算法。它从起始节点开始，尽可能深入地探索每个分支，直到无法继续为止，然后回溯到上一个节点继续探索其他分支。

4. 广度优先搜索（BFS）：

   • BFS 也是一种用于遍历图或树的算法。它从起始节点开始，逐层向外扩展，先访问离起始节点最近的节点，再逐步扩展到更远的节点。

5. 动态规划求解斐波那契数列：

   • 动态规划通过保存子问题的解来避免重复计算，从而提高效率。在这个例子中，我们使用字典 memo 来存储已经计算过的斐波那契数，以减少重复计算。

6. 冒泡排序（Bubble Sort）：

   • 冒泡排序是一种简单的排序算法，它通过多次遍历数组，每次将相邻的两个元素进行比较和交换，使得较大的元素逐渐“冒泡”到数组的末尾。