约定 · 核验 · 更新于 2026-09-22
约定与核验
这是一个教学演示站，讲的是通用的数据结构与算法，没有法规条文或「官方原文」可以引用。页面上的伪代码、复杂度说明和要点都由本站编写，下面把写法约定和正确性的核验方式逐条写清楚。
写法与计数约定（本站归纳）
伪代码写法
下标从 0 开始；「a ← b」表示赋值；「i ← 0 … n−1」表示 i 依次取 0 到 n−1（含两端）；区间 [lo..hi] 含两端。伪代码由本站编写，只为配合演示逐行对照，不对应任何特定教材或编程语言。
复杂度记法
用大 O 表示随输入规模 n 增长的量级，忽略常数。图算法里 V 是顶点数、E 是边数；树遍历里 h 是树高、w 是最宽一层的结点数。「空间」指除输入本身以外需要的额外空间，递归算法把调用栈算在内。
比较次数怎么数
排序与查找演示里的「比较次数」只数元素之间（或元素与目标值）的比较，不数循环下标的比较。二分查找每轮先判相等、再判大小，最多记 2 次。
相等元素怎么处理
冒泡、插入只在「严格大于」时移动，归并在两头相等时先取左段，所以这三种是稳定的；选择、快速、堆排序会远距离交换，不稳定。快速排序演示用「严格小于基准」划分，全部相等的输入会退化到最坏情况，这是有意保留的，便于观察。
邻居的处理顺序
图演示里每个顶点的邻居按名称排序后依次处理（字母序，数字按数值），所以同一输入每次的访问顺序一致。换一种顺序，BFS/DFS 的访问序列可能不同，但都是正确的遍历。
输入规模上限
排序与查找最多 16 个数，树最多 20 个结点、6 层，图最多 10 个顶点、20 条边，栈与队列容量 6。上限只是为了让每一步在手机屏幕上看得清，不是算法本身的限制。
正确性怎么核验
每次构建前运行自动测试，任何一条不通过就不发布。每种排序对 300 组随机输入（含重复值、负数）与边界输入（空数组、1 个数、全部相等、已排好、完全逆序）的结果，都与 JavaScript 内置排序的结果逐项一致。
冒泡、插入、归并三种排序在有重复值时保持相等元素的原有次序（稳定性检查）。
快速排序对已排好的 16 个数恰好比较 120 次（= 16×15/2），对随机排列的平均比较次数与理论值 2(n+1)Hₙ − 4n 相差不到 1 次。
顺序查找返回第一次出现的位置；二分查找在有序数组上找得到时返回的位置确实等于目标，找不到时返回 −1。
栈与循环队列对随机操作序列的出栈/出队顺序、剩余内容，与用普通数组直接模拟的结果一致，上溢、下溢、队满、队空都被拒绝。
四种树遍历对随机生成的二叉树，与另写的一份参考实现输出完全相同；空树、只有根、退化成链的树也逐一检查。
BFS 在随机图上得到的层数与参考实现一致；Dijkstra 的最短距离与 Bellman-Ford 参考实现在 200 张随机图上全部相同，不可达顶点记为 ∞。
所有演示的每一帧都指向存在的伪代码行；同一输入录两次，得到的帧序列完全相同（可回放）。
测试用固定种子生成随机输入，所以每次运行检查的是同一批数据，结果可以复现。发现某一步演示不对，请通过页面底部的「微信咨询」告诉我们具体输入和第几步。
各演示的伪代码行数与复杂度
| 演示 | 伪代码行数 | 最好 | 平均 | 最坏 | 额外空间 |
|---|---|---|---|---|---|
| 冒泡排序 | 7 | O(n) | O(n²) | O(n²) | O(1) |
| 插入排序 | 6 | O(n) | O(n²) | O(n²) | O(1) |
| 选择排序 | 6 | O(n²) | O(n²) | O(n²) | O(1) |
| 归并排序 | 8 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 快速排序 | 7 | O(n log n) | O(n log n) | O(n²) | O(log n) 平均，O(n) 最坏 |
| 堆排序 | 9 | O(n log n) | O(n log n) | O(n log n) | O(1) |
| 顺序查找 | 3 | O(1) | O(n) | O(n) | O(1) |
| 二分查找 | 7 | O(1) | O(log n) | O(log n) | O(1) |
| 栈 | 6 | O(1) | O(1) | O(1) | O(n) |
| 队列（循环队列） | 6 | O(1) | O(1) | O(1) | O(n) |
| 前序遍历 | 5 | O(n) | O(n) | O(n) | O(h) |
| 中序遍历 | 5 | O(n) | O(n) | O(n) | O(h) |
| 后序遍历 | 5 | O(n) | O(n) | O(n) | O(h) |
| 层序遍历 | 6 | O(n) | O(n) | O(n) | O(w) |
| 广度优先搜索（BFS） | 5 | O(V + E) | O(V + E) | O(V + E) | O(V) |
| 深度优先搜索（DFS） | 4 | O(V + E) | O(V + E) | O(V + E) | O(V) |
| Dijkstra 最短路 | 7 | O(V²) | O(V²) | O(V²) | O(V) |