二分查找
经典的二分查找也分为了三个问题：
- 在没有重复元素的数组中找到对应元素
- 在有重复元素的数组中找到上界
- 在有重复元素的数组中找到下界
二分查找例题
LeetCode 33 搜索旋转排序数组
LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
Rotated Sorted Array
Mountain Sequence
OOXX 问题
Search Sorted Matrix
值得注意的细节
使用 left + (right - left) / 2 而不要使用 (left + right) / 2, 避免溢出。
排序
适合链表的排序算法：选择排序
如果需要一次按照两个键排序，必须使用稳定的排序算法。
排序算法选择准则：
1．待排序的记录数目 n 的大小；
2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3．关键字的结构及其分布情况；
4．对排序稳定性的要求。
bloomfilter 错误率 (1-1/n)^k n 为数组大小，k 为 hash 个数
堆
堆可以分成两种：大根堆和小根堆。他们两个的区别是显然的，不多说了，下面的讨论以大根堆为例。
堆的两种基本操作：向上调整和向下调整。
- 向上调整指的是，在堆的尾部插入一个元素，然后再使堆满足性质的行为，也就是需要这个元素向上找到他的位置；
- 向下调整指的是，当堆顶的一个元素可能不满足性质的时候，让这个元素向下找到他的位置。
# 这里我们以 0 为索引起点
def left(i): return 2 * i + 1
def right(i): return 2 * i + 2
def parent(i): return (i-1) // 2
def up(h, i):
"""向上比较简单，因为只需要考虑父元素就行了"""
while i > 0 and h[i] > h[parent(i)]:
h[i], h[parent(i)] = h[parent(i)], h[i]
i = parent(i)
def down(h, i, n):
"""向下稍微复杂一些，因为需要考虑两个子节点"""
while left(i) <= n:
if right(i) <= n and h[right(i)] > h[left(i)]:
j = right(i)
else:
j = left(i)
if h[j] <= h[i]:
break
h[i], h[j] = h[j], h[i]
i = j
构建堆
有了以上两种基本操作，构建堆也就可以按两种方式：
- 从前往后构建，也就是把每一个新加入的元素理解为从后方插入，直接向上调整就行了
- 从后往前构建，这样其实相当于把左右两个子堆合并为一个新堆，但是新堆的根节点不一定满足堆续，只需要向下调整根节点就行了
两种方法的代码分别是：
def build_heap_forward(h):
for i in range(len(h)):
up(h, i)
def build_heap_backward(h):
for i in range(1, len(h)):
down(h, len(h) - i)
堆排
有了上面的代码，那么我们的堆排代码也就很简单了
def heap_sort(h):
build_heap(h)
for i in range(len(h) - 1, 0, -1):
h[0], h[i] = h[i], h[0]
down(h, 0)
字符串排序
可以使用低位优先排序和高位优先排序两种方法。低位优先排序就直接排就好了，高位优先排序很自然是一种递归算法，首先排序高位，然后排序s[1:]。
参考资料
- https://leetcode.com/problems/sort-an-array/discuss/357592/O(n-log-n)-time-O(1)-space-HeapSort
- LibUV 中的最小二叉堆