这篇笔记主要是关于排序和查找的算法。在这个系列的笔记全部都会采用伪代码的形式；除非在一些时候数据结构对于一个算法的实现非常重要，否则大部分时候我们将主要考虑算法本身，而不是算法的实现。
下表为常见的排序算法的 Cheat Sheet.
排序
Input：N 个无序的元素（在 < 上有全序）。
Output：N 个有序的元素，按照从小到大。
选择排序 Selection Sort
对于数组 A：
for i = 1 to length(A) - 1
// 维护每个循环中的最小的数值
min_index = i
for j = i+1 to length(A)
// 将 a[i] 与 a[i, length(A)]中最小的元素交换
if A[j] < A[min_index]
min_index = j
swap A[i] and A[min_index]该算法将第 i 小的元素放到 a[i] 中。数组第 i 个位置的左边是 i 个最小的元素，且它们不会再被访问。
时间复杂度：平均和最差 O(n²)，最好 O(n)
插入排序 Insertion Sort
for i = 2 to length(A)
card = A[i]
j = i - 1
while j > 0 and A[j] > card
A[j+1] = A[j]
j = j - 1
A[j+1] = card特点：比较吃初始状态。如果初始时已经基本有序，则排序会快很多。
时间复杂度：平均和最差 O(n²)，最好 O(n)
归并排序 Merge Sort
mergeSort(A, left, right)
if left < right
middle = (left + right) / 2
mergeSort(A, left, middle)
mergeSort(A, middle+1, right)
merge(A, left, middle, right)
else return归并排序应用的是递归的思想，采用 Divide and Conquer 的思路，每次处理一半的排序，并最后将其统一起来。归并排序每次在中位的位置分开，然后将中位之前的部分排序，中位之后的部分排序，最后再将排序完成的两个部分和中位数值归并。
时间复杂度：平均、最差和最好均为 O(n log n)
快速排序 Quick Sort
quickSort(A, low, high)
if low < high
pi = partition(A, low, high)
quickSort(A, low, pi-1)
quickSort(A, pi+1, high)
else return简而言之，快速排序每次选择一个基准值，然后把比基准值小的扔到基准值的左边，比它大的扔到基准值的右边，然后对左右两边再 recursively 进行一次快速排序。
平均情况：O(n log n)
最好情况：O(n log n)
最坏情况：O(n²) - 当数组已经是排序状态，或者所有元素相等
查找
虽然最暴力的 Brute Force 肯定可以在 O(n) 时间内解决查找的问题，但是查找可以变得更快很多。这需要借助一些数据结构的帮助。
二叉搜索树 Binary Search Tree / BST
二叉搜索树是一个树状数据结构。对于每一个节点，它保存以下数值。
Node {
Node left;
Node right;
Node parent;
Key key;
}其中，key是一个可以比较大小的数值。left, right, parent 分别指向左节点、右节点、父节点，key 保存这个节点的数值。
二叉搜索树满足以下的性质。
左子树的最大 key 不超过当前节点的 key。
右子树的最小 key 不小于当前节点的 key。
根节点是唯一父节点指向 null 的节点。
按序遍历算法（中序遍历）
使用迭代就可以满足遍历需求。这个算法的复杂度是 Θ(n).
InorderTraverse(Node n) {
// reach leaf
if(!n) return;
InorderTraverse(n.left);
print(n.key);
InorderTraverse(n.right);
}查找
对于高度为 h 的二叉树，查询二叉树的算法复杂度是 O(h). 算法与遍历很类似。
BSTSearch(Node n, Key k) {
// reach leaf
if(!n) return false;
if(n.key == k) return true;
return BSTSearch(n.left) || BSTSearch(n.right);
}如果要返回该节点所在的指针（如果存在的话，否则就返回 null），那稍微修改一下就行。
BSTSearchKey(Node n, Key k) {
// reach leaf
if(!n) return null;
if(n.key == k) return n;
if(k < n.key) return BSTSearchKey(n.left);
else return BSTSearchKey(n.right);
}一句话带过最大和最小值的查找，复杂度也会是 O(h)。我们不断地往左节点前行，直到触底，就能找到最小值；往右节点前行，就能找到最大值，这也是 BST 的性质。
插入删除
插入与删除的操作复杂度也都是 O(h)，但是比较复杂的是它们都会动态地调整树状结构。
Add(Node T, Key z) {
y = null;
x = T;
while (x){
y = x;
if(z < x.key)
x = x.left;
else x = x.right;
}
// now x = null
// Case 1: Tree is empty
if (y == NULL) {
T.key = z;
T.left = null;
T.right = null;
} else if (z < y.key) {
y.left = new Node(z);
} else {
y.right = new Node(z);
}
}删除有四种情况，日后补充。
红黑树
二叉树的一个问题在于构建它的时候最坏的情况可能会导致所有节点只有左节点（或只有右节点），这样的话高度就变成了 n。这样不平衡的二叉树可能会导致性能并没有得到优化。红黑树是众多 BST 中，一种比较平衡的 BST，它可以保证基础的操作时间复杂度都为 O(lg n)。
红黑树的性质如下：
每个节点都是红色的或者黑色的，不会又红又黑，也不会是绿色的。
根节点是黑色的。
叶节点都是 null，且都是黑色的。
如果一个节点是红色的，那么它的两个子节点都是黑色的。
对于任意一个节点，从该节点到它的所有后代叶节点的简单路径上，都包含着相同数量的黑色节点。
一些派生的性质。有兴趣的话可以查阅相关的证明。
一个内部有 n 个节点的红黑树，其高度至多为 2lg(n+1)
参考文献：
Introduction to Algorithm, 3rd Edition
Comments