注意点：

通常情况下，当数据量足够大时，一般满足

θ(1)>θ(N)>θ(NlogN)>θ(N^2) (>代表优于)

时间复杂度：O(N^2) 思想：每次从右至左跟已排序数列进行对比，放入合适位置。两次遍历，一次相当于摸牌，另一次相当于具体的查找算法。

将问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解来建立原问题的解。（分解-解决-合并）

归并排序 时间复杂度O(NlogN)（O还是θ——theta，都差不多）

归并排序算法如下：

O渐进上界Ω渐进下界，o和ω 具体看数学定义最清楚。

求解递归式的三种方法：

主方法

思路简单，分成两个子序列，最大和要么全在左侧序列，要么全在右侧序列，要么跨中点；简单写法的参考简单版本，但是有个点需要注意一下，代码给出的复杂度是O(N)

如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外，则程排序算法是原址的（in place)。例如，排序算法中的swap操作。 顺序统计量：一个n个数的集合的第i个顺序统计量就是集合中第i小的数。

堆排序的时间复杂度是O(NlgN)，具有空间原址性。

二叉堆是一个数组，它可以被看成是一个近似的完全二叉树（按层序排列，各个节点的序号同满二叉树相同） 二叉堆可以分为两种形式：最大堆和最小堆（最大还是最小取决于对应的二叉树的所有双亲节点是否都大于或小于其孩子节点的值）。堆排序算法中，使用的是最大堆。最小对通常用于构造优先队列。

维护堆的性质 通俗的讲，就是保持数组的最大堆性质。思路比较简单，比较parent节点和孩子节点，找到最大值，如果最大值是某个孩子节点，交换，递归运行。对于树高为h的节点来说，该程序时间复杂度为O(h)

建堆 建堆过程，说白了就是对每一个非叶节点进行（1）的操作。复杂度O(n)

堆排序算法 交换A[1]和A[n]，此时最大的数已经位于最后一个位置。然后调整剩下的n-1个数据，调用（1）的方法；再交换A[1]和A[n-1]，如此下去。复杂度O(lgn)

具体堆排序过程可参考图解堆排序（不过也注意，其中有一些问题，哪些节点有子节点，从1开始标，应该是(n/2)向下取整）

优先队列（priority queue）是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字（key） 最大优先队列应用：例如在共享计算机系统的作业调度。 最小优先队列应用：用于基于事件驱动的模拟器。

最坏情况复杂度θ（n^2），元素互异的情况下期望时间复杂度θ(NlgN)，通常是实际排序应用中最好的选择。

由于是in place排序，所以不需要合并操作。 伪代码：

数组的划分

数组划分一点分析：默认以A[r]——最后一个元素作为比较中间点，for循环遍历A数组，j指向每个被遍历元素下标；i指向小于A[r]的下标。

画个图理解一下最清楚了：

算导叫法，A[r]称为主元（pivot element）

最坏情况：划分产生子问题元素个数为n-1和0时。此时，T(n)=θ(n2）。当输入数组完全有序时，快排复杂度为θ(n2），插排只有O(n) 最好情况：划分得到的两个子问题的规模都不大于n/2.复杂度θ(nlgn）

这个思路简单，随机选取主元，与A[r]交换，再利用上面的算法计算即可。此种版本主要解决，近乎有序的情况带来的原有快排最坏情况的发生。

在排序的最终结果中，各元素的次序依赖于它们之间的比较，这类排序算法称为比较排序。 三种线性时间复杂度的排序算法：计数排序、基数排序和桶排序。 比较算法采取决策树模型：这里的内部节点用i:j的形式代表A[i]和A[j]进行比较。≤则进左子树比较，反之右子树进行比较。叶子节点给出了最后的顺序。

支持插入删除操作的动态集合称为字典。

栈（stack），后进先出，LIFO 插入称为压入（push），删除称为弹出（pop）。可以简单的理解为有底无盖的杯子。 队列（queue）插入称为入队（enqueue），删除称为出队（dequeue） 链表： 单链表、双向链表、循环链表，建议看下《大话数据结构》了解一下就可以了。 算导以双向链表为例讲解增删查，虽然还是可以通过画图，注意维护涉及节点的prev和next指针指向以及边界条件，能够明白其操作过程，但还是记录下，以备复习之用。

哨兵（sentinel） 哨兵是一个哑对象，其作用是简化边界条件的处理。 类似于以前学习时讲到的头节点。加入哨兵将原来的双向链表转变成一个有哨兵的双向循环两表。L.nil代表哨兵。一图胜千言，如下：

如果有很多个很短的链表，慎用哨兵，因为哨兵所占用的额外存储空间会造成严重的存储浪费。哨兵并没有优化太多的渐进时间界，只是可以使代码更紧凑简洁。

对象的多数组表示： next和prev中的数字指的是对应数字的下标，有趣！

单数组表示：

分支无限制的有根树可以用左孩子右兄弟表示法。

散列表是普通数组概念的推广。

直接寻址缺点：如果U全域很大，存储大小为U.size()的一张表T不太实际，而且对于T来讲如果存储的关键字集合K相对于U来说很凶，则T的大部分空间将会浪费掉。 在散列方式（hash）下，关键字k被放到槽（slot）h(k)中，及利用散列函数（hash function）h，根据k计算出槽的位置。这里，函数h将关键字的全域U映射到散列表T[0...m-1]的槽位上（|U|＞m，正因如此，完全避免冲突是不可能的） 如果h(k1) = h(k2)，则称冲突（collision）

启发式方法：乘法散列和除法散列 随机技术：全域散列 多数散列函数都假定关键字的全域为自然数集，因此，如果所给的关键字不是自然数，就需要找到一种方法将他们转为自然数。

一个不太接近2的整数幂的素数，常常是m的一个较好的选择。

为了使用开放寻址法插入一个元素，需要连续的检查散列表，或称为探查（probe），直到找到一个空槽来放置待插入的关键字为止。 三种技术计算开放寻址法中的探查序列：线性探查、二次探查和双重探查。 这个hash函数应该就是hash（k）= k mod m(m代表散列表的长度） 线性探查，通俗的讲，过程是这样的：利用一个hash函数，计算关键字key位于的槽位下标hash（key)，如果T[hash(key)]已经有值，则探查T[hash(key)+1],T[hash(key) +2]直到最后。类似一人找厕所的过程，到一个厕所（hash(key)位置）跟前，看能不能打开门，打不开就挨着找下一个，直到找到对应的位置。（由于就只有m个元素需要hash，则每个都是能找到对应位置的。） 但是，线性探查存在一个问题，称为一次群集（primary clustering）。例如100个槽位，假设后面95位已经被连续占用，下一次hash出来，如果不幸刚好计算出位置在第6位，则需要连续95次才能找到对应的存储槽位，剩下的4次同样也很耗费时间。 二次探查（quadratic probing） 相比于线性探查，在于偏移量采用的是ax^2+bx这种形式 双重散列（double hashing） 是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择排列的许多特性。 完全散列 采用两级散列。当关键字集合是静态（即关键字存到表中关键字集合就不再变化了）的，采用完全散列，一级散列于带链接的散列表基本一致，二级散列的长度是存储的关键字个数的平方（主要是为了确保第二级上不出现冲突）。

关于树：

注意：《算导》的完全二叉树和满二叉树跟《大话数据结构》里的二者定义完全不同，具体以哪个为准，暂不纠结，哪位朋友知道的，可以告知一下

二叉搜索树的性质：x是一个节点，则其左（右）子树任意节点.key 分别≤（≥）x.key

中序遍历（inorder tree walk）子树根的关键字位于左右子树的关键字之间。 前序遍历（preorder tree walk）子树根的关键字位于左右子树的关键字之前。 后序遍历（postorder tree walk）子树根的关键字位于左右子树的关键字之后。

这里区分一下二叉搜索树和最大堆，相同点：比较都是针对所有节点而言，不同点：二叉搜索树，节点左子树值均小于该节点的值，右子树值均小于该节点的值；最大堆：节点值大于所有孩子的值。

O(h)，h是这棵树的高度，下面五种操作都是这个复杂度 两种写法：递归和while

最大值和最小值：分别一直查左子树（右子树）即可

后继（successor）和前驱（predecessor）： 后继：两种情况，如果x的右子树不为空，则右子树中的最小值就是x的后继； 反之，一直找x的双亲节点，直到x是y的左子树为止。

插入和删除会引起由二叉搜索树表示的动态集合的变化，一定要修改数据结构来反映这个变化，但修改要保持二叉搜索树性质的成立。 插入： 边界条件，二叉搜索树没有元素；否则找到新插入节点z插入的位置的双亲节点。

删除： 三种基本策略：

如果z有两个孩子，那么找z的后继y(一定在z的右子树中），并让y占据树中z的位置。z的原来右子树部分成为y的新的右子树，并且z的左子树成为y的新的左子树，这种情况稍显麻烦，因为还与y是否为z的右孩子相关。

略 BST(binary search tree)的基本操作大都能在O(h)时间内完成。

红黑树是许多平衡搜索树中的一点，可以保证最坏情况下基本动态集合操作的时间复杂度为O(nlgn)。 红黑树是一颗二叉搜索树，增加了颜色，RED or BLACK，确保了没有一条路径会比其他路径长出2倍，因而是近似于平衡的。 相比BST的属性p,left,right,key多了一个属性color。 红黑树的一些特性：

进行增删的时候可能会破坏上面提到的5条性质，因此为了维护这些性质，必须改变某些节点的颜色及指针结构。 指针结构的修改是通过旋转（rotation）来完成的。 这里的左旋和右旋似乎跟《大话数据结构》里AVL树的左旋右旋有相似之处。

一图胜千言：

插入耗费时间O(lgN)，且该程序选择不超过两次 插入一个节点z，并将其着色为红色。

插入后的修补工作：

插入操作只可能破坏红黑树性质2和性质4，并且只能破坏其中一条。 修补的三种情况分析： case 1：z的叔节点y是红色的 此时，不需要旋转，只需要改变颜色,z指向z.p.p即可 z.p.color = y.color = black; z.p.p.color = red;

删除节点耗费O(lgN）时间。 需要提供一个让某节点孩子来接替老子位置的一个方法transplant

节点左右子树高度相差至多为1. 未深入讲解。

为磁盘存储而专门设计的一类平衡搜索树。B树类似于红黑树，但它们在降低磁盘I/O操作数方面要更好一些，许多数据库系统使用B树或者B树变种来存储信息。比如MySQL数据库使用了B+树的数据结构。 B+相比B树来说，主要有几个区别，B+树叶子节点存储了所有数据，可以只经过一次遍历；叶子节点构成了一个单向链表。至于B树的插入删除等，参考2-3树更容易理解一些。 关于B树和B+树的区别等可以参加B树和B+树的区别

B-tree，B+tree，想起以前还以为是一个B+，一个B-呢，哈哈

计算机的主存（primary memory或main memory）通常由硅存储芯片组成。相比辅存比如磁盘磁带价格高，容量小，而辅存容量大价格低然而速度也要慢一些。（这方面的知识哪天还得看下计算机组成原理，虽然《计算机科学导论》也讲过一些，但总觉得还差点东西）

所有叶节点深度相同，即树高h；每个节点所包含的关键字个数有上界和下界，用一个被称为B树的最小度数的固定证书t≥2来表示这些界：每个节点除根节点外必须至少有t-1个关键字，至多可以包含2t-1个关键字。 B+tree将卫星数据存储到叶节点上，内部结点只存放关键字和孩子指针。对存储在磁盘上的一颗大的B树，通常看到分支因子在50~2000之间。

约定：1. B树的根节点始终在主存中，这样无需对根做DISK-READ操作；然而，当根节点被改变后，需要对根节点做一次DISK-WRITE操作。2. 任何被当做参数的节点在被传递之前，都要对他们先做一次DISK-READ操作。

搜索B树

先从x节点内部关键字查找，找不到，并且x有孩子的话或不是叶节点，再从x.ci孩子节点查找。

向B树中插入一个关键字 由于不能向满的叶节点插入节点，故引用分裂操作，将满的叶节点（2t-1）分割为两个（t-1)关键字的节点，中间关键字被提升到y的父节点。从树根往下查找关键字所属位置时，就分裂沿途遇到的每一个满节点。

分裂B树中的节点 分裂是树长高的唯一途径。

以沿树单程下行方式向B树插入关键字

图解插入：

根节点允许有比最少关键字数t-1还少的关键字个数。 当要删除关键字的路径上节点（非根）有最少的关键字个数时，也可能需要向上回溯。 删除实例：

删除比较复杂一点，case1,case2a,2b,2c,case3a,3b. 递归调用自身时，必须保证该节点至少有t个关键字

这里，programming指的是一种表格法，并非编写计算机程序 动态规划方法通常用来求解最优化问题（optimization problem） 似乎跟高中学习的求最优解的问题有相似之处。 按如下4个步骤来设计动态规划算法：

最优子结构（optimal substructure）性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解，主要原因是：反复求解相同的子问题，同斐波那契数列基本递归一样。 动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。此乃时空权衡（time-memory-trade-off）。

自顶向下递归实现：时间复杂度(2^n)

动态规划有两种等价的实现方法：

带备忘的自顶向下法（top-down with memoization） 仍按自然递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）

MEMOIZED-CUT-ROD(p,n)仅仅用来初始化一个存储计算值的数组，主要实现在AUX那个方法里。 借鉴了下别人的思想，尾递归写法如下：

自底向上法（bottom-up method） 在求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。

按照这种思想写了一下斐波那契数列的自底向上实现：