[数据结构与算法] 汇总-notes（考试记忆版）

阳光穿透心脏的1/2处 2023-06-22 03:30 2阅读 0赞

### 文章目录 ###

*  串
 *   *   *   *  KMP
 *  树
 *   *   *   *  树
             *  二叉树遍历
             *  二叉树线索化
             *  哈夫曼树
 *  图
 *   *   *   *  存储结构
             *  遍历
             *  无向连通图的最小生成树（Prim、Kruskal）
             *  有向图的强联通分量
             *  关节点与双连通图
             *  最短路径
             *   *  迪杰斯特拉算法
                 *  弗洛伊德算法
             *  AOV网
             *  AOE网
 *  排序
 *   *   *   *  插入排序
             *   *  交换排序
             *  选择排序
             *  归并排序
             *  外部排序
 *  查找

# 串 #

#### KMP ####

[KMP笔记链接][KMP]

【例题】模式串"ababaaababaa"，求nextval数组（下标从1开始，0记录长度）

【先求next数组】

1.  先画出表格（下标、T、next），并赋值特殊情况next\[1\]=0
2.  看下标`j`那列，记下前面的子串T\[1\]-T\[j-1\]，找出最长的前后缀
    
    1.  没有相同的前后缀 --> next\[j\] = 1
    2.  有相同的前后缀 --> 取最长的前后缀，长度为len --> next\[j\]=len+1

【再求nextval数组】

1.  画出nextval行，并赋值特殊情况nextval\[1\]=0
2.  【算法：求单元格(j, nextval)】先锁定下标为j的那一列 --> 然后看第j列，next那一行（j, next）的值t --> 然后看第t列，T那一行（t, T）–> 用(t, T)和(j, T)比较
    
    1.  (t, T)==(j, T) 的话：(j, nextval)=(t, nextval)
    2.  (t, T)≠(j, T)的话：(j, nextval)=(j, next)
3.  【举例：求单元格(5,nextval)】锁定下标为5的那一列 --> (5, next)=3 --> (3, T)=a --> (3, T)=a与(5, T)=a比较 --> 相同，则(5, nextval)=(3, nextval)=3
4.  【举例：求单元格(6, nextval)】锁定下标为6的那一列 --> (6, next)=4 --> (4, T)=b --> (4, T)=b与(6, T)=a比较 --> 不同，则(6, nextval)=(6, next)

<table> 
 <thead> 
  <tr> 
   <th>下标</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
   <th>10</th> 
   <th>11</th> 
   <th>12</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>T</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>next</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>2</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>nextval</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>4</td> 
   <td>2</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>4</td> 
  </tr> 
 </tbody> 
</table>

// T[0]存着字符串长度
    void getnext(char *T, int next[]) { 
    	int j=1,t=0;
    	next[1] = 0; //特殊状态
    	while (j<T[0]) {  //已知next[j]求next[j+1]，所以j不能等于T[0]
    		if (t==0 || T[j]==T[t]) { 
    			next[j+1] = t+1;
    			++j;++t;
    		}
    		else t = next[t];
    	}
    }
    // KMP搜索：下标0处存长度
    int KMP(char *str, char *substr, int next[]) { 
    	int i=1,j=1;
    	while (i<=str[0] && j<=substr[0]) { 
    		if (j==0 || str[i]==substr[j]) { 
    			++i;++j;
    		} else { 
    			j = next[j]; //失配，回溯
    		}
    	}
    	if (j>substr[0])  return i-substr[0]; //匹配成功
    	else: return 0; //匹配失败
    }

# 树 #

[树总结][Link 1]  
[树代码总结][Link 2]

【选择题】举特例，认真审题

1.一颗二叉树的度可以小于2  
2. n 0 = 1 + n 2 + 2 ∗ n 3 + . . . + ( m − 1 ) ∗ n m n\_0=1+n\_2+2\*n\_3+...+(m-1)\*n\_m n0=1\+n2\+2∗n3\+...\+(m−1)∗nm  
3. n = 2 h − 1 n=2^h-1 n=2h−1  
4. 层 结 点 树 = 2 h − 1 层结点树=2^\{h-1\} 层结点树=2h−1  
5. C 2 n n / ( n + 1 ) C\_\{2n\}^n/(n+1) C2nn/(n\+1)  
6. h = ⌊ l o g 2 n ⌋ + 1 = ⌈ l o g 2 ( n + 1 ) ⌉ h=\\lfloor\{log\_2n\}\\rfloor+1=\\lceil\{log\_2(n+1)\}\\rceil h=⌊log2n⌋\+1=⌈log2(n\+1)⌉  
7.度为m的哈夫曼树，叶子结点为n，非叶子结点为 ⌈ ( n − 1 ) / ( m − 1 ) ⌉ \\lceil\{(n-1)/(m-1)\}\\rceil ⌈(n−1)/(m−1)⌉  
8.前序序列、后序序列不能确定唯一的二叉树

#### 树 ####

树和森林的先序 —> 对应二叉树的先序  
树和森林的后序 —> 对应二叉树的中序

typedef struct CSNode{ 
    	Elem data;
    	struct CSNode *firstchild, *nextsibling;
    }CSNode, *CSTree;

#### 二叉树遍历 ####

【本质】遍历是把树变成一个一维的数组（即线性化）  
【技巧】在遍历的途中，我们可以新增一个pre，表示当前遍历的结点p，在数组的前一个结点。这个思想在很多地方都有应用。比如检查二叉树是否为排序二叉树，二叉树线索化

void LevelOrder(BiTree root) {  //层次遍历
    	BiTNode *que[MAXSIZE]; int front,rear; //队列
    	BiTNode *p;
    	front=rear=0;
    	if (root==NULL) return ; //空树，此句容易少写
    	que[rear]=root; rear=(rear+1)%MAXSIZE; //根结点入队列
    	while (front!=rear) {  //不为空
    		p=que[front]; front=(front+1)%MAXSIZE; //出队列
    		printf("%c", p->data); //访问
    		if(p->lchild!=NULL) { 
    			que[rear]=p->lchild; //左子树入队列
    			rear=(rear+1)%MAXSIZE;
    		}
    		if (p->rchild!=NULL) { 
    			que[rear]=p->rchild; //右子树入队列
    			rear=(rear+1)%MAXSIZE;
    		}
    	}
    }
    void PreOrder_norec(BiTree root) {  //先序非递归
    	// 思路：模拟遍历时指针p的移动
    	// 操作：1. 从根结点开始一直往左走，每经过一个结点先访问，然后放入栈；
    	// 2. 往左走不动了，结点出栈，然后往右走一步，继续上一步，直到往右走不动了
    	BiTNode *stack[MAXSIZE]; int top=-1; //栈
    	BiTNode *p = root; //指针
    	if (root==NULL) return ; 
    	do { 
    		while (p!=NULL) {  //一直往左走
    			printf("%c", p->data); //访问
    			stack[++top]=p; //入栈
    			p=p->lchild;	//往左走
    		}
    		// 往左走不动了
    		if (top!=-1) { 
    			p=stack[top--]; //出栈
    			p=p->rchild; //往右走一步
    		}	  
    	} while (top!=-1 || p!=NULL);
    }
    void InOrder_norec(BiTree root) {  //中序非递归
    	// 思路：模拟遍历时指针p的移动
    	// 操作：从根结点开始一直往左走，每经过一个结点不访问，放入栈；
    	// 往左走不动了，结点出栈，然后访问该结点，并往右走一步，继续上一步，直到往右走不动的时候
    	BiTNode *stack[MAXSIZE]; int top=-1;
    	BiTNode *p = root;
    	do { 
    		while (p!=NULL) {  //一直往左走
    			stack[++top]=p;
    			p=p->lchild;
    		}
    		// 往左走不动了
    		if (top!=-1) { 
    			p=stack[top--]; //出栈
    			printf("%c", p->data); //访问
    			p=p->rchild; //往右走一步
    		}
    	} while (top!=-1 || p!=NULL);
    }
    void PostOrder_norec(BiTree root) {  //后序非递归
    	/*PreOrder_norec中利用的思想是模拟遍历途中指针p的移动，但此方法有一个缺点，无法实现后序遍历 另一种思想：根据访问次序入栈并输出 【先序遍历的操作步骤】访问根，然后把右、左入栈（先入栈后输出，所以将右子树入栈） 【后序遍历】那么次方法下后序遍历应该怎么做？ 1. 后序序列：左 右 根 -> 逆后序序列：根 右 左 2. 想到先序序列：根 左 右。故后序序列可效仿先序序列非递归的方法 操作步骤：根结点入栈；然后出栈，将左右子树加入栈中；直到栈空为止。由此得到逆后序序列；然后将逆后序序列倒过来输出 */
    	BiTNode *stack[MAXSIZE]; int top=-1; //栈
    	BiTNode *inPostOrder[MAXSIZE]; int top2=-1; //第二个栈：用于存储逆后序序列
    	BiTNode *p;
    
    	if (root==NULL) return ; //虽然在这里，这句话可以省略。但还是要养成判断临界条件的好习惯
    	stack[++top] = root; //根结点入栈
    	while (top!=-1) { 
    		p=stack[top--]; //出栈
    		inPostOrder[++top2]=p; //访问
    		if (p->lchild!=NULL) stack[++top]=p->lchild; //右子树入栈
    		if (p->rchild!=NULL) stack[++top]=p->rchild; //左子树入栈
    	}
    	while (top2!=-1) {  //倒序输出逆后序序列
    		p = inPostOrder[top2--];
    		printf("%c", p->data); //正式访问
    	}
    }

#### 二叉树线索化 ####

【本质】把二叉树的空结点用起来，左子树表示线性化结果中前面的结点，右子树表示后一个结点  
【线索化的实现思路】创建一个pre，表示当前结点p线性化结果的前一个结点  
1.pre初始为NULL  
2.进入p时，有两种视角。一个是站在pre往后看p，一个是站在p往前看pre  
【代码】

typedef struct TBTNode{  //Thread BiTree Node
    	char data;
    	struct TBTNode *lchild, *rchild;
    	int ltag,rtag; //1为是线索，0为不是线索
    }TBTNode, *TBTree;
    void CreatePreThread(TBTNode *root) { 
    	// 对root所指的空间进行修改，故这里不要引用
    	TBTNode *pre=NULL; //遍历时的前一个结点
    	if(root==NULL) return ;
    	PreThread(root, pre); //线索化
    	// 【注意！】这里要处理最后一个结点，最后一个结点的右子树一定是空的
    	pre->rchild=NULL; pre->rtag=1;
    }
    void PreThread(TBTNode *p, TBTNode *&pre) {  
    	//对p所指的存储空间进行修改，所以p不用引用
    	//pre表示：在线性化序列中，T的前一个结点。是对pre变量的值进行修改，需要引用
    	if (p==NULL) return ;	
    
    	// 站在T的视角，即可以往前看pre
    	if (p->lchild==NULL) {  //不管p是不是线性序列的第一个，如果是空都要线索化
    		p->ltag=1; p->lchild=pre; //线索化
    	}
    	// 站在pre的视角，即可往后看T
    	if (pre!=NULL && pre->rchild==NULL) {  //pre的rchild为空
    		pre->rtag=1; pre->rchild=p; //线索化
    	}
    
    	//前进，下一个结点
    	pre=p;
    	//因为是前序，已经做了线索化，所以不是线索的情况再递归
    	if (p->ltag==0) PreThread(T->lchild, pre);
    	if (p->rtag==0) PreThread(T->rchild, pre);
    }

【补充】二叉树线索化的重要问题还有它的基本操作  
1.求树的第一个结点，最后一个结点  
2.求当前结点p的前一个或后一个  
3.遍历  
【思路】严格抓住二叉树线性结果序列，明确它的前一个后一个是在哪个位置来写代码。后两个问题可以调用第一个问题来处理

// 以中序线索二叉树为例
    TBTNode *First(TBTNode *p) {  //第一个：p左子树中第一个没有左孩子的结点
    	if (p==NULL) return NULL;
    	while (p->ltag==0) p=p->lchild; //如果左边有结点，一直往左走，直到没有结点
    	return p;
    }
    TBTNode *Last(TBTNode *p) {  //最后一个：右子树当中没有右孩子的结点
    	if (p==NULL) return NULL;
    	while (p->rtag==0) p=p->rchild;
    	return p;
    }
    TBTNode *Next(TBTNode *p) {  //下一个
    	if (p==NULL) return NULL;
    	if (p->rtag==1) return p->rchild; //是线索直接返回
    	else return First(p->lchild);
    }
    TBTNode *Prior(TBTNode *p) {  //上一个：左边最后一个
    	if (p==NULL) return NULL;
    	if (p->lchild==1) return p->lchild; //是线索直接返回
    	else return Last(p->lchild); //左边最后一个
    }
    void Order(TBTNode *root) { 
    	for (TBTNOde *p=First(root); p!=NULL; p=Next(p)) Visit(p); 
    }

#### 哈夫曼树 ####

1.哈夫曼m叉树中只有 n 0 n\_0 n0和 n m n\_m nm的结点，故有公式 n 0 = 1 + ( m − 1 ) ∗ n m n\_0=1+(m-1)\*n\_m n0=1\+(m−1)∗nm  
2. n 0 n\_0 n0个叶子结点的哈夫曼树，共有 2 ∗ n 0 − 1 2\*n\_0-1 2∗n0−1个结点  
3.权值越大的结点，距离根越近；带权路径最短（叶子结点权重\*长度 求和）  
4.由一组结点得到的哈夫曼树可能不唯一（有相同结点、左右子树互换）  
5.构树：每次从左到右选择最小的m个记录合成一个；若结点不够用0补充，但要重新构树

typedef struct node{ 
    	int w;
    	struct node *lchild,*rchild;
    }BiTNode, *BiTree;
    
    BiTree CreateHufferman(int num[], int n);
    int GetWPL(BiTree T, int pathLen);
    void GetCode(BiTree T, int pathLen);
    
    BiTree CreateHufferman(int num[], int n) { 
    	BiTree *trees; //trees用于保存哈夫曼树构造过程的n棵树
    	int min1,min2; //min1最小结点的下标，min2第二小结点的下标
    	BiTNode *tmp; int i,j;
    
    	trees = (BiTree *)malloc(sizoef(BiTree) * n); //BiTree[]指针数组统一管理哈夫曼的叶子结点
    	for (i=0; i<n; i++) {  //创造哈夫曼的叶子结点，并放入trees统一管理
    		tmp = (BiTNode *)malloc(sizeof(BiTNode));
    		tmp->w = num[i];
    		tmp->lchild = tmp->rchild = null;
    		trees[i] = tmp;
    	}
    	for (i=1; i<n; i++) { //构造哈夫曼树，循环n-1次
    		min1 = min2 = -1;
    		for (j=0; j<n; j++) {  //找出从左到右的第一、二个结点
    			if (trees[j]!=NULL) { 
    				if (min1==-1) min1 = j; //第一个结点
    				else if (min2==-1) min2 = j; //第二个结点
    				else break; //找完，退出
    			}
    		}
    		for (j=min2; j<n; j++) {  //找到最小结点和次小结点
    			if (trees[j]!=NULL) { 
    				if (trees[j]->w < min1) {  //比最小结点还小
    					min2 = min1; //注意！最小结点变成了次小结点
    					min1 = j;	
    				} else if (trees[j]->w < min2) {  //比最小结点大，比次小结点小
    					min2 = j;
    				}
    			}
    		}
    		// 合并min1，min2
    		tmp = (BiTNode *)malloc(sizeof(BiTNode));
    		tmp->w = trees[min1]->w + trees[min2]->w;
    		tmp->lchild = trees[min1];
    		tmp->rchild = trees[min2];
    		trees[min1]=tmp;
    		trees[min2]=NULL;
    	}
    	free(trees);
    	return tmp;
    }
    // 调用：GetWPL(hfmTree, 0); 根结点的路径长度为0
    int GetWPL(BiTree T, int pathLen) { 
    	if (T==NULL) return 0; //检测空树情况
    	if (T->lchild==NULL && T->rchild==NULL) {  //若是叶子结点
    		return T->w * pathLen;
    	}
    	return GetWPL(T->lchild, pathLen+1) + GetWPL(T->rchild, pathLen+1);
    }
    // 调用：GetCode(hfmTree, 0); 根结点的路径长度为0
    void GetCode(BiTree T, int pathLen) { 
    	static char code[2*MAX-1]; //静态变量保存编码值
    
    	if (T==NULL) return ; //检测空树情况
    	if (T->lchild==NULL && T->rchild==NULL) {  //叶子结点
    		code[pathLen] = ‘\0’; //赋值结束符
    		printf(“结点值%d 编码值：%s\n”, code); //输出此叶子结点编码情况
    		return ; //退出
    	}
    	
    	code[pathLen]=‘0’; GetCode(T->lchild, pathLen+1); //往左走
    	code[pathLen]=‘1’; GetCode(T->rchild, pathLen+1); //往右走
    }

# 图 #

[图汇总][Link 3]

1.【完全图】任意两顶点都有边（无向完全 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2条，有向 n ( n − 1 ) n(n-1) n(n−1)）  
2.【连通图】任意两点可互通（无向叫连通图，有向叫强连通图）  
3.【极大的连通子图（极大是相对于顶点而言）】不能再大，再加入一个顶点就不满足任意两点互相连通了（无向叫连通分量、极大连通子图；有向叫强连通分量、极大强连通图）  
4.【极小的连通子图（极小是相对于边而言）】子图中两两已经连通且边最小，再加一个就会构成环（无向图叫极小连通子图，有向图没有这种东西）

#### 存储结构 ####

// 邻接矩阵
    typedef struct{ 
    	char vexs[MAXSIZE]; //顶点信息
    	float arcs[MAXSIZE][MAXSIZE]; //邻接表
    	int vernum,arcnum;
    }MGraph; //邻接矩阵
    // 邻接表
    typedef struct ArcNode{ 
    	int adjvex; //边所指的顶点
    	int w;	    //边的权重信息
    	struct ArcNode *next; //下一个弧
    }ArcNode; //边信息
    typedef struct VNode{ 
    	char data; //顶点信息
    	ArcNode *firstarc; //第一条弧
    }VNode; //顶点
    typedef struct{ 
    	VNode vexs[MAXSIZE]; //顶点集
    	int vernum, arcnum;
    }ALGraph; //邻接表

#### 遍历 ####

// DFS_rec O(n+e)
    int visit[MAXSIZE] = { 0};
    void DFS(ALGraph G) { 
    	int i;
    	for (i=0; i<G.vernum; ++i) visit[i]=0;
    	for (i=0; i<G.vernum; ++i) //此图可能是非连通图，从一个顶点可能走不到所有顶点
    		if (visit[i]==0) DFSTool(G, i);
    }
    void DFSTool(ALGraph G, int v) { 
    	ArcNode *p;
    	visit[v]=1;
    	printf(“%c\t”, G.vexs[v].data);
    	for (p=G.vexs[v].firstarc; p; p=p->nextarc) { 
    		if (visit[p->adjvex]==0) DFSTool(G, p->adjvex);
    	}
    }
    // DFS_norec
    void DFS_norec(ALGraph G) { 
    	int visit[MAXSIZE]; //访问数组
    	int stack[MAXSIZE]; int top=-1; //栈
    	int i,j;
    	ArcNode *p;
    	for (i=0; i<G.vernum; ++i) visit[i]=0; //访问数组初始化
    	for (i=0; i<G.vernum; ++i) {  //遍历顶点
    		if (visit[i]) continue; //此结点已经访问过，退出
    		//此结点还未被访问过，从它开始
    		top=-1; //栈清空
    		stack[++top]=i; //此结点入栈
    		visit[i]=1; printf(“%c\t”, G.vers[i].data); //访问此结点
    		while (top!=-1) {  //栈中还有元素
    			j = stack[top]; //得到栈顶，不出栈！
    			for (p=G.vers[j].firstarc; p; p=p->next) {  //从这个顶点开始遍历
    				if (visit[p->adjvex]==0) {  //该结点没有访问过
    					visit[p->adjvex]=1; printf(“%c\t”, G.vers[p->adjvex].data); //访问
    					stack[++top]=p->adjvex; //入栈
    					break; //退出此次循环，开始从p->adjvex顶点往下走
    				}
    			}
    			if (p==NULL) —-top; //如果上面for循环正常结束（即p==NULL）,表明stack[top]的邻边已经遍历完，那就要让它出栈
    		}
    	}
    }
    // BFS O(n+e)
    int visit[MAXSIZE]; //外面定义访问数组
    void BFS(ALGraph G) { 
    	int i;
    	for (i=0; i<G.vernum; ++i) visit[i]=0; //初始化访问数组
    	for (i=0; i<G.vernum; ++i)  //不一定是连通图，第一个结点不能够到达任意一个结点
    		if (visit[i]==0) BFSTool(G, i);
    }
    void BFSTool(ALGraph G, int v) { 
    	int que[MAXSIZE]; int front,rear; //队列
    	ArcNode *p;
    	int i;
    	
    	front=rear=0; //队列初始化
    	que[rear]=v; rear=(rear+1)%MAXSIZE; //v入队列
    	while (front!=rear) {  //队列不为空
    		i=que[front]; front=(front+1)%MAXSIZE; //出队列
    		visit[i]=1; printf(“%c\t”, G.vexs[i].data); //访问
    		for (p=G.vexs[i].firstarc; p; p=p->nextarc) //把该结点所有领接节点入队列
    			if (visit[p->adjvex]==0) { 
    				que[rear]=p->adjvex;
    				rear=(rear+1)%MAXSIZE;
    			}
    	}
    }

【时间复杂度】有顶点都进队一次，所有边都被访问一次，因此总次数为n+e，即O(n+e)

#### 无向连通图的最小生成树（Prim、Kruskal） ####

1.无向连通图的最小生成树：删除无向连通图的边，让其只剩下n-1条且任意两点还是连通的  
2.最小生成树：边权重之和最小  
3.最小生成森林：对非连通图而言的最小生成森林

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th><a href="https://blog.csdn.net/summer_dew/article/details/81660483" rel="nofollow">Prim普利姆</a></th> 
   <th><a href="https://blog.csdn.net/summer_dew/article/details/81660723" rel="nofollow">Kruskal克鲁斯卡尔</a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>思想</td> 
   <td>①以顶点为操作对象，每次选择一个顶点并入子图；<br>②顶点的选择依据：子图到其他顶点的最短路径</td> 
   <td>①以边为操作的主要单位：每次并入一条边；<br>②选择边的依据：当前最小边，且不构成回路</td> 
  </tr> 
  <tr> 
   <td>数据结构</td> 
   <td>①子图vest[i]：结点i是否已并入生成树；<br>②lowcost[i]：结点i到子树的最短边权重</td> 
   <td>①Road：存储图的所有边<br>②用<a href="https://blog.csdn.net/summer_dew/article/details/83036947" rel="nofollow">并查集</a>检查是否构成回边</td> 
  </tr> 
  <tr> 
   <td>适合</td> 
   <td>稠密图（时间复杂度与顶点有关系，与边数没有关系）</td> 
   <td>稀疏图（时间复杂度由边数决定）</td> 
  </tr> 
  <tr> 
   <td>时间复杂度</td> 
   <td><span><span><span> O ( n 2 ) O(n^2) </span><span><span><span style="height: 1.06411em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span><span>n</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span><span>)</span></span></span></span></span>（并入n-1个顶点，每次并入要选出最小者–&gt;n²）</td> 
   <td><span><span><span> O ( e l o g e ) O(eloge) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span>e</span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span>e</span><span>)</span></span></span></span></span>（算法主要操作是对边e的排序上，取决于排序算法的时间复杂度）</td> 
  </tr> 
 </tbody> 
</table>

// Prim：以顶点为单位，每并入一个顶点(vset[]),更新到其余各点的最短开销(lowcost[])
    #define INF 10e7
    int Prim(MGraph G, int v0) { 
    	int vset[MAXSIZE];   	//vset[i]==1即表示顶点i已并入最小生成树
    	// 当前生成树到顶点w的最小边为w-lownode[w]，其权重为lowcost[w]
    	int lowcost[MAXSIZE];
    	int lownode[MAXSIZE];
    	int sum;	//最小生成树的开销
    	int min, w; //选出每次最优的顶点
    	int i,j;
    	// 初始化
    	for (i=0; i<G.vernum; i++) { 
    		vset[i] = 0;
    		lowcost[i] = INF;
    	}
    	// 将v0并入生成树
    	vset[v0]=1;
    	sum=0;
    	for (i=0; i<G.vernum; i++) { 
    		lowcost[i] = G.arcs[v0][i];
    		lownode[i] = v0;
    	}
    	// 还需要n-1个顶点并入
    	for (i=2; i<=G.vernum; i++) { 
    		// 找当前生成树离其他顶点的最短距离
    		min = INF;
    		for (j=0; j<G.vernum; j++) { 
    			if (vset[j]==0 && lowcost[j]<min) { 
    				min = lowcost[j];
    				w = j;
    			}
    		}
    		// 将w并入
    		vset[w] = i; //第i个并入树的结点
    		sum += lowcost[w];
    		// 更新lowcost
    		for (j=0; j<G.vernum; j++) { 
    			if (vset[j]==0 && G.arcs[w][j]<lowcost[j]) //新并入的结点到剩余个点会不会更近
    				lowcost[j]=G.arcs[k][j];
    				lownode[j]=w;
    		}
    	}
    	// 若要创建出此最小生成树，可以根据lowcost[]和lownode[]创建
    	return sum;
    }
    // Kruskal：每次选择最短边，并入时检查是否会构成回路
    typedef struct{ 
    	int a,b; //边的两点
    	int w;   //边的权重
    }Road; //边
    Road roads[MAXSIZE]; //边集
    int parent[MAXSIZE]; //并查集：i结点的父亲是parent[i]；parent[i]==i表示i即为根
    int getRoot(int a) { 
    	while (a!=parent[a]) a=parent[a]; //a的父亲是parent[a]
    		//如果是它自己，则表示找到根
    	return a;
    }
    int Kruskal(MGraph G, Road roads[]) { 
    	int i, a_root, b_root;
    	int sum=0;
    	for (i=0; i<G.vernum; ++i) parent[i]=i;
    	sort(roads, G.arcnum); //将roads按照w从小到大排列
    	for (i=0; i<G.arcnum; ++i) {  //遍历所有的边
    		a_root = getRoot(roads[i].a); //得到顶点a的根
    		b_root = getRoot(roads[i].b); //得到顶点b的根
    		if (a_root!=b_root) {  //不产生回路
    			parent[a] = b;	//更新并查集，将a接到b的下面
    			sum += road[i].w; //更新权重
    			//若要创建出这个最小生成树，可以在这里创建a，b，并连接边
    		}
    	}
    	return sum;
    }

#### 有向图的强联通分量 ####

【强联通】在有向图中，两顶点相互可达  
【强联通图】有向图中任意两点相互可达  
【强联通分量】非强联通图的子图，且子图中任意两点相互可达  
【极大强连通分量】强连通分量中顶点最多的那个

【Kosaraju算法】  
1.求图G的逆图R  
2.对逆图R进行DFS，得到DFS生成森林，求得生成森林的后序序列postorder  
3.以postorder\[\]从后面往前的顺序对原图G进行DFS，即得到好几个生成树trees，这些生成即是强联通分量  
4.若要求极大的强连通分量，求trees中顶点最多的那个

#### 关节点与双连通图 ####

【关结点】若删除V 与 V上的所有边后，图不在连通，则v就是该图的关节点  
【重（双）连通图】没有关节点的图称为双连通图

【判断顶点V是否为关节点】  
1.删除V和V上的所有边获得子图SG  
2.从SG的一个顶点出发DFS，得到遍历结果visit\[\]  
3.看visit\[\]中除了V是否全部访问到。全部访问到则表明V不是关结点

【判断是否为双连通图】判断每个顶点是否为关结点。都不是，则是双连通图

#### 最短路径 ####

##### 迪杰斯特拉算法 #####

【手算答题模版】  
![在这里插入图片描述][2019102214114695.png]  
用dist\[\]存放最短路径长度，path\[\]存放最短路径![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]

// Dijkstra：求一个顶点到其余各点的距离
    void Dijkstra(MGraph G, int v0, int dist[], int path[]) { 
    	// v0到w的最短距离为dist[]，路径为v0->...->path[w]->w
    	int set[MAXSIZE]; //已考虑的顶点
    	int min, i, j, u;
    	// 初始化、从v0到其他各点
    	for (i=0; i<G.vernum; ++i) { 
    		dist[i] = G.arcs[v0][i]; //初始化距离：v0->i
    		set[i] = 0;				 //还未考虑任何顶点
    		if (G.arcs[v0][i]<INF) path[i] = v0; //若v0->i有路，则当前的最短路径即是i->v0
    		else path[i] = -1; //没有路，即为-1
    	}
    	set[v0]=1; path[v0]=-1; //把结点v0设置为已考虑
    	for (i=1; i<G.vernum; ++i) {  //还需要考虑n-1个顶点
    		//找出当前权重最短的边
    		min = INF;
    		for (j=0; j<G.vernum; ++j) { 
    			if (set[j]==0 && dist[j]<min ) { 
    				u = j;
    				min = dist[j];
    			}
    		}
    		set[u]=1; //将此边的另一个顶点并入
    		//更新最短路径dist[]：查看顶点u做为中转站，路线会不会更近
    		for (j=0; j<G.vernum; ++j) { 
    			if (set[j]==0 && dist[u]+G.arcs[u][j]<dist[j]) { 
    				dist[j] = dist[u] + G.arcs[u][j];
    				path[j] = u;
    			}
    		}
    	}
    }
    void PrintPath(int path[], int a) { 
    	int stack[MAXSIZE], top=-1;
    	// 以由叶子结点到根结点的顺序将其入栈
    	while (path[a]!=-1) { 
    		stack[++top] = a;
    		a = path[a];
    	}
    	stack[++top] = a;
    	// 倒过来输出
    	while (top!=-1) { 
    		printf(“%d ”, stack[top—-]);	
    	}
    	printf(“\n”);
    }

##### 弗洛伊德算法 #####

【手算答题模版】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70 1]

void PrintPath(MGraph G, int u, int v, int path[][max]) { 
    	int midNode;
    	if ( path[u][v]==-1 ) { 
            print("<%C,%c>", G.vers[u], G.vers[v]); //直接输出
    	} else { 
    		mindNode = path[u][v];
    		PrintPath(u, mid, path); //mid前半段路径
    		PrintPath(mid, v, path); //mid后半段路径
    	}
    }
    void Floyd(MGraph G, int A[][maxSize], int Path[][maxSize]) { 
    	int i,j,k;
    	// 初始化
    	for (i=0; i<G.vernum; i++) { 
    		for (j=0; j<G.vernum; j++) { 
    			A[i][j] = G.arcs[i][j];
    			Path[i][j] = -1;
    		}
    	}
    	for (k=0; k<G.vernum; ++k) {  //中间经过k点有没有更近呢？
    		for (i=0; i<G.vernum; ++i) { 
    			for (j=0; j<G.vernum; ++j) { 
                    // i->j 对比 i->k->j
    				if (A[i][j]>A[i][k] + A[k][j]) { 
    					A[i][j] = A[i][k] + A[k][j];
    					Path[i][j] = k;
    				}
    			}
    		}
    	} 
    }

#### AOV网 ####

【AOV网】Activity On Vertex network。有向无环图；顶点表示活动；边表示活动的次序  
【拓扑排序序列】判断有向图是否有回路

// 拓扑排序：O(n+e)删除入度为0的顶点和边，直到入度为0的边
    int TopSort(ALGraph &G) { 
    	int v, w, n;
    	int stack[MAXSIZE], top=-1; //存放入度为0的顶点
    	ArcNode *p;
    	// 将图中入度为0的顶点入栈
    	for (v=0; v<G.vernum; ++v) { 
    		if (G.vers[v].cnt==0) stack[++top] = v;
    	}
    	n = 0; //已删除n个结点
    	while (top!=-1) {  //还有入度为0的顶点
    		v = stack[top—-]; //出栈
    		// 删除此顶点
    		++n;
    		for (p=G.vers[v].firstarc; p; p=p->nextarc) {  //删除邻边
    			w = p->adjvex;
    			—- (G.vers[w].cnt);
    			if (G.vers[w].cnt==0) stack[++top] = w; //若又出现入度为0的顶点，加入栈
    		}
    	}
    	if (n==G.vernum) return 1; //拓扑排序成功，为AOV网
    	else return 0; //拓扑排序失败，该有向图不为AOV网，有回路
    }
    // 逆拓扑有序序列：出度为0的顶点先输出，即DFS时第一个退出的顶点
    int visit[MAXSIZE];
    void RTopSort_DFS(ALGraph &G, int v) { 
    	ArcNode *p;
    	visit[v] = 1;
    	// 访问v的顶点
    	for (p=G.vers[v].firstarc; p; p=p->nextarc) { 
    		if (visit[p->adjvex]==0) RTopSort_DFS(G, p->adjvex);
    	}
    	// v的顶点都访问完了，说明顶点v没有下一条边了，也就意味着此时v的出度为0
    	printf(“%c”, G.vers[v].data ); //输出
    }

#### AOE网 ####

【AOE网】Activity On edge network有向无环图；顶点表示事件；边表示活动且边有权值  
【ve】即事件v的最早发生时间(earliest)。不休息紧锣密鼓的把V上游活动全部做完，即取起点到V路径中的max（`{上一个顶点ve+边}的最大值，ve(源点)=0`）  
【vl】即事件v的最迟发生时间(latest)。中途想休息一下，但是不能让工期延长的最迟动工时间(`{下一个顶点的vl-边}的min，vl(汇点)=ve(源点)`）  
【ee】即活动e的最早发生时间。中途不休息赶紧把上游活动做完需要的时间（`ee(i)=ve(边的头顶点)`）  
【el】即活动e的最迟发生时间。中途想休息一下，但是不能让工期延长的最迟动工时间（`vl(边的尾顶点)-边权重`）  
【关键活动】中途不能休息，一休息就会延长工期的活动，即`ee==el`的活动  
【关键路径】关键活动所构成从源点到汇点的路径（可能有多条），此为整个工程的完成的最短时间（即中途一刻也不休息，完成工程的时间）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70 2]  
【代码】

// 方法一：关键路径即图中源点到汇点的最长路径
    // 用拓扑排序求的源点S和汇点E；修改最短路径算法为求最长路径算法，求得SE之间的最长路径；并通过回溯求出所有的路径
    // 方法二：利用关键路径算法
    typedef struct ArcNode{ 
    	int adjvext;
    	int w;
    	struct ArcNode *nextarc;
    }ArcNode;
    typedef struct{ 
    	char data;
    	int cnt; //记录该结点的入度
    	ArcNode *firstarc;
    }VNode;
    typedef struct{ 
    	VNode vers[MAXSIZE];
    	int vernum, arcnum;
    }ALGraph;
    // 计算每个结点的入度
    void CntVNodeInDegree(ALGraph &G) { 
    	for (int v=0; v<G.vernum; v++) { 
    		for (ArcNode *p=G.vers[v].firstarc; p; p=p->next) { 
    			int w = p->adjvex; //边v->w
    			G.vers[w].cnt++;   //w的入度+1
    		}
    	}
    };
    // 拓扑排序：order[]为拓扑有序序列，返回1表示图为有向无环图
    int TopSort(ALGraph &G, int order[]) { 
    	int stack[MAXSIZE], top=-1; //存放入度为0的顶点
    	int v,w,n;
    	// 将图中入度为0的顶点入栈
    	for (i=0; i<G.vernum; ++i)
    		if (G.vers[i].cnt==0) stack[++top] = i;
    	n=0; //已删除n个顶点
    	while(top!=-1) {  //还有入度为0的顶点
    		v = stack[top—-]; //出栈
    		//删除此顶点
    		order[n] = v; n++;
    		for (ArcNode *p=G.vers[v].firstarc; p; p=p->next) { 
    			w = p->adjvex;
    			—-(G.vers[w].cnt);
    			if (G.vers[w].cnt==0) stack[++top]=w;
    		}
    	}
    	if (n==G.vernum) return 1;
    	else return 0;
    }
    // 关键路径
    int CriticalPath(ALGraph &G, int **map) { 
    	// map[G.vernum][G.vernum]为G的邻接矩阵；map[v][w]=1表示v->w为关键活动。初始值为INF，表示不是关键活动
    	int topo[G.vernum];
    	int ve[G.vernum] = { 0}, vl[G.vernum] = { 0};
    	int v, w;
    	ArcNode *p;
    	// 拓扑排序：检查是否为有向无环图，并获得拓扑序列存到topo[]中
    	if (TopSort(G, topo)==0 ) return 0;
    	// 计算每个顶点的ve：ve[]初始值为0，ve[w]=Max{ve[v] + vw的边权重}
    	for (i=0; i<G.vernum; i++) ve[i]=0; //ve[]初始值为0
    	for (i=0; i<G.vernum; i++) { 		//遍历拓扑有序序列
    		v = topo[i];					//得到拓扑有序序列的顶点
    		// 计算它的下一个顶点：v->w
    		for (p=G.vers[v].firstarc; p; p=p->next) { 
    			w = p->adjvex; 				//它的邻边v->w
    			if (ve[w] < ve[v]+p->w) 	//ve(尾) ve(头)+边。取最大值
    				ve[w] = ve[v]+p->w;		//ve(尾)=ve(头)+边
    		}
    	}
    	// 计算每个顶点的vl：vl[]初始值为ve[汇点]，vl[w]=min{vl[v] - vw边的权重}
    	v = topo[G.vernum-1]; //汇点
    	for (i=0; i<G.vernum; ++i) vl[i]=ve[v]; //vl[]初始值为ve[汇点]
    	for (i=G.vernum-1; i>=0; i—-) { 			//从后往前遍历拓扑有序序列
    		v = topo[i];						//拓扑有序序列的顶点
    		// 计算它的下一个顶点：v->w
    		for (p=G.vers[v].firstarc; p; p=p->next) { 
    			 w = p->adjvex; 				//它的邻边v->w
    			 if (vl[v] > vl[w]-p->w) 		//vl(头) vl(尾)-边。取最小值
    			 	vl[v] = vl[w]-p->w;		//vl(头)=vl(尾)-边
    		}
    	}
    	// 求关键活动
    	int ee, el; //当前活动的ee、el
    	for (v=0; v<G.vexnum; v++) { 						//遍历每个顶点
    		for (p=G.vers[i].firstarc; p; p=p->nextarc) { 	//遍历该顶点的边
    			w = p->adjvex;		//它的邻边v->w
    			ee = ve[v];			//ee(vw)=ve(v)
    			el = vl[w]-p->w;	//el(vw)=vl(尾)-边
    			if (ee==el) { 		//为关键活动
    				printf(“(%c->%c)\t”, G.vers[v].data, G.vers[w].data);
    				map[v][w] = 1; //v-w边为关键活动
    			}
    		}
    	}
    
    	return 1;
    }
    void PrintAllCriticalPath(ALGraph &G, int **map, int start, int end) { 
    	static char path[MAXSIZE] = { ‘\0’};
    	static int index = 0;
    	// 关键路径不只一条，打印出所有的关键路径
    	path[index++] = G.vers[start].data;
    	if (start==end) { 
    		path[index] = ‘\0’;
    		printf(“%s\n”, path);
    	} else { 
    		for (ArcNode *p=G.vers[start].firstarc; p; p=p->nextarc) { 
    			int w = p->adjvex;
    			if (map[start][w]==1) { 
    				PrintAllCriticalPath(G, map, w, end);
    			}
    		}
    	}
    	index—-;
    }

# 排序 #

<table> 
 <thead> 
  <tr> 
   <th>性能</th> 
   <th>分析</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>特殊：基数排序O(d(n+r<sub>d</sub>))；d为关键字位数，r为一位的关键字取值范围，n为数量<br><code>“快些以nlog2n的速度归队”：快（快速排序）、些（希尔排序）、归（归并排序）、队（堆排序）</code></td> 
  </tr> 
  <tr> 
   <td>最坏时间复杂度</td> 
   <td>1. 快速排序的时间复杂度为O(n2)<br>2. 其他都和平均情况相等</td> 
  </tr> 
  <tr> 
   <td>最好时间复杂度</td> 
   <td>1. 直接插容易插变成O(n)，起泡起的好变成O(n)<br>2. “容易插”、“起的好”都是指初始序列已经有序</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>1. 快速排序O(log2n) <br>2. 归并排序O(n)<br>3. 基数排序O(rd)<br>4. 其他都是O(1)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>【助记】<code>考研复习痛苦啊，心情不稳定（不稳定的算法），快（快速排序）些（希尔排序）选（简单选择排序）一堆（堆排序）好友来聊天吧</code>。这4种不是稳定的，其他自然都是稳定的</td> 
  </tr> 
  <tr> 
   <td>排序原理</td> 
   <td>1. 经过一趟排序，就能保证一个元素到达最终位置：起泡、快速（交换类的两种），简单选择、堆（选择类的两种） <br>2. 排序方法的元素比较次数和原始序列无关：简单选择排序、折半插入排序<br>3. 排序方法的排序趟数和原始序列有关：交换类的排序<br>4. 比较类的算法，在最坏的情况下能达到最好的时间复杂度为O(nlog<sub>2</sub>n)</td> 
  </tr> 
  <tr> 
   <td>其他</td> 
   <td>简单普通的排序方法的升级版的平均复杂度都为O(nlog2n)，最坏的情况都是和没改进的时候一样O(n^2)，除了堆排序</td> 
  </tr> 
 </tbody> 
</table>

#### 插入排序 ####

// 直接插入排序
    void InsortSort(int arr[], int n) { 
    	int i,j,tmp;
    	for (i=1; i<n; i++) {  //i从左到右：[1, n-1]
    		tmp = arr[i];	  //取下arr[i]
    		for (j=i-1; j>=0 && tmp<arr[j]; j—-) {  //j是i的前一个元素：[0, i-1]
    			// 【注意】tmp与arr[j]的对比必须放在for中判断。若分开判断，最好最坏情况都是O(n^2)
    			// 【注意】若tmp==arr[j]，则不交换，保持原定相对位置，保证排序的稳定性
    			arr[j+1] = arr[j];
    		}
    		arr[j+1]=tmp; //tmp比arr[j]小，或相等。则tmp放在arr[j]的一位
     	}
    }
    // 折半插入排序
    void BiInsertSort(int arr[], int n) { 
    	int i,j,tmp;
    	int low,high,mid;
    	for (i=1; i<n; i++) {  //i从左到右：[1,n-1]
    		tmp = arr[i];		//取下arr[i]
    		low=0; high=i-1;	//确定折半查找的范围
    		while (low<=high) { 	//【注意】low==high也需要判断low位置与tmp的大小
    			mid = (low+high)/2;
    			if (arr[mid]<=tmp) low=mid+1;
    				//【注意】若arr[]出现与tmp相同的数字，则插入位置在后面，保持排序稳定性
    			else high=mid-1;
    		}
    		// 插入位置是arr[low]，则把[low, i-1]的元素后移
    		for (j=i; j>low; j—-) { 
    			arr[j] = arr[j-1];
    		}
    		arr[low]=tmp; //放下tmp
    	}
    }
    // 希尔排序
    // 【增量选择原则】最后一个值一定取1；增量序列中值应尽量没有除1之外的公因子
    void ShellSort(int arr[], int n) { 
    	int i,j,tmp;
    	int gap;
    	for (gap=n/2; gap>0; gap/=2) {  //默认增量序列：除以2且大于0
    		for (i=gap; i<n; i+=gap) {  //【注意】i是从左到右的第二个元素，位移间隔是gap
    			tmp = arr[i]; //取下arr[i]
    			for (j=i-gap; j>=0 && tmp<arr[j]; j-=gap) { //【注意】j是i的前一个元素，位移间隔是gap
    				// 【注意】若tmp==arr[j]，则arr[j]不后移，保持原始相对位置，保证排序的稳定性
    				arr[j+gap] = arr[j]; //注意：tmp比arr[j]小，则arr[j]后移
    			}
    			arr[j+gap]=tmp; //注意；arr[j]比tmp大，则tmp应该放在j的后一位
    		}
    	}
    }

##### 交换排序 #####

// 冒泡排序
    void BubbleSort(int arr[], int n) { 
    	int i,j,tmp;
    	int flag=1; //此趟是否有发生交换
    	for (i=n-1; i>=1 && flag; i—-) {  //无序序列的右边界，每趟完成最后边多填一个有序元素，一共需要n-1趟
    		flag = 0; //标记这一趟没有交换发生
    		for (j=0; j<i; j++) {  //遍历无序序列，判断是否要交换，[0, i-1]
    			if (arr[j]>arr[j+1]) { 
    				tmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;
    				flag=1;
    			}
    		}
    	}
    }
    // 快速排序
    void QuickSort(int arr[], int low, int high) { 
    	int i,j, tmp;
    	if (low<high) {  //low==high表明只剩下一个元素，不需要排序了
    		tmp = arr[low]; //哨兵取最左边这个，i的位置空出来了
    		//找到tmp存放的位置，使小于tmp的放左边，大于tmp的放右边
    		i=low; j=high;
    		while (i<j) { 
    			// i的位置空出来了。从右往左走，直到能放在i位置上的元素
    			while (i<j && arr[j]>tmp) j—-; //arr[j]比tmp大，继续往左走
    			if (i<j) {  //找到比tmp的小的元素arr[j]
    				arr[i]=arr[j]; //放到i的位置，则j的位置空出来了
    				i++;
    			}
    			// j的位置空出来了。从左到右走，直到能放在j位置上的元素
    			while (i<j && arr[i]<tmp) i++; //arr[i]比tmp小，继续往右走
    			if (i<j) {  //找到比tmp大的元素arr[i]
    				arr[j]=arr[i]; //放到j的位置，则i的位置又空出来了
    				—-j;
    			}
    		}
    		arr[i]=tmp; //tmp的位置找到，此时小于tmp的元素在左边，大于tmp的在右边
    		QuickSort(arr, low, i-1);
    		QuickSort(arr, i+1, high);
    	}
    }

#### 选择排序 ####

// 简单选择排序
    void SelectSort(int arr[], int n) { 
    	int i,j,tmp;
    	int min_index;
    	for (i=0; i<n; ++i) {  //i为无序序列的左边界，每趟排序无序序列缩小一个
    		// 在无序序列[i, n-1]中选择最小值
    		min_index = i; //最小值下标
    		for (j=i+1; j<n; ++j) {  
    			if (arr[min_index]>arr[j])
    				min_index = j;
    		}
    		// 把最小值交换到无序序列的最左边arr[i]
    		tmp=arr[i];
    		arr[i]=arr[min_index];
    		arr[min_index]=tmp;
    	}
    }
    // 堆排序：从小到大排序，要从数组头取最大值放到最后，所以要用大顶堆
    void HeapSort(int arr[], int n) {  //元素在arr[0]-arr[n-1]
    	int i,tmp;
    	// 建堆：从最后一个非叶子结点开始调整
    	for (i=n/2-1; i>=0; i—-) //最后一个非叶子结点是n的父亲
    		Sift(arr, i, n-1); //调整[i, n-1]
    	// 堆排序
    	for (i=n-1; i>=1; i—) {  //从大顶堆中取n-1次最值：i表示无序序列的后边界
    		// 堆顶和堆尾交换，将arr[i]并入有序序列
    		tmp = arr[0];	//从大顶堆中取出堆顶（最大值）
    		arr[0] = arr[i];//将堆中最后一个元素放在堆顶
    		arr[i] = tmp;	//将最大值放入大顶堆的最右边
    		Sift(arr, 0, i-1); //调整[0, i-1]
    	}
    }
    void Sift(int arr[], int low, int high) {  //arr[low]不满足堆定义，则在[low, high]范围内调整(即下沉)
    	int i,j,tmp;
    	i=low; 		//此次要调整的元素
    	tmp=arr[i];	//备份要调整的元素，i的位置空出来了
    	for (j=2*i+1; j<=high; j=2*i+1) {  //j指向i的左孩子
    		// 因为是大顶堆，则左右孩子中要取最大的那个
    		if (j<high && arr[j]<arr[j+1]) {  //如果i有右孩子 && 右孩子大
    			j=j+1; //则j指向i的右孩子
    		}
    		if (tmp<arr[j]) {  //元素<它的孩子。但大顶堆的规则是元素>孩子，则需要进行调整
    			arr[i]=arr[j]; 	//孩子上浮到arr[i]
    			i=j;			//元素的位置换到j
    		} else {  //元素>它的孩子。符合大顶堆，即调整结束
    			break; //退出调整
    		}
    	}
    	arr[i]=tmp; //把tmp放在调整结束的位置i
    }

#### 归并排序 ####

// 归并排序：对A[]中的[low, high]进行归并排序
    void MergeSort(int A[], int low, int high) { 
    	if (low<high) { 
    		int mid = (low+high)/2;
    		MergeSort(A, low, mid);		//归并前半段
    		MergeSort(A, mid+1, high);	//归并后半段
    		Merge(A, low, mid, high);	//将[low, mid],[mid+1, high]合并
    	}
    }
    // 将[low, mid]、[mid+1, high]两端有序序列归并成一段有序序列
    void Merge(int A[], int low, int mid, int high) { 
    	int *tmp, i,j,k;
    	
    	tmp = (int *)malloc( sizeof(int)*(high-low+1) ); //暂存排序结果
    	k=0; //合并结果的指针
    	for (i=low, j=mid+1; i<=mid && j<=high; ) {  
    		tmp[k++] = A[i]<=A[j] ? A[i++] : A[j++]; //小的先存
    	}
    	// 处理剩余部分
    	while (i<=mid) tmp[k++] = A[i++];
    	while (j<=high) tmp[k++] = A[j++];
    	// 将结果拷贝到A[]
    	k=0; //合并结果指针
    	for (i=low; i<=high; i++) A[i]=tmp[k++];
    	free(tmp); //释放暂时空间
    }

#### 外部排序 ####

<table> 
 <thead> 
  <tr> 
   <th>外部排序归并操作法</th> 
   <th>涉及的内容</th> 
   <th>说明</th> 
   <th>文件内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td></td> 
   <td>文件中存有n个数，但内存大小只能存放m个数</td> 
   <td><code>15 19 04 83 12 27 11 25 16 34 26 07 10 90 06</code></td> 
  </tr> 
  <tr> 
   <td>第一阶段</td> 
   <td>置换-选择排序</td> 
   <td>将文件中的数据处理成多个<strong>有序子序列</strong></td> 
   <td>【第一种结果】每个子序列长度相同：<code>4 12 15 19 83 | 11 16 25 27 34 | 6 7 10 26 90</code><br>【第二种结果】每个子序列长度不同：<code>4 12 15 19 25 27 34 83 | 7 10 11 16 26 90 | 6</code></td> 
  </tr> 
  <tr> 
   <td>可选步骤</td> 
   <td>最佳归并树（生成哈夫曼树的方法）</td> 
   <td>计算最优的归并方案</td> 
   <td>文件中生成了3个有序子序列，但长度都不相同。在进行二路归并时，策略就有很多：①12先归并,再和3 ②13先归并,再和2 ③23先归并, 再和1<br>归并方案很多，如何取最优的归并方案呢？</td> 
  </tr> 
  <tr> 
   <td>第二阶段</td> 
   <td>败者树（选择每个归并段的最小值）</td> 
   <td>对文件中的<strong>多个有序子序列</strong>进行归并操作</td> 
   <td><code>4 6 7 10 11 12 15 16 19 25 26 27 34 83 90</code></td> 
  </tr> 
 </tbody> 
</table>

【空间复杂度】O(1)  
【时间复杂度】

<table> 
 <thead> 
  <tr> 
   <th>步骤</th> 
   <th>说明</th> 
   <th>时间复杂度</th> 
   <th>I/O操作</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>【第一阶段】初始归并段的生成</td> 
   <td>置换选择排序</td> 
   <td>选择最值那一步的时间复杂度要根据考试要求选择算法而定</td> 
   <td>所有记录都要进行两次I/O操作</td> 
  </tr> 
  <tr> 
   <td>【可选阶段】最佳归并树</td> 
   <td>生成哈夫曼树</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>【第二阶段】选择最值</td> 
   <td>用败者树选择最值</td> 
   <td>1. 【败者树建树】O(klog2k)<br>2. k路归并的败者树高度⌈log2k⌉+1，从k个记录中选择最值需要进行⌈log2k⌉此比较，即时间复杂度是O(log2k)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>【第二阶段】归并</td> 
   <td>归并</td> 
   <td>m个初始归并段进行k路归并，归并的趟数⌈log<sub>k</sub>m⌉</td> 
   <td>每次归并，所有记录都要进行两次I/O操作</td> 
  </tr> 
 </tbody> 
</table>

# 查找 #

> 链接：[查找汇总][Link 4]

[KMP]: https://geodoer.blog.csdn.net/article/details/101053898
[Link 1]: https://geodoer.blog.csdn.net/article/details/84499664
[Link 2]: https://geodoer.blog.csdn.net/article/details/103428953
[Link 3]: https://geodoer.blog.csdn.net/article/details/84563930
[2019102214114695.png]: https://img-blog.csdnimg.cn/2019102214114695.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191022141003772.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191022132012870.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191021112313599.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70
[Link 4]: https://geodoer.blog.csdn.net/article/details/102899697