python 经典算法案例

排序算法

1. 冒泡排序

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. 选择排序

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

1. 插入排序

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

1. 快速排序

def quicksort(arr):
    # 如果数组长度小于等于1，说明已经有序，直接返回
    if len(arr) <= 1:
        return arr

    # 选择一个基准值（pivot），这里选择了数组中间位置的元素
    pivot = arr[len(arr) // 2]

    # 将所有比基准值小的元素放入 left 列表
    left = [x for x in arr if x < pivot]
    
    # 将所有与基准值相等的元素放入 middle 列表
    middle = [x for x in arr if x == pivot]
    
    # 将所有比基准值大的元素放入 right 列表
    right = [x for x in arr if x > pivot]

    # 对 left 和 right 列表递归调用 quicksort 函数，并将结果拼接起来
    # 最终的结果是先排好序的 left 列表 + 相等的 middle 列表 + 排好序的 right 列表
    return quicksort(left) + middle + quicksort(right)

# 测试函数
print(quicksort([3,6,8,10,1,2,1]))  # 输出: [1, 1, 2, 3, 6, 8, 10]

 参考：排序算法之 快速排序 及其时间复杂度和空间复杂度 - 酷酷的排球 - 博客园

1. 归并排序

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 list(merge(left, right))

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left or right)
    return result

搜索算法

1. 二分查找

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

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

1. 广度优先搜索 (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)
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited