全部文章

页码9/11

数组

数组是程序设计中最基础的数据结构，它把相同类型的数据按连续的内存位置有序存放，通过下标就能快速访问对应元素，便于批量存储与处理一组数据，但数组长度大多固定，插入删除操作效率相对较低。

堆排序利用大顶堆（或小顶堆）的堆性质，先将待排序数组构建成堆，反复取出堆顶最大元素放到末尾，再调整剩余元素维持堆结构，完成排序；时间复杂度稳定\(O(n\log n)\)，原地排序，属于不稳定排序。

DAG 即有向无环图，DAG 上的最短路径先对图做拓扑排序，按照拓扑序列依次取出每个顶点，对它的所有出边执行松弛操作即可求出单源最短路径；该算法可以处理负权边，不能处理负环（DAG 本身不存在环），时间复杂度 O(n+m)，效率优于 Bellman‑Ford 与 SPFA。

Floyd‑Warshall 算法是基于动态规划的全源最短路径算法，可求解图中任意两点最短距离，支持负权边，适合小规模稠密图，也能够检测图中的负权环。

增量式 Floyd 在标准 Floyd 基础上，按顺序逐步加入中间节点 k，动态更新任意两点间最短路径，支持节点逐个新增的场景；它复用之前已算好的路径结果，不必每次从头完整重跑，适合图中节点不断增加的问题，时间复杂度仍为\(O(n^3)\)。

二分查找针对有序序列，每次取中间元素和目标对比，减半缩小查找范围，时间复杂度 O (log n)，查找效率高。

快速排序基于分治思想，选取一个基准元素，把数组划分成小于基准和大于基准的两部分，再递归对左右子区间继续划分排序；平均时间复杂度\(O(n\log n)\)，最坏\(O(n^2)\)，属于不稳定排序，不需要额外开辟大量辅助空间。

Dijkstra 算法是图论中经典的贪心算法，依托松弛操作求解非负边权带权图的单源最短路径，广泛运用于路径规划、网络路由等各类工程场景。