算法图解-读书笔记

快速排序

快速排序是一种常用的排序，比选择排序。

基线条件为：数组为空或只包含一个元素，这种情况下根本不用排序。

python
def quicksort(array):
	if len(array) <2:
	return array

基准值：将任意一个元素作为基准值

两个元素的排序

检查第一个元素是否比第二个元素小，如果不比第二个小，就变换他们的位置

三个元素的数组

要使用D&C（分而治之），需要将数组分解，直到满足基线条件。下面介绍快速排序的工作原理：

从数据中选择一个元素，这个元素被称为基准值
找出比基准值小的元素以及比基准值大的元素

分为三个区（两个子数组是无序的）：
- 一个由所有小于基准值的数字组成的子数组
- 基准值
- 一个由所有大于基准值的数字组成的子数组
如果子数组是有序的，左边的数组+基准值+右边的数组
如何对子数组进行排序呢？对于包含两个元素的数组以及空数组，快速排序知道如何将他们排序，因此只要对两个子数组进行快速排序，再合并结果，就能得到一个有序数组！

归纳证明

归纳证明是一种证明算法行之有效的方式，它分为两步：基线条件和归纳条件

是不是有点似曾相识的感觉？例如，假设我要证明我能爬到梯子的最上面。

递归条件是这样的：如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果站在第二个横档上，就能爬到第三个横档。这就是归纳条件。

而基线条件是这样的，即我已经站在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端

对于快速排序，可使用类似的推理。

在基线条件中，我证明这种算法对空数组或包含一个元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。

因此，我可以说，快速排序对任何长度的数组都管用。

快速排序的代码

python
# coding:utf-8
def quicksort(li):
    if len(li)<2:
        return li
    else:
        pivot = li[0]
        less = [i for i in li[1:] if i <= pivot]
        greater = [i for i in li[1:] if i > pivot]

        return quicksort(less)+[pivot]+quicksort(greater)

print(quicksort([10,5,3,6,9]))

大O表示法

快速排序的独特之处在于，其速度取决于选择的基准值。

大O的表示法，分平均情况和最糟的情况，像快速排序平均的情况是nlogn，最糟的是n方


题目练习：
使用大O表示法时，下面各种操作都需要多长时间？
4.5 打印数组中每个元素的值。
o(n)

4.6 将数组中每个元素的值都乘以2。
o(n)

4.7  只将数组中第一个元素的值乘以2。
o(1)

4.8 根据数组包含的元素创建一个乘法表，即如果数组为[2, 3, 7, 8, 10]，首先将每个元素
都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7，以此类推。
o(n方)

##总结

D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n) 快得多。

散列表

目标：

学习散列表——最有用的基本数据结构之一
学习散列表的内部机制：实现、冲突和散列函数

定义

散列函数是这样的函数，即无论给它什么数据，它都还你一个数字。如果用专业术语来表达，散列函数是“将输入映射到数字”

要满足的要求：

它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须为4。如果不是这样，散列表将毫无用处。
它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

结合散列函数和数组创建了一种被称为散列表的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的位置。

python提供的散列表实现为——字典，你可以使用函数dict来创建散列表

63页练习对于同样的输入，散列表必须返回同样的输出，这一点很重要。如果不是这样的，就无法找到你在散列表中添加的元素！请问下面哪些散列函数是一致的？ 5.1 f(x) = 1 一致不是理想的情况，但是属于散列函数 5.2 f(x) = rand() 不一致输入一样的时候，输出必须一样 5.3 f(x) = next_empty_slot()-返回散列表中下一个空位置的索引不一致还不了数字 5.4 f(x) = len(x) 一致

应用案例

应用于查找
防止重复
用作缓存

缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！

仅当URL不在缓存中时，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进行处理了。

总结

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

冲突

冲突：给两个键分配的位置相同。

冲突很糟糕，必须要避免，不然就会出现输入与输出的不匹配

处理冲突的最简单的方法：如果两个键映射到了同一个位置，就再这个位置存储一个链表，但是这种情况会影响到散列表的查询速度

这里有两个经验教训：

散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很好，这些链表就不会很长！

性能

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！

但在最糟情况下，散列表的各种操作的速度都很慢。因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：

较低的填装因子（数组中被占用的位置数。例如：散列表中有5个位置，只有2个被占用，因子为0.4）一旦填装因子大于1，就超出了数组的位置，这个时候就需要调整长度，调整长度是需要很长的工作时间的，一旦超过0.7就该调整列表的长度
良好的散列函数良好的散列函数让数组中的值呈均匀分布，糟糕的散列函数让值扎堆，导致大量的冲突

广度优先

目标

使用新的数据机构图来建立网络模型
可对图使用算法回答“到X的最短路径是什么？”等问题
有向图和无向图
拓扑排序，这种排序算法指出了节点之间的以来关系

初识

广度优先搜索让你能够找出两样东西之间的最短距离，使用广度优先搜索可以：

编写国际跳棋AI，计算最少走多少步就可获胜；
编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
根据你的人际关系网络找到关系最近的医生。

图模型

图是什么？

图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为令居。图用于模拟不同的东西是如何相连的。

广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：

从节点A出发，有前往节点B的路径吗？
从节点A出发，前往节点B的哪条路径最短？

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在Facebook，你与芒果销售商有联系吗？为此，你可在朋友中查找。

这种查找很简单。首先，创建一个朋友名单。

然后，依次检查名单中的每个人，看看他是否是芒果销售商。

假设你没有朋友是芒果销售商，那么你就必须在朋友的朋友中查找。

检查名单中的每个人时，你都将其朋友加入名单。

这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际关系网中找到一位芒果销售商。因此，如果Alice不是芒果销售商，就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网，直到找到芒果销售商。这就是广度优先搜索算法。

查询最短路径

谁是关系最近的芒果销售商。例如，朋友是一度关系，朋友的朋友是二度关系

你按顺序依次检查名单中的每个人，看看他是否是芒果销售商。这将先在一度关系中查找，再在二度关系中查找，因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径。

注意，只有按添加顺序查找时，才能实现这样的目的。

队列

队列只支持两种操作：入队和出队。

如果你将两个素加入队列，先加入的元素将在后加入的元素之前出队。因此，你可使用队列来表示查找名单！这样，先加入的人将先出队并先被检查。——保证了添加顺序

实现图

表示这种映射关系的python代码如下：

python
graph = {} 
graph["you"] = ["alice", "bob", "claire"]

注意：“你”被映射到了一个数组，因此graph[“you”]是一个数组，其中包含了“你”的所有邻居

表示图的代码：

python
graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []

实现算法

首选，创建一个队列。在python中，可以使用函数deque来创建一个双端队列

python
from collection import deque
search_queue = deque()
search_queue+=graph['you']

其次，将你的这些邻居加入到搜索队列中

python
while search_queue: # 只要队列不为空
    person = search_queue(person) # 就取出其中的第一个人
    if person_is_seller(person):  # 检查这个人是否是芒果商
        print(person+"is a mango seller") # 是芒果销售商
        return True
    else:
        search_queue+=graph[person]  # 不是芒果商，将找个人的朋友都加入搜索队列

def person_is_seller(name):
    return name[-1] == 'm'

算法的结束条件：

找到一位芒果销售商
队列变成空的，这意味着你的人际关系网中没有芒果销售商

优化：检查一个人之前，要确认之前没检查过他

python
# coding:utf-8
from collections import deque

def search(name): 
    search_queue = deque() 
    search_queue += graph[name]
    print(search_queue)
    searched = [] 
    while search_queue:
        person = search_queue.popleft() 
        if not person in searched:
            if person_is_seller(person): 
                print(person + " is a mango seller!" )
                return True 
            else: 
                search_queue += graph[person] 
                searched.append(person)
    return False
def person_is_seller(name): 
 return name[-1] == 'm'
graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []
search("you")

运行时间

如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为O(边数)。

你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为 O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。

从某种程度上说，这种列表是有序的。如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。

假设你正在规划一场婚礼，并有一个很大的图，其中充斥着需要做的事情，但却不知道要从哪里开始。这时就可使用拓扑排序来创建一个有序的任务列表。

目录