数据结构与算法

一、数据结构相关算法
针对不同类型的数据结构,对应专属的操作算法与典型应用场景。
1. 线性结构
-
数组与链表:是最基础的线性结构,核心操作包括反转、环检测、节点删除、归并、深拷贝、旋转翻转等;快慢指针、二分查找是常用解题技巧。
-
栈与队列:栈用于后进先出场景(如括号匹配),队列用于先进先出场景;单调栈、单调队列、双端队列、最小栈、循环队列是经典优化变种;优先级队列、延迟队列、阻塞 / 无锁队列是工程中常用的扩展实现。
2. 字符串算法
专门面向文本处理、信息检索场景:
-
匹配与搜索:KMP、Rabin-Karp、BM、Sunday 是经典单模式匹配算法;字典树 (Trie)、AC 自动机、后缀自动机用于多模式匹配;双数组 Trie、回文自动机、Shift-Or、Two-Way 算法是进阶优化实现。
-
处理与分析:字符串哈希、Manacher 算法、后缀数组、LCP 数组用于字符串特征提取与子串统计;SA-IS 是线性时间后缀数组构造算法,基于诱导排序实现,实际性能优异、实现相对简洁;还包括字符串压缩、最小表示法、编辑距离计算等方向。
3. 树结构
树是层次化数据的核心组织方式:
-
二叉树遍历:前序、中序、后序、层序是基础遍历方式;Morris 遍历可实现 O (1) 空间复杂度的遍历;还包括序列化与反序列化、树的直径计算等常用操作。
-
二叉搜索树 (BST):基础操作包括查找、插入、删除;红黑树、AVL 树、Treap、伸展树、替罪羊树是自平衡 BST 的不同实现,通过旋转 / 重构维持查询效率。
-
堆:是完全二叉树的典型应用,核心操作包括堆化、Top-K 问题求解;斐波那契堆、配对堆、二项堆、区间堆是进阶堆结构,在合并、降键等操作上性能更优。
-
并查集 (DSU):用于动态连通性维护,核心优化是路径压缩 + 按秩合并;扩展包括带权并查集、可持久化并查集。
4. 图结构
图用于表达实体间的关联关系,是社交网络、路径规划的核心模型。
-
图的遍历:深度优先搜索 (DFS)、广度优先搜索 (BFS) 是基础;双向 BFS、迭代加深 DFS、A启发式搜索、IDA、D* Lite 是优化与启发式遍历算法。
-
最小生成树:Prim 算法、Kruskal 算法、Boruvka 算法是经典实现,用于求解无向图的最小权连通子图。
-
最短路径:堆优化 Dijkstra、Bellman-Ford、SPFA 用于单源最短路径;Floyd-Warshall、Johnson 算法用于多源最短路径。
-
拓扑排序:Kahn 算法、DFS 逆序法用于有向无环图 (DAG) 的节点排序;可扩展动态拓扑更新、环定位能力。
-
关键路径:基于 AOE 网计算任务的最早 / 最晚完成时间,识别关键活动,用于工程调度场景。
5. 哈希与索引结构
-
散列表:通过哈希函数实现快速查找,冲突解决包括链地址、开放寻址、布谷鸟哈希等方案;一致性哈希、可扩展哈希用于分布式存储场景。
-
倒排索引:是搜索引擎的核心结构,由 Term 词典与倒排列表构成,支持 BM25 相关性评分与倒排链压缩。
-
位图:BitMap、Roaring Bitmap 用于海量整数的快速去重、集合运算,空间效率极高。
6. 高级树结构算法
面向数据库、空间索引、存储引擎等专业场景:
-
多路查找树:B 树、B + 树、B * 树是数据库索引的核心结构,适配磁盘 IO 的读写特性。
-
空间划分树:k-d 树、R 树、球树 (Ball-Tree)、VP 树用于多维空间数据的索引与近邻查询。
-
日志结构树:LSM 树、TSM 树是存储引擎的核心写入优化结构,通过批量写入提升写性能,代表应用如 RocksDB、ClickHouse。
-
密码学树:默克尔树、默克尔前缀树 (MPT)、稀疏默克尔树用于区块链、密码学场景的数据完整性校验。
7. 进阶图算法
面向复杂图问题的专业算法:
-
网络流:Ford-Fulkerson、Dinic、ISAP、HLPP 用于最大流求解;Stoer-Wagner 算法用于全局最小割;最小费用最大流、上下界网络流是扩展应用场景。
-
二分图匹配:匈牙利算法、Hopcroft-Karp 算法是基础匹配算法;KM 算法用于带权二分图匹配;可延伸至最小点覆盖、最大独立集等问题。
-
强连通分量:Tarjan、Kosaraju、Gabow 算法用于求解强连通分量,可通过缩点将图重构为 DAG;2-SAT 是典型应用。
-
图的连通性:双连通分量(点 / 边)、Link-Cut Tree、k – 连通性计算用于动态 / 静态连通性分析。
-
特殊图算法:包括二分图判定、DAG 最长路径、树的重心与直径、LCA(最近公共祖先)的倍增 / 树链剖分实现等。
8. 流式数据结构
面向无法全量加载的流式大数据,通过概率数据结构实现近似统计:
-
基数统计:HyperLogLog、Adaptive HyperLogLog 用于近似基数统计,空间效率极高。
-
频率统计:Count-Min Sketch、HeavyKeeper、Misra-Gries 算法用于近似频度统计,识别热点数据。
-
抽样算法:蓄水池抽样实现流数据的等概率抽样,支持分层、加权等扩展形式。
9. 多项式与傅里叶变换
FFT 快速傅里叶变换、NTT 数论变换、FWT 快速沃尔什变换用于多项式乘法、卷积计算,可将多项式运算的时间复杂度从 O (n²) 降至 O (nlogn),同时支持快速多项式插值。
二、基础算法
基础算法是算法体系的底层基石,覆盖排序、查找两类核心操作,以及通用的解题技巧范式。
1. 排序算法
排序是将无序数据按规则重排的基础操作,按实现原理分为三大类:
-
比较类排序:通过元素两两比较确定顺序,理论时间复杂度下界为 O (nlogn)。
-
基础排序:冒泡、插入、选择排序是入门级实现,时间复杂度多为 O (n²);希尔排序是插入排序的分组优化版本;鸡尾酒排序、梳排序是冒泡排序的双向遍历、步长优化变种;折半插入排序通过二分查找优化插入位置的查找过程。
-
高效排序:快速排序基于分治思想,双轴快排通过双基准值提升分区效率;归并排序是稳定的分治排序;堆排序依托堆结构实现 O (nlogn) 的稳定复杂度。工业级优化算法包括:Pdqsort(模式消除快排)融合快排、堆排与插入排序,可避免快排最坏情况,被 Go、Rust 等语言标准库采用;BlockSort(块排序)是原地稳定排序,内存效率高且具备自适应性;GrailSort 可在常数额外空间内实现稳定排序,适配内存受限场景;OrsonSort 为自适应混合排序,可根据数据分布动态调整策略。
-
-
非比较类排序:不通过元素比较,依托数值特征排序,适用于值域有限的整数场景,理想时间复杂度可达 O (n)。核心包括计数排序、桶排序、基数排序(分最高位优先 MSD、最低位优先 LSD 两种实现);优化方向包括 SIMD 向量化加速、负数值域适配、链式存储优化等。
-
外部 / 分布式排序:面向数据量超内存的场景或分布式集群。多路归并、锦标赛排序、置换选择排序是传统外部排序核心;MapReduce 排序、Flink 流式排序、Hive 分桶排序是大数据生态下的分布式排序实现。
2. 查找算法
查找是从数据集合中定位目标元素的操作,按策略与数据结构分为两类:
-
基础查找:顺序查找适用于无序数据,时间复杂度 O (n);二分查找、斐波那契查找、插值查找、三分查找均基于有序数据的分治思想,通过缩小搜索区间提升效率,时间复杂度 O (logn),其中三分查找专门用于单峰函数的极值求解。
-
高级查找:哈希查找通过哈希函数直接映射存储位置,平均复杂度 O (1);跳表、红黑树通过层级化结构维持有序查找的高效性;k-d 树用于多维空间数据的近邻查找;插值查找可通过边界优化避免极端数据分布下的性能退化。
3. 基础技巧
是各类算法通用的实现思路与优化手段:递归与分治、迭代、模拟是最基础的实现范式;双指针、前缀和 / 差分、滑动窗口、区间合并是数组与区间类问题的核心技巧;摩尔投票法用于线性空间求解众数;原地哈希可实现 O (1) 空间的元素标记;贪心构造用于局部最优可推导全局最优的场景。
三、策略算法
策略算法是面向复杂问题的通用求解范式,通过特定决策策略缩小解空间、推导最优解。
1. 动态规划 (DP)
核心思想是将问题拆解为重叠子问题,存储子问题解避免重复计算,核心是状态定义与状态转移方程。
-
基础类型:线性 DP、区间 DP、树形 DP、状态压缩 DP、数位 DP、概率 DP、博弈论 DP(如 Nim 游戏)是主流分类;插头 DP 是基于轮廓线的连通性状压 DP,专门解决网格回路、路径类问题;基环树 DP 针对带单环的树结构,通过破环为树结合环形 DP 求解;换根 DP 通过二次扫描法,以 O (n) 复杂度计算所有节点作为根的 DP 结果。
-
优化技巧:状态压缩、滚动数组用于空间优化;单调队列优化、斜率优化、四边形不等式优化、决策单调性优化用于降低转移的时间复杂度;矩阵快速幂、前缀和可分别优化线性 DP 与多维 DP 的转移过程。
-
经典问题:背包系列(0-1 背包、完全背包、多重背包、分组背包、二维费用背包、有依赖的背包)是 DP 最经典的题型;LCS(最长公共子序列)、LIS(最长上升子序列)、编辑距离、最长回文子序列、最大子段和等也是高频应用场景。
2. 贪心算法
每一步做出局部最优选择,最终推导全局最优解,需满足贪心选择性质与最优子结构两个核心前提。
- 核心应用:活动选择问题、霍夫曼编码、最小生成树(Prim/Kruskal)、分数背包、区间覆盖是经典场景;带截止时间的任务调度、文件压缩是实际工程应用;同时存在大量贪心不成立的反例,需通过严格证明保证算法正确性。
3. 回溯算法
本质是深度优先的暴力枚举,通过 “尝试 – 回退” 的方式遍历所有可行解,适合排列、组合、路径类约束问题。
-
经典问题:组合与排列、N 皇后、数独求解、子集生成、单词搜索是基础题型;正则表达式匹配、括号生成、岛屿 DFS 是扩展场景。
-
优化技巧:可行性剪枝、最优性剪枝可提前排除无效路径;记忆化回溯存储子问题结果避免重复计算;双向回溯从问题两端同时搜索缩小范围;调整搜索顺序可提升剪枝触发效率。
4. 分支限界
以广度优先或最佳优先方式搜索解空间,通过限界函数剪掉不可能得到最优解的分支,常用于组合优化问题。核心包括优先队列式分支限界、动态界值更新,典型应用如 TSP 问题近似解、0-1 背包的分支限界优化。
5. 随机化算法
引入随机因子优化算法性能或正确性:随机快速排序通过随机选择基准避免最坏情况;蒙特卡洛算法以概率保证正确性、运行时间确定;拉斯维加斯算法保证结果正确、运行时间随机;舍伍德算法用于消除最坏情况与输入分布的关联。
四、数学与计算几何
是算法的理论基础,为复杂问题提供数学支撑与高效求解方法。
1. 数论算法
围绕整数性质展开,是密码学、组合优化的核心工具。
-
基础:最大公约数 (GCD)/ 最小公倍数 (LCM)、扩展欧几里得算法、贝祖定理是数论基石。
-
素数相关:埃氏筛、线性筛用于批量筛选素数;米勒 – 拉宾是概率性素数判定算法;Pollard-Rho 用于大数质因数分解;区间筛用于大区间内的素数筛选。
-
幂与模运算:快速幂、快速乘用于大数幂运算的高效计算与溢出规避;模逆元、中国剩余定理、BSGS 算法用于各类同余方程的求解。
2. 组合数学
研究离散对象的计数与排列规律:排列组合计算、卡特兰数应用、容斥原理是基础内容;卢卡斯定理用于大组合数取模;斯特林数、贝尔数是进阶组合计数工具,通常通过递推预处理实现快速查询。
3. 计算几何
处理平面 / 空间中的几何对象计算,是图形学、地理信息系统的底层支撑。
-
基础:向量点积 / 叉积是核心工具,用于点线面关系判定、距离与面积计算。
-
核心算法:Graham 扫描、Andrew 算法用于求解平面点集的凸包;分治法求解最近点对;旋转卡壳用于求解最远点对;还包括线段相交判定、多边形凹凸性判断、Voronoi 图、三维凸包等进阶内容。
五、工程化与性能优化
聚焦算法与数据结构在工业场景的落地优化,兼顾理论复杂度与实际运行性能。
1. 数据结构选型原则
选型需结合时间 / 空间权衡、读写比例、数据规模,同时适配 CPU/GPU 等硬件架构;通过复杂度分析、Amdahl 定律评估并行加速比,辅助选型决策。
2. 性能优化技巧
-
基础优化:内存对齐、缓存友好设计(利用时间 / 空间局部性)、SIMD/AVX 向量化编程,充分利用 CPU 硬件特性。
-
进阶优化:批量操作、延迟计算、写时复制 (COW)、零拷贝技术、软硬件预取,减少冗余计算与数据拷贝开销。
-
内存管理:内存池、对象复用降低内存分配与回收开销;通过专业工具检测内存泄漏。
3. 并发与分布式优化
并发场景下,无锁数据结构、细粒度分段锁、乐观 / 悲观锁选型用于平衡性能与数据一致性;分布式场景中,Raft/Paxos 等一致性算法、分布式锁、数据分片与负载均衡是核心技术。
六、跨领域应用与前沿技术
数据结构与算法是各计算机领域的底层支撑,延伸至 AI、区块链、量子计算等多个前沿方向。
1. 人工智能
-
神经网络:卷积层依赖张量运算,循环层依托队列 / 栈结构,Transformer 的注意力机制核心是矩阵运算。
-
强化学习:经验回放池基于环形缓冲区实现,优先级经验回放依托堆结构优化采样效率。
2. 机器学习基础算法
-
监督学习:线性回归、逻辑回归、支持向量机 (SVM)、决策树与随机森林、K – 近邻算法 (KNN) 是基础算法;朴素贝叶斯、梯度提升树 (GBDT/XGBoost)、集成学习(Bagging/Boosting)是进阶优化方案,均依托排序、查找、树结构等基础能力。
-
无监督学习:K – 均值聚类、层次聚类、主成分分析 (PCA) 是基础;DBSCAN 密度聚类、孤立森林、谱聚类、EM 算法(高斯混合模型)用于更复杂的聚类、降维、异常检测场景。
-
搜索与优化:A搜索算法、遗传算法、模拟退火是启发式优化的代表;IDA、D* Lite、粒子群优化 (PSO)、蚁群算法用于更复杂的路径规划与组合优化问题。
3. 区块链
共识算法中,PoW 依托哈希计算,PBFT 基于图论共识;存储层默克尔树、LSM 树、分布式哈希表 (DHT)、IPFS 内容寻址均是数据结构的典型应用。
4. 量子计算
量子比特数组、量子哈希是新型量子数据结构;Grover 搜索算法、Shor 算法(大数分解)、量子傅里叶变换是标志性量子算法,在特定问题上具备指数级加速能力。
5. 边缘计算
面向边缘节点资源受限的特点,衍生出微型布隆过滤器、轻量级跳表等低内存占用的数据结构,适配边缘硬件的内存约束。






