4 快速排序
4.1 分而治之（divide and conquer，D&C）
一种解决问题的思路：将新问题递归到可解决已解决的问题上去。或者可称为：归纳法。
使用 D&C 解决问题的过程包括两个步骤：
找出基线条件，这种条件必须尽可能简单。
不断将问题分解（或者说缩小规模），直到符合基线条件。
D&C 并非可用于解决问题的算法，而是一种解决问题的思路。
4.2 快速排序
使用D&C来解决，针对一个数组进行快速排序。
step1
先确定最简单的情况（即基线条件）—— 空数组，或只有1个元素的数组——这种数组不用排序！
#基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。
def quicksort(array):
if len(array) < 2:
return array
step2
比基线情况复杂一点时：有两个元素的数组——只需要比较这两个元素的大小即可。
step3
三个元素的数组：D&C 的思路——将数组分解，直到满足基线条件。
快速排序的做法是：从数据中选出一个基准值，然后找出比基准值小的元素及比基准值大的元素，相当于构造了一个分区，形成了：
- 一个由所有小于基准值的数字组成的子数组；
- 基准值；
- 一个由所有大于基准值的数组组成的子数组。
接下来要做的事情就是使用step2来解决即可，也就是，有三个元素的数组快速排序步骤如下：
- 选择基准值。
- 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
- 对这两个子数组进行快速排序。
依此类推，包含4个、5个，n个元素的情形也是如此。
快速排序代码
def quicksort(array):
if len(array) < 2:
return array ←------基线条件：为空或只包含一个元素的数组是“有序”的
else:
pivot = array[0] ←------递归条件
less = [i for i in array[1:] if i <= pivot] ←------由所有小于等于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] ←------由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
4.3 快速排序的速度
快速排序的性能高度依赖所选择的基准值，如果选择的基准值合适，速度最佳情况可达到O(NlogN) ,每层比较N次，层数由选择的基础值确定。
最糟情况则需要O(NN),这意味着每次选择的基准值都是最大或最小值。
只要每次随机的选择基准值，快速排序的平均运行时间即可达到最优情况，即O(N*logN)。 快速排序是最快的排序算法之一。
5 散列表
散列表，一种一一映身，以便快速查找——python中的字典竟然就是一种散列表！
5.1 散列表的基本用途
先看用途，再看散列表结构。
- 模拟映射关系；
- 防止重复；
- 缓存/记住数据，以免服务器再通过处理来生成它们。
5.2 散列表是什么样的
直接解释有点复杂，用一个问题来描述：类似于超市中的产品条码对应到其价格——
- 如果用本子(无序)来记录，在查找时通常需要O(N)时间；
- 如果是有序的，则可以用之前的二分法，大约O(logN)时间；
但通常我们去小店里买东西时，问老板，老板大都是立即告诉我们单价的，他在‘大脑’中形成了一种映射，输出一个物品名称——对应输出一个价格。
我们希望在物品量更多时，仍能达到这一效果：即输入物品，立即获得一个价格反馈——这就像一种映射函数，在散列表中称为散列函数。
散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字——散列函数“将输入映射到数字”：满足两个条件，必需前后是一致的，即相同的输入得到相同的结果；它必需将不同的输入映身到不同的数字。
通过散列函数将一个数组和另一个数组对应起来，即构成了一个散列表（hash table）.
如果不清楚，看一看python的字典结构即可：
book = dict()
book["apple"] = 0.67 ←------一个苹果的价格为67美分
book["milk"] = 1.49 ←------牛奶的价格为1.49美元
book["avocado"] = 1.49
print(book)
{'avocado': 1.49, 'apple': 0.67, 'milk': 1.49}
5.3 应用案例：
将散列表用于查找
电话本可以通过散列表来实现。查找速度近于O(1)时间。
电话本需要提供如下功能：
- 添加联系人及其电话号码。
- 通过输入联系人来获悉其电话号码。
简单点来说，用python中的字典来创建这样一个电话本再合适不过。
防止重复
向列表中增加数据时，先检查是否在散列表中即可。
# 一个防止重复投票的案例。
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
>>> check_voter("tom")
let them vote!
>>> check_voter("mike")
let them vote!
>>> check_voter("mike")
kick them out!
将散列表用作缓存
即把用户经常重复发起的一些请求（如登录前页面）以散列表的形式存在本地，当用户发起请求时，先从该散列表中查询是否已在本地，在则不需传至服务器端处理。
