装饰者模式（Decorate）

动态地将责任附加到对象上。若要扩展功能，装饰者提供了比继承更有弹性的替代方案。

设计原则四：类应该对扩展开放，对修改关闭。

如果使用过 Python，应该听过装饰器，虽然概念有点不同，但都是通过动态添加的方式给对象扩展功能。

快速排序

与归并排序一样，快速排序也使用了分治思想，下面是对一个典型的子数组 A[low … high] 进行快速排序的三步分支过程：

1. 分解：数组 A[low … high] 被划分为两个子数组 A[low … mid - 1] 和 A[mid + 1 … high]，使得 A[low … mid - 1] 中的每一个元素都小于等于 A[mid]，而 A[mid] 也小于等于 A[mid + 1 … high] 中的每个元素。
2. 解决：通过递归调用快速排序，对子数组 A[low … mid - 1] 和 A[mid + 1 … high] 进行排序。
3. 合并：因为子数组都是原址排序的，所以不需要合并操作：数组 A[low … high] 已经有序。

数据结构

栈（stack）

判断空栈：

1
2

stack_empty(S)
	return S.top == 0

压栈：

1
2
3

push(S, x)
	S.top++
	S[S.top] = x

弹栈：

1
2
3
4
5
6

pop(S)
	if stack_empty(S)
		error "underflow"
	else
		S.top--
		return S[S.top + 1]

散列表

直接寻址表

散列表

散列函数

开放寻址法

线性探查

二次探查

双重散列

二叉搜索树

递归查找：

1
2
3
4
5
6
7

tree_search(root, k)
	if root == null or k == root.key
		return root
	if k < root.key
		return tree_search(root.left, k)
	else
		return tree_search(root.right, k)

红黑树

旋转：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

left_rotate(T, root)
	rChild = root.right
	root.right = rChild.left
	if rChild.left != T.null
		rChild.left.parent = root
	rChild.parent = root.parent
	if root.parent == T.null
		T.root = rChild
	elif root == root.parent.left
		root.parent.left = rChild
	else
		root.parent.right = rChild
	rChild.left = root
	root.parent = rChild

插入：

观察者模式（Observer）

定义了对象之间的一对多依赖，当一个对象改变状态时，它的所有依赖者都会收到通知并自动更新。

初识

我们先来了解一下报纸和杂志的订阅是怎么回事：

1. 报社的业务就是出版报纸、杂志等各种出版物。
2. 如果我想看报社的 A 报纸和 B 杂志，那么就向报社订阅 A 报纸和 B 杂志。
3. 当他们有新的 A 报纸或 B 杂志出版时，就会向你派送，只要你是他们的订户，你就会一直收到新报纸，新杂志。
4. 如果你不想看 B 杂志了，取消订阅，他们就不会再送新的 B 杂志给你了。但不会影响你订阅的 A 报纸。
5. 只要报社还在运营，就会一直有人向他们订阅或取消报纸等出版物。

在观察者模式中，出版者报社 = 主题（subject），而我们订阅者 = 观察者（observer）。

排序和顺序统计量

堆排序

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树（除了最底层，该树是完全满的，而且是从左到右填充）。

表示堆的数组 A 包括两个属性：

• A.length（通常）给出数组元素的个数。
• A.heap_size 表示有多少个堆元素存储在该数组中。
  也就是说，虽然 A[A.length] 可能都存有数据，但只有 A[A.heap_size] 中存放的是堆的有效元素。（0 <= heap_size <= length）