本文概述了 TheAlgorithms/Python 存储库中的主要算法实现。该存储库包含跨多个领域的 TPY 基础算法的纯 Python 实现，包括排序、搜索、动态规划、机器学习、密码学、数学计算、图算法和字符串处理。
每个算法类别都在专门的子部分中进行了详细介绍
有关这些算法可能使用的数据结构的信息，请参阅 数据结构。有关项目构建系统和配置的详细信息，请参阅 存储库基础设施与 CI/CD。
该存储库将算法分为七个主要类别，每个类别对应一个专门的子部分
来源
存储库中的大多数算法实现遵循一致的模式
来源
该存储库实现了具有不同性能特征的算法，针对不同的用例进行了优化
| 算法 | 函数名称 | 时间复杂度 | 空间复杂度 | 稳定性 | 原地 |
|---|---|---|---|---|---|
| 冒泡排序 | bubble_sort_iterative() | O(n²) | O(1) | 稳定 | 是 |
| 快速排序 | quick_sort() | O(n log n) | O(log n) | 不稳定 | 是 |
| 归并排序 | merge_sort() | O(n log n) | O(n) | 稳定 | 否 |
| 堆排序 | heap_sort() | O(n log n) | O(1) | 不稳定 | 是 |
| 插入排序 | insertion_sort() | O(n²) | O(1) | 稳定 | 是 |
| Shell Sort | shell_sort() | O(n log² n) | O(1) | 不稳定 | 是 |
| 选择排序 | selection_sort() | O(n²) | O(1) | 不稳定 | 是 |
| 二分搜索 | binary_search() | O(log n) | O(1) | 不适用 | 不适用 |
| 线性搜索 | linear_search() | O(n) | O(1) | 不适用 | 不适用 |
| 指数搜索 | exponential_search() | O(log n) | O(1) | 不适用 | 不适用 |
| 问题类型 | 函数/类 | 时间复杂度 | 空间复杂度 | 问题域 |
|---|---|---|---|---|
| 序列优化 | Fibonacci.get() | O(n) | O(n) | 数字序列 |
| 优化 | knapsack() | O(nW) | O(nW) | 资源分配 |
| 子序列 | longest_subsequence() | O(n²) | O(n) | 数组优化 |
| 资源切割 | bottom_up_cut_rod() | O(n²) | O(n) | 资源优化 |
| 矩阵运算 | matrix_chain_multiply() | O(n³) | O(n²) | 矩阵计算 |
| 子串匹配 | longest_common_substring() | O(mn) | O(mn) | 字符串分析 |
| 组合数学 | combination_sum_iv() | O(n²) | O(n) | 计数问题 |
来源
冒泡排序通过重复遍历列表，比较相邻元素，并在顺序错误时交换它们。该存储库提供了迭代和递归实现
来源
快速排序是一种分而治之的算法，它选择一个枢轴元素，围绕它对数组进行分区，然后递归地对子数组进行排序
来源
搜索算法在数据结构中查找目标值的位置。该存储库实现了多种搜索算法
| 算法 | 平均时间复杂度 | 空间复杂度 | 需要排序的输入 | 备注 |
|---|---|---|---|---|
| 二分搜索 | O(log n) | O(1) | 是 | 多种实现（迭代、递归、标准库） |
| 线性搜索 | O(n) | O(1) | 否 | 简单的实现，顺序搜索 |
| 指数搜索 | O(log n) | O(1) | 是 | 适用于无界/无限列表 |
来源
二分查找通过反复将排序数组分成两半，直到找到目标元素或确定其不存在。该存储库提供了多种实现
来源
动态规划通过将复杂问题分解为更简单的子问题来解决。该存储库包含了多种动态规划问题的实现
斐波那契实现使用动态规划来避免重新计算值
该实现将先前计算的值存储在序列列表中，从而可以高效地检索斐波那契数。
来源
图算法解决与图数据结构相关的问题。该存储库包含各种图算法的实现
拓扑排序按顺序排列有向无环图中的节点，以便对于每条有向边 (u, v)，顶点 u 在排序中出现在顶点 v 之前
来源
字符串算法旨在高效地处理和操作字符串。该存储库包含各种与字符串相关的算法的实现
前缀函数（克努特-莫里斯-普拉特算法）计算字符串的每个前缀的最长真前缀（它也是后缀）的长度
来源
算法选择取决于问题特征、数据大小和性能要求
来源
| 实现文件 | 函数名称 | 最佳情况 | 平均情况 | 最坏情况 | Space键 | 备注 |
|---|---|---|---|---|---|---|
bubble_sort.py | bubble_sort_iterative() | O(n) | O(n²) | O(n²) | O(1) | 提前终止优化 |
quick_sort.py | quick_sort() | O(n log n) | O(n log n) | O(n²) | O(log n) | 随机化枢轴 |
merge_sort.py | merge_sort() | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定，分而治之 |
heap_sort.py | heap_sort() | O(n log n) | O(n log n) | O(n log n) | O(1) | 原地堆化 |
insertion_sort.py | insertion_sort() | O(n) | O(n²) | O(n²) | O(1) | 自适应，稳定 |
shell_sort.py | shell_sort() | O(n log n) | O(n log² n) | O(n²) | O(1) | 间隔序列优化 |
selection_sort.py | selection_sort() | O(n²) | O(n²) | O(n²) | O(1) | 始终进行 n² 次比较 |
binary_search.py | binary_search() | O(1) | O(log n) | O(log n) | O(1) | 需要排序的输入 |
binary_search.py | exponential_search() | O(1) | O(log n) | O(log n) | O(1) | 无界搜索 |
linear_search.py | linear_search() | O(1) | O(n) | O(n) | O(1) | 无需排序 |
| 文件 | 函数/类 | 时间复杂度 | 空间复杂度 | 问题规模变量 |
|---|---|---|---|---|
fibonacci.py | Fibonacci.get() | O(n) | O(n) | n = 序列索引 |
knapsack.py | knapsack() | O(nW) | O(nW) | n = 物品，W = 容量 |
knapsack.py | mf_knapsack() | O(nW) | O(nW) | 内存函数变体 |
rod_cutting.py | bottom_up_cut_rod() | O(n²) | O(n) | n = rod 长度 |
rod_cutting.py | top_down_cut_rod() | O(n²) | O(n) | 记忆化递归 |
longest_increasing_subsequence.py | longest_subsequence() | O(n²) | O(n) | n = 数组长度 |
matrix_chain_multiplication.py | matrix_chain_multiply() | O(n³) | O(n²) | n = 矩阵数量 |
longest_common_substring.py | longest_common_substring() | O(mn) | O(mn) | m, n = 字符串长度 |
combination_sum_iv.py | combination_sum_iv_dp_array() | O(target × len(array)) | O(target) | 动态规划变体 |
viterbi.py | viterbi() | O(T × N²) | O(T × N) | T = 观测值，N = 状态 |
来源
存储库中的算法实现遵循以下标准
文档：每种算法都包含详细的文档字符串，内容包括
测试：实现包括
代码质量：实现符合
来源