[数据结构·排序] 插入排序及其变种
这是一份关于插入排序及其变种的详细讲解。我为您整理了三种主要的插入排序算法：直接插入排序、折半插入排序和希尔排序。 插入排序算法详解插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 本文将详细介绍三种主要的插入排序方式： 直接插入排序 (Direct Insertion Sort) 折半插入排序 (Binary Insertion Sort) 希尔排序 (Shell Sort) 1. 直接插入排序 (Direct Insertion Sort)这是最基础的插入排序。它的核心思想是将数组分为“已排序区间”和“未排序区间”。初始时，已排序区间只有一个元素。 算法流程 从第一个元素开始，该元素可以认为已经被排序。 取出下一个元素（称为“基准”或 key），在已经排序的元素序列中从后向前扫描。 如果该元素（已排序）大于新元素，将该元素移到下一位置。 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。 将新元素插入到该位置后。 重复步骤...
[数据结构·排序] 排序方法及其分类
根据您提供的课件内容（《第三十章 内部排序》），其中详细介绍了多种内部排序方法。 课件将这些排序方法按基本思想（策略）主要分为五大类。以下是整理好的所有排序方法及其分类： 1. 插入排序 (Insertion Sort)基本思想：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序的子序列的适当位置，直到所有记录都插入为止 1。 直接插入排序 (Direct Insertion Sort) 2 最基本的插入排序方法。 希尔排序 (Shell Sort) 3 又称“缩小增量”排序，是对直接插入排序的改进。 其他插入排序： 折半插入排序 (Binary Insertion Sort) 4：利用折半查找来寻找插入位置。 2-路插入排序 5：旨在减少移动记录的次数，需要辅助空间。 表插入排序 6：采用链表存储结构，在排序过程中不移动记录，只改变指针。 2. 交换排序 (Exchange Sort)基本思想：两两比较待排序记录的关键字，如果发生逆序则交换，直到整个序列中没有反序的记录为止 7。 冒泡排序 (Bubble Sort)...
[数据结构·树] 线段树：单点修改与区间最值查询
这是一道非常经典的单点修改 + 区间最值查询 (RMQ) 问题。由于涉及频繁的修改和查询，使用线段树（Segment Tree）可以将单次操作的时间复杂度降低到 $O(\log n)$，从而在限制时间内完成 $200,000$ 次操作。 线段树解决区间最值问题 (RMQ)1. 题目分析 需求： 区间查询 (Q a b)：查询 $[a, b]$ 区间内的最大值。 单点更新 (U a b)：将 ID 为 $a$ 的成绩更新为 $b$（前提是 $b$ 更大）。 数据规模：$n, m \le 200,000$。如果使用暴力遍历，复杂度为 $O(n \times m)$，显然会超时。 最优解法：线段树。其查询和修改复杂度均为 $O(\log n)$，总复杂度 $O(m \log n)$。 2. 线段树设计思路(1) 存储结构使用一个数组 tree[] 来存储线段树节点，通常大小开到原数组的 4倍。 tree[node] 存储当前区间内的最大值。 根节点编号为 1，代表区间 $[1, n]$。 对于编号为 node 的节点： 左子节点编号为 node * 2 (或 node...
[数据结构·树] 平衡二叉搜索树（AVL）
🌳 AVL 树 (自平衡二叉查找树) 的 C 语言实现与解析AVL 树是一种自平衡的二叉查找树（BST）。它通过在插入和删除节点后进行“旋转”操作，来确保树的高度始终保持在 $O(\log n)$ 级别，从而保证了所有基本操作（查找、插入、删除）的最坏时间复杂度都是 $O(\log n)$。 📄 完整的 C...
[数据结构·树] 二叉树的遍历方法及应用
二叉树的遍历是指按照某种特定的顺序访问树中的每一个节点，且每个节点只被访问一次。常见的遍历方法主要分为两大类：深度优先搜索（DFS）和广度优先搜索（BFS）。 深度优先搜索 (DFS)：尽可能深地搜索树的分支。根据根节点被访问的顺序，又分为前序遍历、中序遍历和后序遍历。 广度优先搜索 (BFS)：又称为层序遍历，从根节点开始，逐层地访问节点。 1. 前序遍历 (Pre-order Traversal)访问顺序：根 (Root) -> 左 (Left) -> 右 (Right) 核心思想：首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。 递归实现思路：12345678910111213function preorder(node):if node is null:returnvisit(node) // 访问根节点preorder(node.left) // 遍历左子树preorder(node.right) // 遍历右子树 迭代实现思路（使用栈）： 将根节点入栈。 循环直到栈为空：a. 弹出栈顶节点 node 并访问它。b. 先将...
[数据结构·树] 二叉查找树（BST）
你好！这是一个非常核心的数据结构问题。 首先，我来澄清一下：二叉查找树（Binary Search Tree, BST） 和 二叉排序树（Binary Sort Tree） 是 完全相同的概念，只是名字不同。它们都描述的是同一种数据结构。 🌳 什么是二叉查找树 (BST)？二叉查找树（BST）是一种特殊的二叉树，它“有序”地组织数据，其定义如下： 它首先是一棵二叉树（每个节点最多有两个子节点）。 对于树中的任意一个节点，其左子树中所有节点的值都小于该节点的值。 对于树中的任意一个节点，其右子树中所有节点的值都大于该节点的值。 它的左、右子树也分别是二叉查找树。 注意： 这个定义通常不允许重复值。如果允许重复值，一种常见的约定是将其放在右子树（即右子树的值 >= 节点的值）。 🧠 主要实现什么功能？二叉查找树的核心功能是提供高效的动态集合操作。它的主要优势在于： 高效查找...
[数据结构·图] Kruskal 算法的最小生成树
最小生成树 (MST) 从理论到实操：基于 Kruskal 算法1. 题目解析与理论基础什么是最小生成树 (Minimum Spanning Tree, MST)？想象你要在一个拥有 $n$ 个城市的国家修建光缆，使得所有城市都能互相连通（直接或间接相连）。 生成树 (Spanning Tree)：在一个图中，选出 $n-1$ 条边，将所有 $n$ 个点连接起来，且没有环的结构。 最小生成树 (MST)：在所有可能的生成树中，边的权值之和最小的那一个。 结合题目 输入：$n$ 个节点，$m$ 条带权无向边。可能有重边（两个点之间有多条线）。 目标：选出 $n-1$ 条边，连接所有点，使权值和最小。 数据范围： $n \le 10^3$（点不多） $m \le 10^5$（边比较多） $w \le 10^9$（权重很大，注意：结果需要用 long long） 2. 算法选择：Kruskal 算法对于这道题，我们推荐使用 Kruskal (克鲁斯卡尔) 算法。 为什么选 Kruskal？Kruskal 算法的核心思想是...
[数据结构·图] 最小生成树——普里姆算法
最小生成树：普里姆算法 (Prim) - 邻接表版1. 算法核心思想Prim 算法是一种 贪心算法。它的逻辑类似于“通过不断吞并最近的邻居来扩张领土”。 集合划分：将顶点分为两个集合： 已选集合 ($S$)：已经在最小生成树中的点。 未选集合 ($V-S$)：还没有加入树的点。 贪心策略：每次从“未选集合”中找到一个顶点，使得它与“已选集合”之间的边权值最小。 更新：将该顶点加入 $S$，并更新它的邻居到 $S$ 的距离。 2. 数据结构设计由于使用邻接表，我们无法像邻接矩阵那样 $O(1)$ 查边，也无法高效地扫描所有点的最短距离。因此，我们需要配合 优先队列 (Min-Heap) 来快速获取当前距离生成树最近的点。 图存储：vector<vector<pair<int, int>>> adj (存目标点和权值)。 距离数组：dist[i] 记录节点 $i$ 到当前生成树集合的最小距离（注意：不是到源点的距离，那是 Dijkstra）。 访问标记：vis[i]...
[数据结构·图] 关键路径
图的关键路径 (Critical Path) 复习指南1. 核心概念1.1 定义关键路径是在 AOE 网 (Activity On Edge Network) 中，从源点 (Start) 到汇点 (End) 的所有路径中，路径长度（权重之和）最长 的那条路径。 1.2 适用范围 (AOE 网) AOE 网： 顶点 (Vertex)：表示 事件 (Event)，例如“项目开始”、“地基打好”。事件是一个瞬间点。 边 (Edge)：表示 活动 (Activity)，边上的权值表示活动持续的时间。 核心意义：关键路径的长度决定了完成整个工程所需的 最短时间。 1.3 关键活动 关键路径上的活动称为 关键活动。 这些活动是没有“缓冲时间”的，一旦延误，整个工期都会延误。 2. 核心计算步骤 (四步法)计算关键路径通常需要计算四个核心参数。假设图中有 $n$ 个事件（顶点），边 $$ 表示活动 $ak$，持续时间为 $w{i,j}$。 第一步：求 事件的最早发生时间 $ve(k)$ 顺序：从源点开始，按 拓扑序...
[数据结构·图] 拓扑排序
图的拓扑排序 (Topological Sorting) 复习指南1. 核心概念1.1 定义拓扑排序是对有向无环图 (DAG, Directed Acyclic Graph) 的顶点的一种排序。它使得对于图中的每一条有向边 $(u, v)$，顶点 $u$ 在排序中都出现在顶点 $v$ 之前。 1.2 适用范围 (AOV 网) AOV 网 (Activity On Vertex Network)：用顶点表示活动，用边表示活动间的优先关系。 前提条件：图必须是 有向 的，且 没有环 (Acyclic)。 性质： 如果存在环，则无法进行拓扑排序。 一个 DAG 的拓扑排序序列可能不唯一。 2. 核心算法实现最常用的算法是基于 入度 (Indegree) 的算法（也称为 Kahn 算法）。 2.1 算法步骤 (Kahn 算法) 初始化：计算图中所有节点的入度。 入队：将所有入度为 0 的节点放入队列（Queue）中。 循环处理： 当队列不为空时，取出队首节点 $u$，放入结果序列。 遍历 $u$ 的所有邻接点 $v$ (即存在边 $u \to v$)。 将 $v$ 的入度减...