[TOC]
# 排序
## 插入排序
### 直接插入排序
算法：
~~~
void InsertSort(SeqList R, int n) {
int i, j;
for (i=2; i<n; i++) {
R[0] = R[i];
for (j=i-1; R[0].key < R[j].key; j--) {
R[j+1] = R[j];
}
R[j+1] = R[0];
}
}
~~~
`R[0]`的两个作用：
+ 进入查询循环前保存`R[i]`的副本；
+ 监视数组下标是否越界。
实例
### 希尔排序
## 交换排序
### 冒泡排序
实例：
### 快速排序
## 选择排序
### 直接选择排序
### 堆排序
例子：
## 归并排序
## 分配排序
### 箱排序
### 基数排序
## 总结
# 查找
## 顺序表的查找
常用的有顺序查找、二分查找。
## 树表的查找
### 二叉排序树
实例:
## 散列表的查找
散列函数的构造方法：
+ 直接地址法：H(key) = key + c
+ 数字分析法：
+ 除余法：H(key) = k % p
+ 平方取中法
+ 折叠法
处理冲突的方法：
+ 开放地址法
+ 线性探测法：地址序列 = d + i (d = H(key)；i=1、2、3 .....）
+ 二次探测发：地址序列 = d ± i<sup>2</sup>(d = H(key)；i=1、2、3 .....，即d+1<sup>2</sup>、d-1<sup>2</sup>、d+2<sup>2</sup>、d-2<sup>2</sup>....）
+ 双重散列法：地址序列 = d ± i*d1(d = H(key)；i=1、2、3 .....，即d，d+1*d1、d+2*d2....）
+ 拉链法（链地址法）
### 线性探测法
这里的探测因子取值为：13
分别得到下标：
h(26) = 26 % 13 = 0
h(12) = 12 % 13 = 12
....
### 二次探测发
# 树
## 哈弗曼树
# 图
## 图的遍历
### 深度优先搜索遍历（DFS）
类似于树的**前序遍历**
### 广度优先搜索遍历
## 图的最小生成树
生成树：连通图的包含图中所有顶点的一个极小连通子图（变最少）。一个极小连通子图是无回路的连通图。
### 普利姆（Prim）算法
> g、h都是最小生成树，他们分别是在第e步两种不同的选择结果。
### 克鲁斯卡尔（Kruskal）算法
> 根据权值选择变。
## 最短路径
## 拓扑排序
