算法图解|快速排序和广度优先搜索

快速排序

快速排序是一种常用的排序算法，比选择排序快得多。

快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序。

在调用栈的每层都涉及O(n)个元素

• 在平均情况下(随机地选择用作基准值的元素),即最佳情况下，栈长为O(log n),其运行时间为O(n log n)
• 在最糟情况下(总是将第一个元素用作基准值)，栈长为 O(n),其运行时间为O(nxn)。

过程

• 首先，从数组中选择一个元素，这个元素被称为基准值(pivot)

• 将数组分成两个子数组:小于基准值的元素和大于基准值的元素。

• 对这两个子数组进行快速排序：对其递归的调用快速排序。

#归纳证明：基线条件和归纳条件

代码示例：

def quicksort(arr):
    # 基线条件：为空或只有一个元素的数组是有序的
    if len(arr) < 2:
        return arr
    else:
        # 递归条件，基准值
        pivot = arr[0]
        # 小于基准值
        less = [i for i in arr[1:] if i <= pivot]
        # 大于基准值
        graeter = [i for i in arr[1:] if i > pivot]
        # 递归对两个子数组快速排序，单元化处理
        return quicksort(less) + [pivot] + quicksort(graeter)

print(quicksort([1,3,4,2,6]))  #[1, 2, 3, 4, 6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

广度优先搜索

是一种用于图的查找算法：这种算法将搜遍整个关系网
#在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查 二度关系

运行时间：
关系网中每个顶点添加到队列需要的时间是固定的， 即为O(1)，所以需要的总时间为O(V)
每个顶点的连接边数O(E)
O(V + E)，其中V为顶点(vertice)数，E为边数。

#将键映射到值，构建关系网

graph = {}
graph["asimov"] = ["tom", "bob", "alice"]
graph["tom"] = []
graph["bob"] = ["jonny"]
graph["alice"] = []
1
2
3
4
5

在asimov的关系网中找到jonny

要搜索的目标/结束搜索的基线条件

def person_is_seller(name):
    return name == 'jonny'
1
2

搜索

from collections import deque
def search(name):
    # 创建一个队列（双端队列）
    search_queue = deque()
    # 入队,第一层只有graph[name]
    search_queue += graph[name]
    # 存放搜索过的
    searched = []
    # 只要队列存在
    while search_queue:
        # 从左出队
        person = search_queue.popleft()
        # 仅当没有检查过时
        if not person in searched:
            # 如果搜索到
            if person_is_seller(person):
                print("搜索到的结果%s" % person)
                return True
            else:
                # 上一层没有的话会将下一层graph[person]入队，以此类推。
                search_queue += graph[person]
                # 添加到搜索过的数组，避免重复搜索
                searched.append(person)
    # 检查过所有都没有结果的话返回False
    return False


search("asimov")  # 搜索到的结果jonny
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28