第一章
一、名词解释
1、 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合
2、 数据：是描述客观事物的符号，是计算机中可以操作的对象是能被计算机识别；并输入计算机处理的符号集合
3、 数据元素：是组成数据的有一定意义的基本单位，在计算机中通常作为整体处理；也被称为记录
4、 数据项：一个数据元素可以由若干个数据项组成
5、 数据项是数据不可分割的最小单位
6、 数据对象：是性质相同的数据元素的集合，是数据的子集
7、 逻辑结构：是指数据对象中元素之间的相互关系
7.1、 集合结构：集合结构中的数据元素除了同属于一个集合处，它们之间没有其他关系
7.2、 线性结构：数据元素之间是一对一的关系
7.3、 树形结构：数据元素存在一种一对多的层次关系
7.4、 图形结构：数据元素是多对多的关系
8、 物理结构：是指数据的逻辑结构在计算机中存储形式
8.1、 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
8.2、 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的
9、 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称
9.1、 原子类型：是不可以再分解的基本类型包括整型、实型、字符型等
9.2、 结构类型：由若干个类型组合而成，是可以再分解的，例如：整型数组是由若干整型数据组成的
10、 抽象数据类型（Abstract Data Type；ADT）是指一个数学模型及定义在该模型上的一组操作
第二章 算法
1、 算法：是解决特定问题解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
注：算法至少有一个或多个输出
2、 算法的特性
2.1 有穷性： 指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
2.2 确定性：算法的每一步骤都具有确定的含义，不会出现二义性
2.3 可行性：算法的每一步都必须是可行的，也就是说每一步都能够通过执行有限次数完成
3、 算法设计的要求
3.1 正确性：算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求能够得到问题的正确答案
3.2 可读性：算法设计的另一目的是为了便于阅读理解和交流
3.3 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
3.4 时间效率高和存储量低
4、 算法效率的度量方法
4.1 事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低
4.2 事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算
注： 一个程序的运行时间，依赖于算法的好坏和问题的输入规模
5、 函数的渐进增长：给定两个函数f（n）和g（n），如果存在一个整数N，使得对于所有的n>N,f(n)总是比g（n）大，那么我们说f（n）的增长渐进快于g（n）
注： 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数
6、 算法时间复杂度定义：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级，算法的时间复杂度，也就是算法的时间度量，记作T（n）=O（f（n）），它表示随问题规模n的增长，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度。简称为时间复杂度，其中f（n）是问题规模n的某个函数。
7、 推导大O阶
7.1 用常数 1 取代运行时间中的所有加法常数。
7.2 在修改后的运行次数函数中，只保留最高阶项
7.3 如果最高阶存在且不是 1，则去除与这个项相乘的常数，得到的结果就是大O阶
8、 线性阶
9、 对数阶：O（log n）
10、 平方阶： O（n*n）
11、 常见的时间复杂度
| 执行次数的函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O（1） | 常数阶 |
| 2*n+3 | O（n） | 线性阶 |
| 3n^2+2n+1 | O（n^2） | 平方阶 |
| 5*log_2 n+20 | O（log_n） | 对数阶 |
| 2n+3n*log_2 n+19 | O（n*log_n） | n*log_n阶 |
| 6n^3+2n^2+3n+4 | O（n^3） | 立方阶 |
| 2^n | O（2^n） | 指数阶 |
12、最坏情况运行时间是一种保证，那就是运行时间将不会再坏了，在应用中，这里一种最重要的需求，通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间
13、算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S（n）=O（f（n）），其中，n为问题的规模，f（n）为语句关于n所占存储空间的函数
第三章 线性表
1、 线性表：零个或多个数据元素的有限序列
2、 若将线性表记为（a_1,…,a_i-1,a_i,a_i+1,…,a_n）,则表中a_i-1领先于a_i,a_i领先于a_i+1,称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。当i=1,2,…,n-1时，a_i有仅有一个后继元素，当i=2，3，…,n时，a_i有仅有一个直接前驱。
注：1） 线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。
2） 在较复杂的线性表中，一个数据元素可以由若干个数据项组成
3、 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素
属性：
1） 存储空间的启始位置
2） 线性表的最大存储位置
3） 线性表的当前长度
4、 线性表顺序存储结构优缺点
优点
1） 无须为表中元素之间的逻辑关系而增加额外的存储空间
2） 可以快速地存取表中任一位置的元素
缺点
1） 插入和删除操作需要移动大量元素
2） 当线性表长度变化较大时，难以确定存储空间的容量
3） 造成存储空间的“碎片”
5、 线性表的链式存储结构的特点是用任一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
6、 为了表示每个数据元素a_i与其直接后继数据元素a_i+1之间的逻辑关系，对数据元素a_i来说，除来存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链，这两部分信息组成数据元素a_i的存储映像，称为节点（Node）。
n个结点（a_i的存储映像）链结成一个链表，即为线性表（a_i,a_2,…a_n）的链式存储结构，因此链表的每个结点中包含一个指针域，所以叫做单链表
7、 单链表结构与顺序存储结构优缺点
1） 存储分配方式
* 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
* 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
2）时间性能
* 查找
1） 顺序存储结构O（1）
2） 单链表O（n）
* 插入和删除
1） 顺序存储结构需要平均移动表长一半的元素，时间为O（n）
2） 单链表在线出某位置的指针后，插入和删除时间仅为O（1）
* 空间性能
1） 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
2） 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
8、 静态链表：用数组描述的链表叫做静态链表
9、 静态链表的优缺点：
* 优点
1） 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点
* 缺点
1） 没有解决连续存储分配带来的表长难以确定的问题
2） 失去了顺序存储结构随机存取的特性
10、 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
11、 双向链表（double linked list）是在单链表的每个结点，再设置一个指向其前驱结点的指针域
第四章 线性表
1、 栈（stack）是限定仅在表尾进行插入和删除操作的线性表
注：允许插入和删除的一端称为栈顶（top）另一端称为栈底（bootom），不含任何数据元素的栈称为空栈，栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构
2、 栈的顺序存储结构
3、 两栈共享空间
4、 栈的链式存储结构，简称为链栈
注： 如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些
5、 栈的应用–递归
6、 斐波那契数列实现
7、 递归定义： 把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数
8、 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出
9、 迭代和递归的区别是： 迭代使用的是循环结构；递归使用的是选择结构
10、 栈的应用–四则运算表达式求值
10.1 后缀（逆波兰）表示法定义
11、 中缀表达式转后缀表达式
12、 队列：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
注： 队列是一种先进先出（Fist In First Out）的线性表，简称FIFO，允许插入的一端为对尾，允许删除的一端称为对头
13、 队列顺序存储
14、 循环队列定义： 头尾相接的顺序存储结构称为循环队列
15、 队列的链式存储结构： 其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列
注：可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时则用链队列
第五章 串
1、 串（String）是由零个或多个字符组成的有限序列，又名叫字符串
2、 串的顺序存储结构
3、串的链式存储结构
注：串的链式存储结构除了在连接串与串操作有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好
4、 朴素的模式匹配算法
5、 KMP模式匹配算法
7、 KMP模式匹配算法改进
练习
《璇玑图》破解诗篇的算法
第六章 树
1、 树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树，在任意一棵非空树中
1） 有且仅有一个特定的称为根（root）的结点；
2） 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T_1,T_2,...、T_m,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）如图6-2-1 所示。
2、 结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点的度的最大值
3、 结点的子树的根称为该结点的孩子（child）相应地，该结点称为孩子的双亲
4、 同一个双亲的孩子之间互称兄弟（sibling）结点的祖先是从根到该结点所经分支上的所有结点，以某结点为根的子树中的任一结点都称为该结点的子孙
5、 结点的层次（level）从根开始定义起，根为第一层；根的孩子为第二层
6、 双亲在同一层的结点互为堂兄弟
7、 树中结点的最大层次称为树的深度（Depth）或高度
8、如果将树中结点的各个子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树
9、 森林（Forest）是m（m>=0）棵互不相交的树的集合
10、 双亲表示法：在每个结点中，附设一个指示器指示其双亲结点在树组中的位置
11、 存储结构的设计是一个非常灵活的过程，一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适，是否方便，时间复杂度好不好等
12、 每个结点有多个指针域；其中每个指针指向一颗子树的根结点，我们把这种方法叫做多重链表表示法
13、孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有 n 个孩子链表，如果是叶子结点则次单链表为空，然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维中
14、 孩子兄弟表示法： 任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的左兄弟如果存在也是唯一的，因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟
15、 二叉树（Binary Tree）是 n （n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成
16、 二叉树五种形态
16.1 空二叉树
16.2 只有一个根结点
16.3 根结点只有左子树
16.4 根结点只有右子树
16.5 根结点既有左子树又有右子树
17、 斜树：所有的结点都只有左子树的二叉树叫左斜树，所有结点都是只有右子树的二叉树叫右斜树
18、 满二叉树： 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
19、 完全二叉树： 对一棵具有 n 个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树
20、 二叉树的性质
20.1 在二叉树的第 i 层中至多有2^i-1个结点（i>=1）
20.2 深度为k 的二叉树至多有（2^k）-1个结点（k>=1）
20.3 对任何一棵二叉树T，如果其终端结点数为 n_0,度为2的结点数为n_2;则 n_0=n_2+1
20.4 具有 n 个结点的完全二叉树的深度为【log_2 n】+1(|x|表示不大于x的最大整数)
20.5 如果对一棵有 n 个结点的完全二叉树（其深度为【log_2 n】+1）的结点按层序编号（从第1层到【log_2 n】+1层，每个层从左到右），对任一结点 i (i<=i<=n)有：
20.5.1 如果i=1，则其双亲是结点【i／2】
20.5.2 如果2*i>n;则结点 i 无左孩子（结点 i 为叶子结点）；否则左孩子是结点2*i
20.5.3 如果2*i+1>n,则结点 i 无右孩子，否则右孩子结点2*i+1
21、 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等
22、 二叉链表： 二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，这样称的链表叫做二叉树
23、 二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点使得每个结点被访问一次且仅被访问一次
24、 前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
25、 中序遍历： 规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点最后中序遍历右子树
26、 后序遍历： 树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
27、 层序遍历：若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点，逐个访问
28、 指向前驱荷后继的指针称为线索；加上线索的二叉树称为线索链表，相应地二叉树就称为线索二叉树（Threaded Binary Tree）
注： 如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱荷后继，那么采用线索二叉链表的存储结构就是非常不错的选择
29、 赫夫曼树及其应用 –最基本压缩编码方法
30、 设需要编码的字符集为{d_1,d_2,…,d_n} 各个字符在电文中出现的次数或频率集合为{w_1,w_2,…,w_n} 以d_1,d_2,…,d_n作为叶子结点，以w_1,w_2,…,w_n 作为相应叶子结点的权值来构造一棵赫夫曼树，规定赫夫曼树的左分支代表O，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的O和1的序列便为该结点对应字符的编码；这就是赫夫曼编码
第七章 图
1、 图（Graph）是由顶点的有穷非空集合和顶点之间的集合组成，通常表示为G（V，E），其中，G表示一个图，V是图，G中顶点的集合，E是图G中边的集合
2、 有向边：若从顶点V_i 到V_j的边有方向，则称这条边为有向边，也称为弧（Arc）
3、 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单的图
4、 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图
5、 有很少边或弧的图称为稀疏图，反之称为稠密图
6、 路径的长度是路径上的边或弧的数目。第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点最后一个顶点之外，其余顶点不重复出现回路称为简单回路
7、 在无向图G中，如果从顶点V到V1有路径，则称V和V1是连通的。如果对于图中任意两个顶点V_i,Vj属于V，Vi和Vj是连通的，则称G是连通图（Connected Graph）
8、 无向图中的极大连通子图称为连通分量
9、 在有向量图G中，如果对于每一对Vi，Vj属于V，Vi不等于Vj从Vi到Vj 和从Vj到Vi都存在路径，则称G是强连通图，有向图中的极大强连通子图称做有向图的强连通分量
10、 图的邻接矩阵（Adjacency Matrix）存储方式，是用两个数组来表示图，一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息
11、 邻接表：数组与链表相结合的存储方法称为邻接表
12、 十子链表：能把邻接表与逆邻接表结合起来
13、 ivex和jvex 是与某条边依附的两个顶点在顶点表中的下标，ilink 指向依附顶点ivex的下一条边，jlink 指向依附顶点jvex的下一条边。这就是邻接多重表结构
14、 边集数组：是由两个一维数组构成。一个是存储顶点的信息，另一个是存储边的信息。这个边数组每个数据元素由一条边的起点下标（begin），终点下标（end）和权（weight）组成
15、 深度优先遍历：也就称为深度优先搜索，简称为DFS
16、 广度优先遍历：又称为广度优先搜索，简称BFS
17、 我们把构造连通网的最少代价生成树称为最小生成树
18、 普里姆算法
19、 克鲁斯卡贝算法
20、 最短路径 对于网图来说：最短路径：是指两顶点之间经过的边上权值之和最少的路径，并且我们称路经上的第一个顶点是源点，最后一个顶点是终点
21、 迪杰斯特拉算法
22、弗洛伊德算法： 如果你面临需要所有顶点至所有顶点的最短路径问题时，弗洛伊德算法应该是不错的选择
23、 拓扑排序：在一个表示工程的有向图中，用顶点表示活动用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Activing On Vertex Network）
拓扑排序：其实就是对一个有向图构造拓扑序排的过程
24、 关键路径：路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动
第八章 查找
1、 查找表（Search Table） 是由同一类型的数据元素（或记录）构成的集合
2、 关键字（Key）是数据元素中某个数据项的值
3、 查找（Searching）就是根据给定某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）
4、 静态查找表（Static Search Table）：只作查找操作的查找表
5、 动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从表中删除已经存在的某个数据元素
6、 顺序查找（Sequential Search）：又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功
7、 折半查找（Binary Search） 时间复杂度（O_log n）
8、 插值查找（Interpolation Search）是根据要查找的关键字key 与 查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式
key-a【low】
-------------------
a【high】-a【low】
9、 斐波那契查找
10、 折半查找是进行加法与除法运算 mid=（low + high）／2），插值查找进行复杂的四则运算
（mid=low + （high-low））*（key-a【low】）／（a【high】-a【low】），
而斐波那契查找只是最简单加减法运算（mid=low+F【k-1】-1），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率
11、 索引就是把一个关键字与它对应的记录相关联的过程
12、 索引按照结构可以分为线性索引、树型索引和多级索引
13、 线性索引就是将索引项集合组织为线性结构也称为索引表
14、 稠密索引：将数据集中的每个记录对应一个索引项
注：对于稠密索引这个索引来说，索引项一定是按照关键码有序的排列
15、 分块索引： 是把数据集的记录分成了若干块，并且这些块需要满足两个条件
15.1 块内无序 即每一块内的记录不要求有序
15.2 块间有序
15.3 最大关键码： 它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大
15.4 存储了块中的记录个数，以便于循环时使用
15.5 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历
16、 倒排索引
17、 其中记录号表存储具有相同次关键字的所有记录号（可以是指向记录的指针或者是该记录的主关键字），这样的索引方法就是倒排索引（inverted index）
18、 二叉排列树（Binary Sort Tree）又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树
18.1 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值
18.2 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
18.3 它的左右子树也分别为二叉排列树
19、 二叉排序树插入操作
20、 平衡二叉树（Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree）是一种二叉树，其中一个节点的左子树和右子树的高度差至多等于1
21、 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）
注：距离插入结点最近的，且平衡因子的绝对值大于1 的结点为根的子树，称为最小不平衡子树
22、 多路查找树（muitl - way Search tree） 其每一个结点的孩子树可以多于两个，且每一个结点处可以存储对过元素
23、 2-3树：是这样一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为 3 结点）
23.1 一个2 结点包含一个元素和两个孩子，一个3 结点包含一小一大两个元素和三个孩子
24、 2-3-4树：就是2-3树的概念扩展，包括了4结点的使用，一个4结点包含小、中大三个元素和四个孩子（或没有孩子）
25、 B树（B-tree）是一种平衡的多路查找树
26、 B+树的结构特别适合带有范围的查找，比如查找我们学校18～22岁的学生人数
27、 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）
注：这种对应关系f称为散列函数，又称为哈希（Hash）函数，按这个思想采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）
28、 散列技术既是一种存储方法，也是一种查找方法
29、 散列技术最适合的求解问题是查找与给定值相等的记录
30、 散列函数因素参与：
30.1 计算散列地址所需的时间
30.2 关键字的长度
30.3 散列表的大小
30.4 关键字的分布情况
30.5 记录查找的频率，综合这些因素
31、 开放定址法： 一旦发生了冲突；就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
f（key）=（f（key）+d_i）MODm(d_i=1,2,3,..,m-1)
解决冲突的开放地址法称为线性探测法增加平方运算的目的是为了不让关键字都聚集在某一块区域我们称这种方法为二次探测法
f_i(key)=(f(key)+d_i)MOD m (d_i=1^2,-1^2,2^2,-2^2,...,q^2,-q^2) q<=m/2
在冲突时，对于移量d_i采用随机函数i+算得到，我们称之为随机探测法
第九章 排序
1、 排序：假设含有n个记录的序列为{r_1,r_2,…,r_n},其相应的关键字分别为{k_1,k_2,…,k_n},需确定1，2，。。。n的一种排列p_1,p_2,…,p_n,使其相应的关键字满足k_p1<=k_p2<=···<=k_pn非递减（或非递增）关系，即使序列成为一个按关键字有序的序列{r_p1,r_p2,…,r_pn},这样的操作就称为排序。
2、 排序的稳定性：假设k_i=k_j(1<=i<=n,1<=j<=n,j!=j)且在排序前的序列中r_i;则称所用的排序方法是稳定；反之，若可能使得排序后的序列r_i领先r_2,则称所用的排序方法是不稳定的。
3、 内排序与外排序：内排序是在整个排序过程中，待排序的所有记录全部被放置在内存中。
外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行
3.1 时间性能
3.2 辅助空间
3.3 算法的复杂性
4、 插入排序；交换排序；选择排序和归并排序
5、 七种排序算法
5.1 简单算法：冒泡排序；简单选择排序；直接插入排序
5.2 改进算法：希尔排序；堆排序；归并排序；快速排序
6、 冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止
6.1 冒泡排序优化，时间复杂度O（n^2）
7、 简单选择排序算法（Simple selection Sort）就是通过n-i 次关键字间比较，从n-i+1记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之 时间复杂度O（n^2）
8、 直接插入排序算法（Straight Insertion Sort）基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表 时间复杂度O（n^2）
9、 希尔排序
10、 希尔排序原理：所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
11、 堆：堆是具有下列性质的完全二叉树；每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值；称为小顶堆
12、 堆排序（Heap Sort）：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列
13、 归并算法（Merging Sort）：假设初始序列含有 n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到【n/2】（【x】表示不小于x的最小整数）个长度为2或1的有序子序列，再两两归并，…如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2路归并排序。
时间复杂度O（n+log n）
14、 快速排序算法：通过一趟排序将待记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的