常见算法与应用

什么是算法？

算法是解决特定问题的一组有序、明确、有限的操作步骤。一个好的算法不仅要正确，还应具备较高的效率。

如何评价一个算法？

评价算法的常用指标有：

• 时间复杂度：算法运行所需时间随输入规模变化的增长趋势。
• 空间复杂度：算法执行过程中占用的内存空间随输入规模的变化趋势。

通常采用大 O 记法（Big O Notation）来表示渐近复杂度，即在输入规模足够大的情况下，时间/空间的增长速度。

常见时间复杂度级别及示例

• O(1)、O(log n)、O(n) 属于高效算法；
• O(n²) 及以上的复杂度，适用于数据量小或可接受较长计算时间的场景；

![[res/Pasted image 20250604223425.png]]

![[res/Pasted image 20240112000803.png]]

排序算法

简单选择排序

标准选择排序：在一轮循环比较中，只找最小值的位置，最后只交换一次。

"""
简单选择排序思路：
- 将第一个元素和后面的元素逐一比较，把数值最小的元素和第一个置换，否则不置换
- 将第二个元素和后面的元素逐一比较，把数值最小的元素和第二个置换，否则不置换
- 依次迭代
"""
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i  # 假设当前 i 是最小的
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            
                
data = [64, 25, 12, 22, 11]
selection_sort(data)
print("简单选择排序后：", data)

冒泡排序

"""
冒泡排序思路：

关键：通过相邻元素两两比较，将最大值不断“冒泡”到序列末尾

循环机制：
- 外层循环：控制趟数，总共进行 n - 1 趟排序（n 是列表长度）
- 内层循环：控制每一趟比较的次数，第 i 趟最多需要比较 n - 1 - i 次
"""


def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False     # 用于优化：如果本轮没有发生交换，说明已排序好
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 如果一轮比较中没有发生交换，说明数组已排序
            break


data = [64, 25, 12, 22, 11]
bubble_sort(data)
print("冒泡排序后：", data)

动态过程：

![[res/bubbleSort.gif]]

搅拌排序(双向冒泡)

搅拌排序的原理，通过反复从左到右和从右到左的遍历，逐步地将最小和最大的元素推到正确的位置。

请注意，如果在某一轮中没有发生任何交换，算法就会提前结束，因为数组已经有序。

"""
正常冒泡：每次都从左向右比较并将最大值移到右边

搅拌排序：双向冒泡

- 从左到右一趟，把最大的元素“冒泡”到末尾；
- 然后从右到左一趟，把最小的元素“冒泡”到前面；
- 每轮循环后，左右边界向中间收缩，直到没有交换发生

每一轮中如果没有交换，说明已排序，可提前结束
"""


def cocktail_shaker_sort(arr):
    n = len(arr)
    start = 0
    end = n - 1
    swapped = True

    while swapped:
        swapped = False

        # 从左到右冒泡，将最大值移到末尾
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True

        # 如果这一趟没有发生交换，说明已排序好
        if not swapped:
            break

        end -= 1
        swapped = False

        # 从右向左冒泡，将最小值移到开头
        for i in range(end, start, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True

        if not swapped:
            break

        start += 1


data = [64, 25, 12, 22, 11]
cocktail_shaker_sort(data)
print("搅拌排序后：", data)

归并排序

归并排序的核心思想（分治法）：

• 分解：将列表从中间拆分成左右两个子列表
• 递归排序：对两个子列表分别排序
• 合并：将两个有序子列表合并成一个有序列表

合并两个有序列表操作：

• 两个有序列表 left 和 right 各自维护一个指针
• 比较 left[i] 和 right[j]，谁小就放到结果列表中，指针向后移动
• 如果一个列表先用完，则把另一个列表的剩余部分直接追加到结果中

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):
    merged = []
    i = j = 0

    # 比较并合并两个有序列表
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # 追加剩余元素（某个列表已经用完）
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

data = [64, 25, 12, 22, 11]
sorted_data = merge_sort(data)
print("归并排序后：", sorted_data)

动态过程： ![[res/mergeSort.gif]]

快速排序

快速排序使用分治法策略，把一个序列分成较小和较大的两个子序列，然后递归地排序两个子序列。

步骤思路：

• 选取基准（pivot）；
• 分区（小于基准放左边，大于的放右边）；
• 分别递归排序两个子列表；
• 子序列为空或只有一个元素时递归终止。

def quick_sort(arr):
    """快速排序入口函数，使用分治法"""
    def _quick_sort(arr, start, end):
        if start < end:
            # 获取分区后 pivot 的最终位置
            pivot_index = partition(arr, start, end)
            # 递归排序左边部分
            _quick_sort(arr, start, pivot_index - 1)
            # 递归排序右边部分
            _quick_sort(arr, pivot_index + 1, end)

    def partition(arr, start, end):
        """对 arr[start:end+1] 进行分区，返回基准位置"""
        pivot = arr[end]  # 选取最后一个元素作为基准
        i = start - 1  # 小于基准的元素的最后位置
        for j in range(start, end):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        # 将基准元素放到正确位置
        arr[i + 1], arr[end] = arr[end], arr[i + 1]
        return i + 1

    _quick_sort(arr, 0, len(arr) - 1)
    return arr


if __name__ == "__main__":
    data = [64, 25, 12, 22, 11]
    sorted_data = quick_sort(data)
    print("快速排序结果：", sorted_data)

查找算法

顺序查找

顺序查找（Sequential Search）是最基础的查找算法之一，也叫线性查找。它逐个检查列表中的元素，直到找到目标值或遍历完整个列表。

def sequential_search(arr, target):
    """
    顺序查找（线性查找）
    :param arr: 可迭代对象（列表、元组等）
    :param target: 查找的目标值
    :return: 如果找到，返回索引；否则返回 -1
    """
    for index, value in enumerate(arr):
        if value == target:
            return index

    return -1


data = [64, 25, 12, 22, 11]
target = 22

result = sequential_search(data, target)
if result != -1:
    print(f"找到了目标值 {target}，索引为：{result}")
else:
    print(f"未找到目标值 {target}")

折半查找

折半查找（Binary Search）是一种高效的查找算法，适用于已排序的序列。相比顺序查找的线性效率，折半查找的时间复杂度为 O(log n)，在处理大数据量时更为高效。

折半查找通过不断将查找范围 对半缩小，直到找到目标元素或范围为空。

def binary_search(arr, target):
    """
    折半查找
    :param arr: 有序列表
    :param target: 要查找的目标值
    :return: 若找到返回索引，否则返回 -1
    """
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

    return -1


data = [64, 25, 12, 22, 11]
target = 22
result = binary_search(data, target)

if result != -1:
    print(f"找到了目标值 {target}，索引为：{result}")
else:
    print(f"未找到目标值 {target}")

经典问题与算法

穷举法

穷举法又称为暴力破解法，通过列举所有可能的情况并逐一验证，直到找到符合条件的解。

特点：简单直接，适用于问题规模较小或解空间有限的场景，但效率低。

示例：解决“百钱买百鸡”问题

场景：

• 公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只
• 用 100 元买 100 只鸡，问公鸡/母鸡/小鸡各多少只

这个问题的关键在于满足两个约束条件：

• 总钱数为 100 元：5x + 3y + z/3 == 100
• 总鸡数为 100 只：x + y + z == 100

可知：

• x 最大不能超过 100 // 5 = 20
• y 最大不能超过 100 // 3 = 33
• z 可以由 100 - x - y 推出，所以无需再循环
• 提前判断 z % 3 == 0，再判断是否满足钱数条件

def main():
    print("公鸡\t母鸡\t小鸡")
    for x in range(21):  # 公鸡最多20只
        for y in range(34):  # 母鸡最多33只
            z = 100 - x - y
            if z >= 0 and z % 3 == 0:  # 小鸡数量必须是3的倍数
                total_cost = 5 * x + 3 * y + z // 3
                if total_cost == 100:
                    print(f"{x}\t{y}\t{z}")


if __name__ == "__main__":
    main()

示例2：解决“五人分鱼”问题

场景：

五个人 A、B、C、D、E 合伙捕鱼，晚上睡觉时鱼堆在一起。
第二天早上他们依次醒来，每次都：

1. 把鱼分成 5 份；
2. 扔掉 1 条多余的鱼；
3. 拿走自己那份；
4. 剩下的继续留给后面的人。

问：最少一共捕了多少条鱼才能满足每个人都可以这么操作？

思路：

这是一个经典的穷举 + 数学反推问题：

• 从最小可能的鱼数 fish = 1 开始；
• 对每一个尝试的 fish：
  • 模拟五次分鱼过程（五个人）；
  • 每轮必须满足 (total - 1) % 5 == 0，即减 1 后能整除 5；
  • 如果 5 轮都满足条件，那这个数就是答案；
  • 为了加速搜索，每次 fish += 5（因为必须减去 1 后能整除 5）；

def is_vaild(total):
    for _ in range(5):
        if (total - 1) % 5 != 0:
            return False
        total = (total - 1) // 5 * 4
    return True


def find_min_fish():
    fish = 1
    while True:
        if is_vaild(fish):
            return fish
        fish += 5  # 优化搜索步长


if __name__ == "__main__":
    total_fish = find_min_fish()
    print("最少鱼数为:", total_fish)

贪心法

贪婪法：在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。

不回溯、不考虑后果，适用于满足“贪心选择性质”和“最优子结构”的问题。

示例：0-1 背包问题

场景：假设小偷有一个背包，最多能装 20 公斤赃物，他闯入一户人家，发现如下表所示的物品。
很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。

class Thing:
    """物品类，包含名称、价格、重量及单位价值（价格/重量）"""

    def __init__(self, name, price, weight):
        self.name = name
        self.price = price
        self.weight = weight

    @property
    def value(self):
        return self.price / self.weight


def input_thing():
    """读取一行物品数据并返回元组 (name, price, weight)"""
    name, price, weight = input().split()
    return name, int(price), int(weight)


def main():
    # 读取背包最大承重 & 物品数量
    max_weight, num_of_things = map(
        int, input("请输入背包容量和所有物品数量（用空格分隔）：").split())

    all_things = []
    print("请输入每件物品的信息（名称 价格 重量）")
    for _ in range(num_of_things):
        all_things.append(Thing(*input_thing()))

    # 按单位价值排序（贪心策略：优先选单位价值高的）
    all_things.sort(key=lambda x: x.value, reverse=True)

    total_weight = 0
    total_price = 0
    selected = []

    # 贪婪选择物品
    for thing in all_things:
        if total_weight + thing.weight <= max_weight:
            selected.append(thing)
            total_weight += thing.weight
            total_price += thing.price

    print("\n小偷拿走了这些物品：")
    for item in selected:
        print(f"- {item.name}（价格：{item.price}，重量：{item.weight}）")
    print(f"\n总重量：{total_weight} kg")
    print(f"总价值：{total_price} 美元")


if __name__ == "__main__":
    main()

信息输入：

请输入背包容量和所有物品数量（用空格分隔）：20 6
请输入每件物品的信息（名称 价格 重量）
电脑 200 20
收音机 20 4
钟 175 10
花瓶 50 2
书  10 1
油画 90 9

输出结果：

小偷拿走了这些物品：
- 花瓶（价格：50，重量：2）
- 钟（价格：175，重量：10）
- 书（价格：10，重量：1）
- 收音机（价格：20，重量：4）

总重量：17 kg
总价值：255 美元

分治法

将复杂问题分解成若干个相同或类似的子问题，递归求解子问题后，再合并其解得到原问题的解。

分治法是递归思想的核心体现。

示例：归并排序、快速排序（[[#快速排序|见上文]]）、二分查找、Strassen矩阵乘法等。

回溯法

回溯法又称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先条件并不优或达不到目标时，就退回一步重新选择。

回溯法的本质就是 尝试 + 撤销，是一种系统化搜索所有可能解的方式，非常适合组合、排列、路径问题等。

示例：骑士巡逻问题

场景：

骑士巡逻（Knight’s Tour）：在国际象棋棋盘上，骑士从某一格开始，按照规则移动（L形），尝试走遍棋盘的所有格子，且每格只走一次。

SIZE = 5  # 棋盘大小
total = 0  # 全局变量统计走法总数
show_solution = False  # 是否打印每种走法

# 马可以走8个方向（行偏移，列偏移）
DIRECTIONS = [
    (-2, -1), (-2, +1),
    (+2, -1), (+2, +1),
    (-1, -2), (-1, +2),
    (+1, -2), (+1, +2)
]


def print_board(board):
    """打印棋盘"""
    for row in board:
        print(''.join(str(col).center(4) for col in row))
    print()


def patrol(board, row, col, step=1):
    """递归回溯查找所有走法"""
    global total
    # 边界检测和当前位置是否已访问
    if 0 <= row < SIZE and 0 <= col < SIZE and board[row][col] == 0:
        board[row][col] = step  # 标记当前格为第 step 步
        if step == SIZE * SIZE:
            total += 1
            if show_solution:
                print(f"第 {total} 种走法：")
                print_board(board)
        else:
            # 尝试马走的8个方向
            for dx, dy in DIRECTIONS:
                patrol(board, row + dx, col + dy, step + 1)
        board[row][col] = 0  # 回溯：撤销当前位置


def main():
    board = [[0 for _ in range(SIZE)] for _ in range(SIZE)]
    patrol(board, SIZE - 1, SIZE - 1)  # 起点在右下角
    print(f"\n共有 {total} 种走法")


if __name__ == "__main__":
    main()

动态规划

动态规划是一种将原问题划分为 重叠子问题 的算法策略，它通过 保存子问题的解（使用记忆法或表格法）来避免重复计算，从而显著降低时间复杂度。

将原问题划分为重叠子问题，通过保存子问题的解（记忆化或表格法）避免重复计算，从而降低时间复杂度。

动态规划通常适用于满足以下两个条件的问题：

• 最优子结构 -- 原问题的最优解可以有子问题的最优解组合而成。
• 子问题重叠性 -- 原问题在递归求解过程中会重复计算相同的子问题。

示例：解决最大子数组和的问题（Kadane 问题）

问题描述：

给定一个整数列表，可能包含正数、负数或 0，找出其中 连续子列表的最大和。连续子列表指的是索引连续的元素组成的子列表。

算法思路：

定义两个变量：

• partial：以当前位置结尾的最大连续子数组的和
• overall：目前为止所有位置中遇到的最大子数组的和

状态转移公式：

• partial = max(nums[i], partial + nums[i]，表示要么从当前位置重新开始，要么继续之前的子数组
• overall = max(overall, partial)

时间复杂度：O(N) -- 只需遍历一遍列表即可

def max_subarray_sum(nums):
    """
    使用动态规划（Kadane算法）寻找最大连续子数组和。
    :param nums: List[int], 整数列表
    :return: int,最大连续子数组的和
    """
    if not nums:
        return 0  # 空列表返回 0

    # 初始化两个变量
    partial = overall = nums[0]

    for i in range(1, len(nums)):
        partial = max(nums[i], partial + nums[i])
        overall = max(overall, partial)

    return overall


if __name__ == "__main__":
    # 输入格式：空格分隔的整数
    nums = list(map(int, input("请输入整数序列，以空格分隔：\n").split()))
    result = max_subarray_sum(nums)
    print("最大子数组和为：", result)