Elian's blog page

归并的基本思想归并：把两个或多个已经有序的序列合并成一个新的有序序列。 归并排序最常用的是二路归并： 把待排序序列拆成若干个有序子表。 每次把相邻的两个有序子表归并成一个更长的有序子表。 子表长度逐趟翻倍，直到整个序列有序。 内部排序中通常采用二路归并；多路归并更常出现在外部排序中。 若朴素地做 $m$ 路归并，每次要从 $m$ 个子表的当前元素中选出最小者，最多需要比较 $m-1$ 次。二路归并时 $m=2$，所以每选出一个元素只需要比较 1 次。 二路归并设数组中已有两个相邻有序子表： $$A[left, mid),\quad A[mid, right)$$ 二路归并要把它们合成一个有序区间 $A[left, right)$。 ↻ + − 核心指针含义： 指针 含义 i 指向左子表当前待比较元素 j 指向右子表当前待比较元素 k 指向原数组中当前写回位置 归并时每次比较 B[i] 和 B[j]： 若 B[i] <= B[j]，把 B[i] 写回 A[k]，然后 i++、k++。 若 B[i] > B[j]，把...

选择类排序的共同思想选择排序的共同动作是：每一趟从待排序元素中选择一个关键字最小或最大的元素，把它加入有序子序列。 两种典型算法： 简单选择排序：直接在线性表中扫描，找出当前待排序区的最小元素。 堆排序：用堆快速维护当前待排序区的最大或最小元素。 简单选择排序简单选择排序每一趟在待排序区 $A[i..n-1]$ 中找最小元素，把它与 $A[i]$ 交换。第 $i$ 趟结束后，$A[0..i]$ 是最终有序区。 ↻ + − 简单选择排序的 C 写法12345678910111213141516171819202122232425262728/** * Sorts an integer array in nondecreasing order using simple selection sort. * * Args: * a: Array to sort in place. * n: Number of elements in the array. * * Notes: * After pass i, a[0..i] contains the i+1...

Exchange Sorts交换类排序交换类排序的共同点是：根据两个元素关键字的比较结果，交换它们在序列中的位置。 主要讨论两种交换类排序： 冒泡排序：只比较相邻元素，若相邻逆序则交换。 快速排序：通过一次划分把枢轴放到最终位置，再递归处理左右子表。 冒泡排序冒泡排序从后往前或从前往后两两比较相邻元素。如果相邻元素逆序，就交换它们。一趟冒泡结束后，会有一个元素到达最终位置。 下面采用“从后往前冒泡”的写法：每一趟把当前无序区中最小的元素冒到最前面。 如果一次处理无交换发生，则说明已经有序，提前停止算法。 ↻ + − 冒泡排序的 C 写法1234567891011121314151617181920212223242526272829/** * Sorts an integer array in nondecreasing order using bubble sort. * * Args: * a: Array to sort in place. * n: Number of elements in the array. * * Notes: * ...

Insertion Sorts插入排序的共同思想插入类排序的核心是： 把一部分元素看作已经有序。 每次取出一个待排序元素。 在已有序部分中找到它应该插入的位置。 移动元素，腾出位置，把该元素放进去。 直接插入、折半插入、希尔排序都属于这个思路，但“已有序部分”的定义和“插入位置”的查找方式不同。 直接插入排序直接插入排序每一趟都把 $A[i]$ 插入到前面已经有序的子序列 $A[0..i-1]$ 中。 ↻ + − 直接插入排序的 C 写法123456789101112131415161718192021222324/** * Sorts an integer array in nondecreasing order using direct insertion sort. * * Args: * a: Array to sort in place. * n: Number of elements in the array. * * Notes: * The prefix a[0..i-1] is already sorted before each...

排序的基本概念排序：重新排列一组记录，使记录按照关键字递增或递减。 设输入记录为 $R_1,R_2,\dots,R_n$，对应关键字为 $k_1,k_2,\dots,k_n$。若按递增排序，输出应是输入记录的一个重排 $R’_1,R’_2,\dots,R’_n$，并满足： $$k’_1 \le k’_2 \le \dots \le...

AOE Network And Critical PathAOE 网用于分析工程项目中“活动耗时”与“工程最短完成时间”。它和 AOV 都依赖有向无环结构，但含义不同： AOV 网：顶点表示活动，边表示活动先后约束，主要用于 拓扑排序。 AOE 网：顶点表示事件，边表示活动，边权表示活动耗时，主要用于求关键路径。 AOE 网在带权有向图中： 顶点表示事件。 有向边表示活动。 边上的权值表示完成该活动的开销，常见含义是活动所需时间。 这样的网络称为 AOE 网，即 Activity On Edge Network。 AOE 网有两个基本性质： 只有某顶点所代表的事件发生后，从该顶点出发的活动才能开始。 只有进入某顶点的各活动都已经结束时，该顶点所代表的事件才能发生。 AOE 网中通常只有一个入度为 0 的顶点，称为源点或开始顶点；只有一个出度为 0 的顶点，称为汇点或结束顶点。 关键路径从源点到汇点的有向路径可能有多条。所有路径中，路径长度最大的路径称为关键路径，关键路径上的活动称为关键活动。 这里的路径长度是路径上活动耗时之和。 为什么是最长路径 AOE...

DAG And AOV Network DAG 是没有有向环的有向图。 AOV 网用 DAG 表示活动之间的先后依赖。 DAGDAG 是 Directed Acyclic Graph，即有向无环图。 定义：若一个有向图中不存在有向环，则称为有向无环图。 这里的“无环”指的是：不存在一条沿弧方向出发，最后又回到出发顶点的路径。 例如： 12V0 -> V1 -> V3V0 -> V2 -> V3 这是 DAG，因为所有边都大致从前往后指向，不可能沿方向回到原顶点。 而： 1V1 -> V2 -> V3 -> V1 不是 DAG，因为存在有向环。 与拓扑排序的关系 一个有向图存在拓扑序列，当且仅当它是 DAG。若拓扑排序过程中图还没空，但已经找不到入度为 0 的顶点，则说明剩余部分存在有向环。 DAG 描述表达式表达式树会把每次出现的操作数或子表达式都画出来；DAG...

Topological Sorting拓扑排序解决的是 AOV 网中的“先后顺序”问题。 AOV 网用顶点表示活动，用有向边 <u, v> 表示活动 u 必须先于活动 v 进行。因为活动依赖不能循环，所以 AOV 网必须是 DAG，也就是有向无环图。 和 DFS 判环的关系 拓扑排序本身可以判断有向图是否有环。DFS 也可以通过 VISITING 状态判断有向环，见DFS 判有向图环。 拓扑序列的定义一个有向图的顶点序列若满足： 每个顶点出现且只出现一次。 若图中存在从顶点 A 到顶点 B 的路径，则 A 必须排在 B 前面。 则称该序列为这个图的一个拓扑序列。 等价地说：如果序列中 A 在 B 前面，那么图中不能存在从 B 到 A 的路径。 拓扑序列通常不唯一。例如两个活动互不依赖时，它们谁先谁后都可以。 Kahn 算法：不断删除入度为 0 的顶点Kahn 算法是考研中最常见的拓扑排序实现。时间复杂度与遍历图一样。 核心规则： 从 AOV 网中选择一个没有前驱的顶点，也就是入度为 0...

最短路径问题讨论的是：在图中，从一个顶点走到另一个顶点，怎样使路径长度最小。 这里的“长度”要分清两种情况： 无权图：每条边都可看成权值为 1，路径长度就是路径上的边数。 带权图：路径长度是路径上各边权值之和，也叫带权路径长度。 问题分类单源最短路径给定一个源点 $s$，求 $s$ 到其他各顶点的最短路径。 常见方法： 无权图：BFS。 非负权图：Dijkstra。 允许负权边但无负权回路：可用 Bellman-Ford 或 SPFA。 每对顶点间的最短路径求图中任意两个顶点 $V_i$ 到 $V_j$ 的最短路径。 常见方法： Floyd。 也可以对每个顶点各运行一次 Dijkstra，但前提仍然是边权非负。 BFS：无权图的单源最短路径无权图可以看成每条边权值都为 1 的特殊带权图。BFS 从源点按“距离层次”向外扩展：先访问距离为 1 的点，再访问距离为 2 的点。一个顶点第一次被 BFS 访问时，它的距离已经是从源点到它的最短距离。 ↻ + − 数组含义 visited[v]：顶点 v 是否已经被访问。 dist[v]：源点到 v...

顺序查找顺序查找也称线性查找，通常用于线性表。基本思想是从表的一端开始，逐个比较关键字，直到查找成功或查完整个表。 ↻ + − 普通顺序查找123456789int sequential_search(const int a[], int n, int key) { for (int i = 0; i < n; ++i) { // 每次循环都比较一次关键字。 if (a[i] == key) { return i; } } return -1;} 普通顺序查找中，若表长为 $n$： $$ASL_{success}=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}$$ 若查找失败，需要比较完所有 $n$ 个元素： $$ASL_{fail}=n$$ 若采用从下标 1 开始、0 号位置放哨兵的教材写法，则失败时会停在 0...