Quick Sort
快排算法思路快排的算法思想是分治：
分：将整个序列分为左右两个子序列，左边的子序列小于等于x，右边的子序列大于x，这个x我们称为主元（pivot），用它来分割序列
治：子序列递归执行
合：左右两个子序列均已排序，中间的主元满足要求，因此得到的就是最终结果
算法正确性因为主元所在的位置与最终已排序序列的位置是一致的，那么依次分割，将序列切短至长度为1，那么自然就得到了最终的排序序列
实现12345QUICKSORT(A,p,r)if p < r then q ← PARTITION(A,p,r) QUICKSORT(A,p,q-1) QUICKSORT(A,q+1,r)
我们用PARTITION来获取主元：
123456789101112PARTITION(A,p,r)x ← A[r]i ← p-1for j ← p to r-1 do if A[j] ≤ x i ← i+1 swapped with A[i] and A[j]end forswapped with A[i+1] and A[r]return i+1
用循环不变式可以证明PARTITION ...
Martix-chain multiplication
矩阵链乘法的最优结合法
我们定义矩阵链为：$A_1A_2A_3···A_n$
我们可以用一对封闭的小括号表示矩阵链的乘积
e.g.:$A_1A_2A_3A_4$的矩阵链结合方式共有5种
(((A_1A_2)A_3)A_4) \\
((A_1A_2)(A_3A_4)) \\
((A_1(A_2A_3))A_4) \\
(A_1((A_2A_3)A_4)) \\
(A_1(A_2(A_3A_4)))矩阵乘法在处理矩阵链之前我们必须了解两个矩阵相乘需要执行多少次运算以及结合方式对其造成的影响
1234567891011MATRIX-MULTIPLICATION(A,B)if A.cols ≠ B.rows then error "incompatible dimension" else let C be a new A.rows×B.cols matrix for i ← 1 to A.rows for j ← 1 to B.cols C[i,j] ← 0 for k ← 1 to A.cols C[i,j] ← C[i,j]+A[i,k]*B ...
Knapsack problem
背包问题
0-1背包
A thief robbing a store finds n items.The ith item is worth $w_i$ dollars and weighs $w_i$ pounds,where $v_i$ and $w_i$ pounds,where $v_i$ and $w_i$ are integers.The thief wants to take as valuable a load as possible,but he can carry at most W pounds in his knapsack,for some integer W.which items should he take?
令dp[i][j]为前i个物品，载重为j的最大价值，那么最大价值取决于第i个物品拿不拿
不拿：dp[i-1][j]
拿：dp[i-1][j-w[i]]+v[i]
然后选择较大者即可
dp[i][j]=max\{dp[i-1][j],dp[i-1][j-w[i]]+v[i]\}但是你发现第一维是可以优化掉的：前i个物品只和前i-1个物品有关
...
DP&greedy
动态规划和贪婪算法总结
PS：鉴于经验比较少，此文所写理论占多，待以后补充
动态规划和贪婪算法是一对孪生兄弟，但是动态规划是哥哥，因为动态规划可以解决的问题贪婪算法不一定能解决，反之，贪婪算法可行的动态规划一样可行，但是相对时间复杂度会更大
问题性质动态规划问题具有两个性质：最优子结构(optimal substructure)和重叠子问题(overlapping subproblems)
而贪婪算法问题具有两个性质：最优子结构和贪婪选择性质(greedy-choice property)
你会发现两者都有最优子结构，最优子结构指的是原问题的最优解包含相关子问题的最优解，即原问题的最优解依赖于子问题的最优解
动态规划能适用的问题一定会有重叠子问题的性质，如果一个问题只有最优子结构(e.g.Quicksort)，那么它没有必要用动态规划，因为动态规划本来就是让这些重叠的子问题只执行一次而让程序得到优化的一种算法技巧
贪心算法也不具有重叠子问题性质，反而具备贪婪选择性质：局部最优解即是全局最优解的一部分，通过贪心选择，我们留下一个子问题，依次根据贪心选择得到局部解，最终组合在一起就是全局最 ...
BFS
Breadth-first search
Why so named粗翻为“宽度优先搜索”，本质是搜索算法
（网上博客什么“广度优先遍历”也是绝了，遍历是traverse，岂不是BFT？）
按所谓的“广度优先遍历”的顺序其实就是接下来要讲到的BLACK顶点的出现顺序
为什么这么取名呢？
Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier
在边界的宽度上均匀扩展在已发现顶点和未发现顶点之间的边界
讲解为了跟踪整个过程，我们约定好顶点有三种颜色表示：BLACK，GRAY，WHITE
WHITE表示还未发现的顶点，所以一开始所有顶点都是白的，之后会染成另外两种颜色
GRAY是中间色，表示已发现，但是它的邻接点还有白色的，实际上灰色代表着上面提到的边界
BLACK表示已发现，并且它的邻接点都已染灰或黑，没有白色的
\begin{alig ...
Red-Black tree
红黑树红黑树保证两颗子树之间高度不会相差两倍以上，因此是（红黑）“近似平衡”（黑节点是完美平衡）的
红黑树满足以下性质（约定称为RB性质）：
Every node either red or black
The root and leaves(NIL ‘s)are black
If a node is red,then its parent is black
All simple paths from any node $x$ to a descendant leaf have the same number of black nodes =black-height($x$) or bh($x$)
（注意$bh(x)$不包含$x$本身，即本身是黑节点不记数，否则黑高和等价2-3-4树的高度不等）
我们称leaf为external node，而其他保存键值的为internal node
这里的$NIL$并不是用空指针表示，而是用一个实际的节点$T.nil$表示，颜色为BLACK，其他随意。用作哨兵处理边界条件：空指针没有颜色，而$T.nil$有（比如下面插入时，假如uncle是 ...
BinarySearchTree
搜索二叉树这里不对搜索二叉树做出定义，仅讲解主要操作
DATATYPE结点属性为$left,right,p(arents),key$，分别表示左孩子，右孩子，父（母）节点，键值
树仅保存$root$，表示整个树的根节点
$NIL$表示该位置为空（一般用空指针表示）
INSERT我们用$y$来表示trailing pointer,$z$表示欲插入的结点，$y$跟踪$z$，指向其父节点，即$z.p$。
为了维护BST的性质，我们需要与当前根节点进行比较，找到合适的空地插入，也正因此需要$y$来告诉我空地位置在哪，以便更新其父节点
伪码如下：
123456789101112131415161718TREE-INSERT(T,z)x ← T.rooty ← NILwhile x ≠ NIL do y ← x if z.key<x.key then x ← x.left else then x ← x.rightz.p ← yif y=NIL then T.root ← z elseif z.key<y.key then y.left ← z ...
无题
活动选择问题
Scheduling several competing activites that require exclusive use of a common resource,with a goal of selecting a maximum-size set of mutually compatible activities.Suppose we have a set $S=\{a_1,a_2,…,a_n\}$ of n proposed activities that wish to use a resource,such as a lecture,which can serve only one activity at a time.Each activity $a_i$ has a start time $s_i$ and a finish time $f_i$,where $0 \leq s_i < f_i < \infty$.If selected,activity $a_i$ takes place during the half-open ti ...
