外部排序
所谓外部排序，即对外存中的记录进行排序（相对于内部排序而言）。有了内部排序算法，为什么还要外部排序?因为外存中记录规模太大，内存放不下。外部排序可以概括为一句话∶将内存作为工作空间来辅助外存数据的排序。外部排序最常用的算法是归并排序。归并排序之所以常用，是因为它不需要将全部记录都读入内存即可完成排序。因此，可以解决由于内存空间不足导致……继续阅读 »
yanzexi
1年前 (2023-10-28) 236浏览 0评论
0个赞
若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相同即$key_i=key_j$，且在排序前$R_i$在$R_j$的前面，若使用某一排序算法排序后，$R_i$仍然在$R_j$的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允……继续阅读 »
yanzexi
1年前 (2023-10-27) 234浏览 0评论
0个赞
最短路径
$Dijkstra$算法
朴素$Dijkstra$算法，时间复杂是$O(n^2+m)$，$n$表示点数，$m$表示边数：
//dijkstra 算法
int g[N][N]; // 存储每条边
int dist[N]; // 存储 1 号点到每个点的最短距离
int st[N]; // 存储每个点的最短路是否已经确定……继续阅读 »
yanzexi
1年前 (2023-10-26) 327浏览 0评论
0个赞
存储表示
存储与基本操作
图的邻接表（稀疏图，一般$\left| E \right|……继续阅读 »
yanzexi
1年前 (2023-10-24) 305浏览 0评论
1个赞
跳转表
跳转表
每一水平列表称作一层（$level$），其中$S_0$和$S_h$分别称作底层（$bottom$）和顶层（$top$）。与通常的列表一样，同层节点之间可定义前驱与后继关系。为便于查找，同层节点都按关键码排序。需再次强调的是，这里的次序只是内部的一种约定；对外部而言，各词条之间仍然只需支持判等操作即可。
……继续阅读 »
yanzexi
1年前 (2023-10-22) 292浏览 0评论
1个赞
红黑树
性质
插入
红黑树的插入有 12 种情况，插入一个结点最容易出现两个连续的红色结点从而破坏红黑树的性质，故需要进行双红调整。插入的情况整体分为三类，第一类是父节点为黑节点直接插入：
第二种情况是父节点为红色且父节点有兄弟：
&nbs……继续阅读 »
yanzexi
1年前 (2023-10-20) 264浏览 0评论
2个赞
伸展树
引入
伸展树（$splay$ $tree$）也是平衡二叉搜索树的一种形式。相对于$AVL$树，伸展树的实现更为简捷。伸展树无需时刻都严格地保持全树的平衡，但却能够在任何足够长的真实操作序列中，保持分摊意义上的高效率。伸展树也不需要对基本的二叉树节点结构，做任何附加的要求或改动，更不需要记录平衡因子或高度之类的额外信息，故适用范围更广。
……继续阅读 »
yanzexi
1年前 (2023-10-19) 299浏览 0评论
0个赞
二叉搜索树的最小绝对差
中序遍历逐行算差：
TreeNode* pre = nullptr;
int result = INT_MAX;
void traversal(TreeNode* cur) {
if (!cur){
return;
}
traversal(cur -> left);
……继续阅读 »
yanzexi
1年前 (2023-10-18) 274浏览 0评论
0个赞
二叉搜索树
基于二叉树模板实现
查找：
bool search(TreeNode* root, int x){
if(!root){
return false;
}
if(x == root -> val){
return true;
}else if(x < root -> val){
……继续阅读 »
yanzexi
1年前 (2023-10-17) 267浏览 0评论
0个赞
堆
定义
堆应满足结构性和堆序性两个条件，首先，其逻辑结构须等同于完全二叉树，此即所谓的“结构性”。如此，堆节点将与词条一一对应。其次，就优先级而言，堆顶以外的每个节点都不大（小）于其父节点，此即所谓的“堆序性”。堆的结构等同于完全二叉树的堆，n 个词条组成的堆的高度$h = \lfloor log_2n \rfloor = O(logn)$……继续阅读 »
yanzexi
1年前 (2023-10-16) 249浏览 0评论
1个赞
