广义表

头尾链表存储表示：一个struct由两部分组成，第一部分tag表示原子节点还是广义表，第二部分若tag为原子节点则存元素，若tag为广义表则存储头指针和尾指针，头指针指向第一个元素，尾指针指向除了第一个元素的广义表。

扩展线性链表表示：一个struct由三部分组成，第一部分tag表示原子节点还是广义表，第二部分指向下一层节点，第三部分指向同级节点。（类似于孩子兄弟）

KMP

数据结构是数据结构，算法是算法，史前PPT写法，我们都爱它。 对于所有的写法都要记住一件事情，i只增不减，动的永远是j，有助于背诵。 注意：严版本的KMP的next含义和网上的大多数模板是不同的。 首先是定义: 当模式串中第j个字符与主串中第i个字符“失配”时，在模式串中需重新和主串中该字符进行比较的字符的位置。 然后是如何手动填充，先找到最长的 相同的 不含尾的前缀，和不含头的后缀，它们的长度 + 1就是next数组的值。对于next[1]初始化为0即不匹配，特别地在教材中的定义下，字符串是不包含j当前下标的，即[1~j-1]这个范围的最长字串长度然后再+1。 此处给出一个根据此定义计算的next数组例子。

字符串 a b a b a c
下标 1 2 3 4 5 6
next[j] 0 1 1 2 3 4

另一个

1
2

a b c a a c a b a c a
0 1 1 1 2 2 1 2 3 2 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void get_next(SString &T, int &next[] ) 
{// 求模式串T的next函数值并存入数组next
    i = 1, j = 0;   
    next[1] = 0;
    length = T[0];//就是这么定义的，怎么着
    while (i < length) {
        if (j == 0 || T[i] == T[j]) 
        {
            i++, j++;
            next[i] = j;
        }
        else  j = next[j];
    }
} // get_next

next改进写法。如果当前模式串中存在两个相同的字符，当匹配时如果后面的没匹配上，前面的一定也匹配不上，所以如果没有改进就需要一直跳转。为了减少复杂度，我们直接在构造next数组的时候进行优化。注意到这时候的nextval数组的含义已经发生了变化，但next和nextval都符合kmp匹配时跳转的需求。

此处举例说明。

模式串：  a a a a b
next：   0 1 2 3 4
nextval：0 0 0 0 4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void get_nextval(SString &T, int &nextval[]) 
{  // 求模式串T的next函数修正值并存入数组nextval.
    i = 1; j = 0;
    nextval[1] = 0;
    length = T[0];
    while (i < length) {
        if (j == 0 || T[i] == T[j]) {
            ++i;  ++j;
            if (T[i] != T[j])  nextval[i] = j;
            else  nextval[i] = nextval[j];
            //若下一对相等，则他们的nextval值也相等，
        }
        else  j = nextval[j];
    }
} // get_nextval

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int Index_KMP(SString S, SString T, int pos) {
    // 利用模式串T的next函数求T在主串S中第pos个字符之后的
    //位置的KMP算法，其中，T非空，1≤pos≤StrLength(S)。
    i = pos;   j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j = 0 || S[i] == T[j]) { ++i;  ++j; }
        // 继续比较后继字符
        else  j = next[j];         // 模式串向右移动
    }
    if (j > T[0])  return  i-T[0];    // 匹配成功
    else return 0;
} // Index_KMP

霍夫曼

典中典合并果子

to be continued

图

基本概念

有向图，无向图。（有向边可以称作有向弧，弧尾是起始节点，弧头是终止节点） 完全图，有向完全图。 带权图称作网，即有向网，无向网。 若边或弧的个数 e<nlogn，则称作稀疏图，否则称作稠密图。

假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，边(v,w)和顶点v和w相关联。

和顶点v关联的边的数目定义为顶点的度。

对于有向图： 顶点的度 = 入度 + 出度

子图：顶点是子集，边也是子集

设存在图$(G=(V,{VR}))以及图(G^{\prime}=(V^{\prime},{VR^{\prime}}))$，

并且满足以下条件：

  • $(V^{\prime}\subseteq V)$，即集合$(V^{\prime})$是集合$(V)$的子集。
  • $(VR^{\prime}\subseteq VR)$，也就是集合$(VR^{\prime})$是集合$(VR)$的子集。 那么，此时称$(G^{\prime})$为$(G)$的子图。

无向图：

路径：在无向图G=(V,{E})中由顶点v至v’ 的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v’ 之间有路径存在。 连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。 连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。 极大连通子图就是在原图形G的所有连通子图中，不能再添加任何节点和边而仍然保持连通性的子图。（说人话就是把一个图拆成几份，这几份本身最开始也不相连）

有向图：

路径：在有向图G=(V,{E})中由顶点v经有向边至v’ 的顶点序列。路径上边的数目称作路径长度。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v’ 之间有路径存在 强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 强连通分量：极大连通子图 有向图的极大强连通子图（和无向图中的连通性不同，这里是强连通性）是指一个子图，在这个子图中，对于任意两个节点u和v，存在从u到v的有向路径和从v到u的有向路径，并且这个子图在满足强连通性的子图中是最大的（不能再添加节点和边来保持强连通性）。

生成树：极小连通子图，包含图的所有 n 个结点，但只含图的 n-1 条边。即在生成树中添加一条边之后，必定会形成回路或环。

有向树：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。 //有向图生成树一定是有向树

有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

存储

邻接矩阵，邻接表。

十字链表和邻接多重表。（只存在于教科书的奇怪东西https://www.cnblogs.com/wkfvawl/p/9985083.html待我从长计议）

遍历

广搜，深搜

强连通分量

用的是 Kosaraju（是否需要掌握存疑），但是Tarjan用的更多吧。

最小生成树

迫于形势，学习教材版本。但事实上，408对于代码要求很低，更多是人肉实现。 首先学习MST性质，简单来说，一个联通带权图，分成两份（非空，大于等于1个顶点），从这两个分量之间找到最短的那条边，最小生成树一定包括这条边。

prim就是从一点开始不断连连和这个分量最短的边。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

enum GraphKind{
    DG,DN, UDG,UDN
}; //{有向图，有向网，无向图，无向网}

typedef struct ArcCell {
    int adj;     //权值
    InfoType *info; //该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];


struct MGraph{
    int vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs;                  //邻接矩阵
    int vexnum, arcnum;              //图的当前顶点数和弧数
    GraphKind kind;                  //图的种类标志
};

//注意以上代码表示arcs是一个二维矩阵，大小为[MAX_VERTEX_NUM][MAX_VERTEX_NUM]，除了教材还没见过那个正常人写这么有病的代码

struct {
    int adjvex;      // 顶点子集U中的顶点
    int lowcost;         // 顶点子集V-U到当前顶点的边的权值
} closedge[MAX_VERTEX_NUM]; // 辅助数组

int LocateVex(MGraph G, VertexType v) {
    int ct;
    for (ct = 0; ct < G.vexnum; ct++)
        if (G.vexs[ct] == v)
            return ct;
    return -1;
}

int minimum(MGraph G) {
    int i, k = -1;
    int min = INT_MAX;
    // 从权值不为0的边中选择拥有最小权值的边
    for(i = 0; i < G.vexnum; i++) {
        if(closedge[i].lowcost != 0 && closedge[i].lowcost < min) {
            min = closedge[i].lowcost;
            k = i;
        }
    } 
    return k;
}


//从u出发构建无向图的最小生成树
void MinSpanTree_PRIM(MGraph G, VertexType u) {
    int i, j, k;   
    // 返回顶点u在无向网中的位置
    k = LocateVex(G, u);

    // 辅助数组初始化
    for(j = 0; j < G.vexnum; j++) {
        if(j != k) {
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j].adj;
        }
    }

    // 顶点k进入顶点子集U
    closedge[k].lowcost = 0;

    // 选择其余G.vexnum-1个顶点
    // i仅用来计数
    for(i = 1; i < G.vexnum; i++) {
        // 从顶点子集V-U中选出下一个候选顶点
        k = minimum(G);      
        // 输出
        printf("(%d,%d)\n", closedge[k].adjvex, G.vexs[k]); //输出生成树的边
        // 将顶点k加入到顶点子集U
        closedge[k].lowcost = 0;        
        // 更新顶点子集U与顶点子集V-U的边的信息
        for(j = 0; j < G.vexnum; j++) {
            if(G.arcs[k][j].adj < closedge[j].lowcost) {
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j].adj;
            }
        }
    }

}

kruskal就是先排序边，然后从短到长，如果不在一个集合里面那么就连一起。

最短路

dijkstra

floyd

次优查找树的构造

很偏门的知识点（

首先和二分查找一样，我们保证数据有序，当每个数据查询的概率不相等时，二分查找就不是最优的了，二最优查找树的构造复杂度过高O(n^3),所以采用次优查找树。

构造采用递归的思想，我们对于其中每一个元素计算不包括它的情况下，左面的权重也就是概率的和与右面的权重和的差的绝对值，然后取最小的作为根节点，然后将其左右分为两个子树，继续按照上述的方式构造即可。

还有抽象的调整情况，次优树构造过程中没有考虑到单个关键字的权值大小，有可能出现根节点的权值小于左右子树，只需要将左右子树中权值最大的那个节点替换掉根节点，最后再将替掉的原根节点按顺序插入就好了

二叉排序树/二叉搜索树

这个很简单，左面比根小，右面比根大的一颗二叉树。根据定义似乎不存在重复的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) 
{  
if (!T)
    { p = f;  return FALSE; }  // 查找不成功
else  if ( EQ(key, T->data.key) )
       	 { p = T;  return TRUE; }  // 查找成功
       else  if ( LT(key, T->data.key) )
	 SearchBST (T->lchild, key, T, p ); 
              else  SearchBST (T->rchild, key, T, p ); 
                    			    } // SearchBST

查找就是简单的递归。然后我们考虑一下插入，根据定义，插入只有在没有查到的情况下才可以进行，所以先进行一次查找然后发现不存在，下面进行操作：

  1. 查找形如Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) ，f是当前节点的父节点，p用于返回在二叉搜索树中找到的目标节点或者没找到时返回树的叶子节点（而不是NULL）进而方便插入下一个。
  2. 创建一个新节点，赋值，左右孩子为nullptr,比较它和p的key，变成p的孩子。

下一步是删除操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// 定义函数 DeleteBST，用于在二叉搜索树中删除指定键值的节点
// 参数 root 是指向二叉搜索树根节点的指针，通过引用传递，方便修改树结构
// 参数 key 是要删除的节点对应的键值
Status DeleteBST (BiTree &root, KeyType key) {
    // 如果根节点指针为空，说明二叉树为空，直接返回删除失败（FALSE）
    if (root == NULL) {
        return FALSE;
    }

    // 判断当前根节点的数据中的键值是否与要删除的 key 相等
    if (EQ(key, root->data.key)) {
        // 如果相等，调用Delete 函数
        return Delete(root);
    }
    // 如果要删除的 key 小于当前根节点的键值，说明目标节点可能在左子树中
    else if (LT(key, root->data.key)) {
        // 递归调用 DeleteBST，传入左子树指针和要删除的 key，继续在左子树中查找并删除节点，返回相应结果
        return DeleteBST(root->lchild, key);
    }
    else {
        //同理
        return DeleteBST(root->rchild, key);
    }
}
// 函数用于删除二叉树中的指定节点，并对树结构进行调整，返回删除操作是否成功
//替身法
Status Delete(BiTree &nodeToDelete) {
    // 情况一：要删除的节点没有右子树，只有左子树
    if (!nodeToDelete->rchild) {
        BiTree temp = nodeToDelete;  // 暂存要删除的节点指针
        nodeToDelete = nodeToDelete->lchild;  // 让要删除的节点指针指向其左子树
        delete temp;  // 释放原来要删除的节点内存
    }
    // 情况二：要删除的节点没有左子树，只有右子树
    else if (!nodeToDelete->lchild) {
        BiTree temp = nodeToDelete;
        nodeToDelete = nodeToDelete->rchild;
        delete temp;
    }
    // 情况三：要删除的节点既有左子树又有右子树
    else {
        BiTree parent = nodeToDelete;
        BiTree successor = nodeToDelete->lchild;
        // 从左子树出发，找到左子树中最右下的节点（值最大的节点），用于替换该节点，因为左面的都比右面小
        while (successor->rchild) {
            parent = successor;
            successor = successor->rchild;
        }
        //swap值
        nodeToDelete->data = successor->data;

        //此时parent是nodeToDelete（左子树没有右孩子）或者是sucessor的根节点
        if (parent == nodeToDelete) {
            parent->lchild = successor->lchild;
            //左子树的值给到删除节点，然后干掉左面的以一个节点
        } else {

            parent->rchild = successor->lchild;
        }
        delete successor;  // 释放后继节点内存
    }
    return TRUE;
}

删除

AVL树/平衡二叉树

当BST在顺序插入的时候，就会退化成链表，高度变成了n，而不是logn。所以我们要维护树的平衡，避免这种情况。 首先定义平衡因子：该节点的左子树高度减去右子树高度。 AVL树的所有节点平衡因子的绝对值均小于等于1。

其插入和BST类似，即先查找，找不到再插入。其删除也和BST类似，节点与后继交换后删除。但是以上操作后可能会引起平衡因子的变化，所以相比BST需要进一步维护。

更改后，一共可能出现两种情况$h_l < h_r - 1 $ 或者 $ h_l > h_r + 1$，然后又可以细分成四种情况即LL，LR，RL，RR（此处解释一下怎么记忆，L还有R表示的是哪个子树的高度更高）。注意的是无论如何维护，我们的目的只是，降低树的高度，保持它的性质，所以可以通过自己举例只有三个节点的情况下的大小关系协助记忆怎么进行旋转。

维护的操作一共就两种，即左旋（逆时针旋转），右旋（顺时针旋转）。旋转的是危机节点(即不平衡节点)，以它的后继的节点为中心（也是新的根）旋转。**左旋时，如果后继的不平衡节点也有左孩子，那么这个子树变成这个危机节点的右孩子。同理，右旋时，冲突的右子树变成危机节点的左孩子。**最后原先的后继不平衡节点变成新的根节点。

补充：后来发现LR，RL不能这么说，即使危机节点的孩子不是危机节点也需要旋转。这里重新总结一下，L是以左孩为中心右旋，R是以右孩为中心左旋。

下面进行操作总结。

情况 操作
LL 右旋
LR 先左旋左孩子然后右旋
RR 左旋
RL 先右旋右孩子然后左旋

我们可以发现啊，如果我们反着看情况的字母，再看对应的操作，字母和旋转是相反的（L -> 右旋 R-> 左旋），然后也是从后往前旋转（LR -> RL -> 左右）。

插入时，如果存在父子节点都是失衡的，我们先维护最下面的失衡节点（也是距离插入节点最近的那一个），通常只要下面平衡了，上面也会平衡。

最后补充一下删除，删除可能需要多次维护才能保证平衡，需要依次沿着祖先向上检查调整。

B站讲解：https://www.bilibili.com/video/BV1tZ421q72h/

B树(B-树)

蚌埠住了：B树就是B-树，"-“是个连字符号，不是减号 。B树也是一个自平衡树，但是不是二叉树，是多叉树。

B树的意义是什么呢？首先假如你是HDD，I/O那是毫无疑问的慢，如果要是随机读写那更慢了，顺序读写虽然也很慢，但是相对随机读写（磁头狂怒）也是大大滴快了。或者说，现在谁还有HDD，不都是SSD吗？SSD的随机读写不是快很多吗？但是呢我们知道一个重要的指标叫做4K随机读写，也是比顺序读写慢很多的。所以B树就是为数据库存储大量硬盘上的数据所诞生的，通过减少树的高度，减少访问次数，增加每一次访问的大小（读取较大而又不那么大的一块存储空间和读取单个数据节点用时差不多），进而加快查询速度。（常数复杂度的大胜利）

下面给出节点struct，m代表阶数，注意：key是Record的一个很小的部分，便于存储访问比较。因为存储的Record可能也是一个结构体，含有很多数据，这是我们让它按照里面的key来进行排序，实现分离索引与数据。（key越小，每次能读的关键字个数越多，也就是阶数也就可以越高，树高也就更矮，而要是用record索引，如果record存很多的话，读的个数就少了）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#define m 3
//m 代表B树的阶数
struct BTNode {
    int keynum;               // 结点中关键字个数，结点大小
    BTNode* parent;           // 父结点指针
    
    int key[m + 1];       // 关键字数组
    Record* recptr[m + 1];    // 记录指针数组
    
    BTNode* ptr[m + 1];       // 子结点指针数组
    
};

typedef BTNode* BTree;  // B-树类型

下面给出m阶B树的性质。（至于为什么上面数组是m+1，也就是m+1个，因为当插入已经有m的关键字的节点的时候可能存在溢出，这时要进行分裂）

  1. 除了根节点和叶子节点，每个节点的子节点个数n必须满足, $\lceil m/2 \rceil \leq n \leq m$。
  2. 如果根节点不是叶子节点，那么它至少有两个子节点。
  3. 所有的关键字升序排列。
  4. 关键字的个数$ k = n - 1$。
  5. 所有的叶子节点都在同一层。

下面进行查找操作（按照教材版本）（我把关键字设成int）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// 查找结果结构
struct Result {
    BTNode* pt;  // 指向找到的节点或插入位置的节点
    int i;       // 关键字在节点中的位置或插入位置
    int tag;     // 查找状态：1 表示成功，0 表示失败
};

// 在节点中查找关键字的位置
int Search(BTNode* p, int K) {
    int i = 0;
    while (i < p->keynum && K > p->key[i]) {
        i++;
    }
    //这时候i对应第一个大于等于K的key
    return i; 
}

// B 树查找函数
Result SearchBTree(BTNode* T, int K) {
    BTNode* p = T;      // 当前节点指针，初始指向根节点
    BTNode* q = NULL;   // 父节点指针，初始为 NULL
    bool found = false; // 查找标志，初始为 false
    int i = 0;          // 关键字索引，初始为 0

    // 在 B 树中查找关键字 K
    while (p && !found) {
        i = Search(p, K);  // 在节点 p 中查找 K 的位置
        if (i < p->keynum && p->key[i] == K) {
            found = true;  // 找到关键字 K
        } else {
            q = p;         // 记录父节点
            p = p->ptr[i]; // 继续在子树中查找
        }
    }

    // 返回查找结果
    if (found) {
        return {p, i, 1};  // 查找成功，返回节点 p 和关键字位置 i
    } else {
        return {q, i, 0};  // 查找失败，返回插入位置的节点 q 和位置 i
    }
}

下面进行插入操作，和BST一样，都是在查找失败的情况下才能进行插入，并且失败时候给出插入位置的指针。插入操作考的比较简单，你不需要掌握代码，你只能人肉运行就行。首先，明确的是我们插入的位置一定是最底层的叶子节点。

  1. 如果关键字个数小于m，那么直接插入
  2. 如果关键字个数等于m，不满足B树的性质了，那么就开始向上分裂！以中间元素$\lceil m / 2 \rceil$为分割点分开左右，然后将这个元素上移到父节点，原先的右侧关键词那些，变成该元素的右侧的一个子树，左侧的关键词那些变成左面的一个子树（包括关键词下面连着的一坨树）。
  3. 如果父节点也溢出了，那么重复这个分裂操作。如果根节点溢出那么创造一个新的根节点。

下面进行删除操作

  • 删除非叶结点元素最终都转换成删除叶结点元素
  • 叶结点元素
    • 没有下溢出无需调整
    • 下溢出
      • 兄弟够借：借（父下去兄上来）
      • 兄弟不够借：合并（父下来到兄弟节点再合并） （可能导致父结点下溢出，此时递归考虑）

B+树

B+树才是真正数据库用的（B-树不是，没想到吧）。

其性质和B树类似，区别如下：

  1. 关键字数量等于节点数量
  2. 关键字是子树的最大关键字值（由1，2可知，其子树类似于从关键字伸出去的一支，而不像B树那种左右两支，并且子树是包括父节点的关键字的）
  3. 只在叶子节点存储记录
  4. 每个叶子节点之间通过链表的方式连接

哈希

哈希函数一般是题目给你的，所以我们不做考虑。下面只包含地址冲突的解决方法。

开放定址法

假设关键字为key，有哈希函数$H(key) \qquad H_2(key)$

当$H(key2) == H(key1)$时，也就是发生了冲突，我们找到一个增量$d_i$，作为偏移找到另一个不冲突的地址。下面是$d_i$的三种取法。

  1. 线性探测$d_i = c * i$，每次走步长c
  2. 平方探测$d_i = \pm i^2 \quad (i = 0,1,2,3,..)$
  3. 双散列函数探测$d_i = i * H_2(key)$

链地址法

将具有同一散列地址的结点保存于各自的链表之中。

公共溢出区法

散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与基本表的相应单元进行比较，若相等，则查找成功；否则，再到溢出表中进行顺序查找。

平均查找长度ASL

只考虑查找成功的平均查找长度：

  1. 线性探测不冲突就是1，冲突就是实际几步，求和除以n
  2. 链地址，构建完哈希表后，1 * 所有有第一个节点值的个数+2 * 所有有第二个节点的链表个数 + 3 * 。。。。。，求和除以n

排序

冒泡

稳定排序。

插入

稳定排序。

常规插入很简单，这里提及一下没什么用，但是教材出现的表插入排序。本质上就是一个链表，不断有序插入另一个初始为空的链表，但是这里是用静态链表实现的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <limits.h> // 定义 MAXINT

typedef struct {
    int key;
    int next;
} Elem;

void LInsertionSort(Elem SL[], int n) {
    // 初始化
    SL[0].key = INT_MAX; // 头节点的 key 设置为最大值
    SL[0].next = 1;      // 头节点指向第一个记录
    SL[1].next = 0;      // 第一个记录指向头节点，形成循环链表

    // 表插入排序
    for (int i = 2; i <= n; ++i) {
        int j = 0; // 前驱节点
        int k = SL[0].next; // 当前节点

        // 在已排序的链表中找到插入位置
        while (SL[k].key <= SL[i].key) {
            j = k;
            k = SL[k].next;
        }

        // 将节点 i 插入到节点 j 和节点 k 之间
        SL[j].next = i;
        SL[i].next = k;
    }
}

希尔排序

不稳定排序。

基于插入排序改进，给出一个增量d，然后不断d / 2，直到d = 1，对于每一个d，就是每隔d个就取一个最后构成一组子序列，对这一组子序列进行插入排序。

快排

不稳定排序。

发现和正常人写的还是不一样。

在待排序的序列中任选一个数作为枢轴值（pivotkey），用双指针一个指向表的第一个值（low=1),另一个指向最后一个值（high=L.length)。

若high指针指向的值大于枢轴值，则high指针向前移动，否则将high与枢轴记录交换。

再从low指针的位置找到比枢轴值大的记录放到high的位置。

当low=high时将初始选中的枢轴值放在那个位置。

这样，在枢轴值两侧分为了两个都大于它或都小于它的两个子表，并按以上步骤不断递归最后得到正确的排序序列。

归并

稳定排序。

记住是先分再排序即可。

堆排

不稳定排序。一般考大根堆排序。通过数组表示堆，下标从1开始。

第一步先建堆，从最后一个不是堆的节点（下标为$\lfloor n / 2\rfloor$）（也就是不满足堆的性质，叶子节点显然是满足的），开始调整，调整后它也变成了堆，一直调到1为止。

大根堆对应着down操作，如果孩子比父亲大，那么就用最大的孩子替换父节点。

第二步是将堆的根也就是最大的元素和数组最后一个交换位置，再对根进行down操作。注意数组此时指的是无序数组的部分，和选择排序差不多。

计数排序

稳定的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值
    int max_val = *max_element(arr.begin(), arr.end());

    // 创建计数数组并初始化为0
    vector<int> count(max_val + 1, 0);

    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num]++;
    }

    // 累加计数数组，确定每个元素的最终位置
    // 类似前缀和
    for (int i = 1; i <= max_val; i++) {
        count[i] += count[i - 1];
    }

    // 创建临时数组存储排序结果
    vector<int> output(arr.size());

    // 从后向前遍历原数组，确保稳定性
    // 注意是原数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        //  count[arr[i]] - 1 最终位置 - 1 变成 0-index
        count[arr[i]]--;
    }

    // 将排序结果复制回原数组
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

基数排序

稳定排序。

使用最低位优先做法。

对于十进制数，我们创建10个桶，分别记录哪一位是0-9。这个桶我们用链表进行存储，拥有头指针和尾指针，便于尾插，先进先出。

第一步是分配，将某一位是数字x的放到x桶里面，只是指针指向而已，不是真的移动，因为是链表。

第二步是收集，对于每个桶如果非空，那么把它串起来。

最后是往高位重复上述操作。

时间复杂度$O(d*(n + r))$，d是最大位数，n是数据个数，r是桶的个数。

桶排序

  • 适用于均匀分布的输入

  • 将输入范围划分为m个桶

  • 记录关键字k分到第i个桶

    • i=f(k)

  • 每个桶分别排序

  • 依次输出每个桶