此页面记录了后端架构师应该理解的基本算法。算法是解决问题的分步过程或公式，对于优化系统性能、高效处理数据以及在后端系统中实现核心功能尤为重要。有关这些算法所操作的相关数据结构的信息，请参见数据结构。
算法可以根据其设计方法、应用领域或计算特性进行分类。理解这些分类有助于架构师为特定用例选择合适的算法。
来源: README.md36-61
排序是许多后端系统中的一项基本操作，从数据库操作到搜索功能。不同的排序算法在时间复杂度、空间复杂度和稳定性方面具有不同的特性。
| 算法 | 平均时间复杂度 | 最佳情况 | 最坏情况 | 空间复杂度 | 稳定吗？ | 备注 |
|---|---|---|---|---|---|---|
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 | 实现简单但对于大型数据集效率低下 |
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 是 | 仅对接近有序的数据高效 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 是 | 对小型数据集高效 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 | 实践中非常快，常作为许多库的默认设置 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 | 性能可预测，用于Java的Arrays.sort对象排序 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 | 原地排序，保证O(n log n)时间 |
| 希尔排序 | O(n log n) 到 O(n²) | O(n log n) | O(n²) | O(1) | 否 | 插入排序的改进版 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 是 | 当值范围k相对于n较小时效率高 |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | 是 | 将元素分配到桶中，然后对桶进行排序 |
| 基数排序 | O(d*(n+k)) | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | 是 | 按个位或字符排序 |
来源: README.md37-47
Java提供了几种内置的排序工具
Arrays.sort()：对基本类型使用双轴快速排序，对对象使用改进的归并排序Collections.sort()：使用改进的归并排序算法（TimSort）Comparator接口允许根据特定属性进行灵活排序来源: README.md48-49
二分查找是一种高效的搜索算法，适用于已排序数组，时间复杂度为O(log n)。
来源: README.md48
布隆过滤器是一种节省空间的概率数据结构，用于测试一个元素是否是一个集合的成员。它常用于大规模数据去重。
主要特性
来源: README.md50 README.md511-521
Knuth-Morris-Pratt (KMP) 算法是一种高效的字符串匹配算法，它利用模式串的信息来避免不必要的字符比较。
主要优势
来源: README.md51-52
DFS与BFS比较
| 特征 | DFS | BFS |
|---|---|---|
| 实现 | 使用栈（或递归） | 使用队列 |
| 内存使用 | O(h)，其中 h 为高度 | O(w)，其中 w 为最大宽度 |
| 完整性 | 对于无限图不完整 | 已完成 |
| 最适合 | 路径查找，拓扑排序 | 最短路径（无权重） |
| 用例 | 循环检测，迷宫生成 | 层序遍历，网络路由 |
贪婪算法在每一步做出局部最优选择，以期找到全局最优解。它们适用于以下情况：
常见示例
来源: README.md54
动态规划通过将复杂问题分解为更简单的子问题并存储结果以避免重复计算来解决问题。
常见应用
来源: README.md57 README.md544-545
回溯通过尝试选项并在达到无效状态时“回溯”来探索所有可能的解决方案。
应用程序
来源: README.md55-56
朴素贝叶斯是一种基于贝叶斯定理的分类算法，假设预测器之间相互独立。
应用程序
来源: README.md58 README.md548-551
推荐系统使用算法根据用户的偏好和行为模式向用户推荐相关项目。
实施注意事项
来源: README.md59 README.md557-558
最小生成树（MST）算法在连通的无向图中找到一个边子集，该子集连接所有顶点，且总边权重最小。
应用程序
来源: README.md60
最短路径算法寻找图中节点之间最有效的路径。
应用程序
为生产系统选择算法时，请考虑：
来源: README.md445-447
在基于Java的后端系统中实现算法时
尽可能利用内置实现
Collections.sort()用于集合排序Arrays.sort()用于数组排序Collections.binarySearch()用于已排序列表的搜索对于性能关键的算法，考虑使用多线程能力，例如
ForkJoinPool用于分治算法ExecutorService用于并行处理Stream API用于数据管道操作注意内存影响
来源: README.md504-507