算法图解-快速排序与散列表4-5/11 算法图解-快速排序与散列表

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)

文章图片
最优情况-O(logN) 只要每次随机的选择基准值，快速排序的平均运行时间即可达到最优情况，即O(N*logN)。快速排序是最快的排序算法之一。
5 散列表
散列表，一种一一映身，以便快速查找——python中的字典竟然就是一种散列表！
5.1 散列表的基本用途先看用途，再看散列表结构。

模拟映射关系；
防止重复；
缓存/记住数据，以免服务器再通过处理来生成它们。

5.2 散列表是什么样的直接解释有点复杂，用一个问题来描述：类似于超市中的产品条码对应到其价格——

如果用本子(无序)来记录，在查找时通常需要O(N)时间；
如果是有序的，则可以用之前的二分法，大约O(logN)时间；

【算法图解-快速排序与散列表4-5/11】但通常我们去小店里买东西时，问老板，老板大都是立即告诉我们单价的，他在‘大脑’中形成了一种映射，输出一个物品名称——对应输出一个价格。
我们希望在物品量更多时，仍能达到这一效果：即输入物品，立即获得一个价格反馈——这就像一种映射函数，在散列表中称为散列函数。
散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字——散列函数“将输入映射到数字”：满足两个条件，必需前后是一致的，即相同的输入得到相同的结果；它必需将不同的输入映身到不同的数字。
通过散列函数将一个数组和另一个数组对应起来，即构成了一个散列表（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!

将散列表用作缓存
即把用户经常重复发起的一些请求（如登录前页面）以散列表的形式存在本地，当用户发起请求时，先从该散列表中查询是否已在本地，在则不需传至服务器端处理。