《算法图解》笔记 ii

快速排序

快速排序是一种常用的排序算法，比选择排序快得多（O(n^2)）,快速排序也使用了D&C。

1. 选择基准值
2. 将数组分成两个子数组：基准值左边的数组和基准值右边的数组
3. 对这两个数组进行快速排序

来写一下代码实现：

def quicksort(list):
    if len(list)<2:
        return list
    else:
        #暂且取第一个值作为基准值
        pivot=list[0]
        less=[]
        greater=[]
        for item in list:
            if item<pivot:
                less.append(item)
            if item>pivot:
                greater.append(item)
        return quicksort(less)+[pivot]+quicksort(greater)


if __name__ == '__main__':
    test_list=[2,43,53,12,542,3253]
    print(quicksort(test_list))

快速排序的最糟情况是O(n^2),O(n2)已经很慢了，为什么还要叫它快速排序呢?

快速排序的平均运行时间为O（nlogn）,而合并排序的时间总是O（nlogn），合并排序似乎更有优势，那为什么不用合并排序呢？

因为大O表示法中的n是一个常量，当两种算法的时间复杂度不一样时，即使n在数值上不同，对总时间的影响很小，所以通常不考虑。

但有些时候，常量的影响很大，对快速排序和合并排序就是这样，快速排序的常量小得多，所以当这两种算法的时间复杂度都为O（nlogn）时，快速排序要快得多。而相较于最糟的情况，快速排序遇上平均情况的可能性更大，所以可以稍稍忽视这个问题。（快速排序最糟的情况下调用栈为O(n),在最佳情况下，调用栈长O(logn)）

散列表

使用散列函数和数组可以构建散列表，散列表是包含额外逻辑的数据结构。

但是要编写出完美的散列函数几乎不可能，假如给两个键分配的空间相同的话就会出现冲突。如何处理冲突呢?最简单的办法是：假如在某一空间上产生冲突，就在这一空间后再加上一个链表。但是假如这个链表很长，会很影响查找的速度（链表只能顺序查找，查找时间为O(n)）

所以一个能尽量避免冲突的散列函数是多么重要，那么怎么编写一个性能较高的散列表呢？

1. 较低的填装因子（一旦填装因子大于0.7，就需要调整长度）
2. 良好的散列函数（让数组中的值呈均匀分布，可以了解下SHA函数）

广度优先搜索

广度优先搜索能够解决两个问题：

1. 两个节点之间是否存在相连的路径
2. 最短的距离是多少？这个“最短距离”的含义有很多种。

想象这么一个问题：你想在你的微信好友和好友的好友中寻找是否有人是一名消防员，该如何查找？并且尽可能这人和你的关系更近些。

实现：

from collections import  deque

def is_fireman(person):
    #假设一个很简单的判断，假设消防员的名字尾部为f
    return person[-1]=='f'

def search_fireman(search_graph):
    search_queue=deque()
    search_queue+=search_graph["i"]
    while search_queue:
        person=search_queue.popleft()
        if is_fireman(person):
            return person
        else:
            if search_graph.__contains__(person):
            #假如这个人不是消防员，就将这个人的朋友全加入队列
                search_queue+=search_graph[person]
    return "你的圈子里没有消防员"

if __name__ == '__main__':
    test_graph={}
    test_graph["i"]=["Alice","Abby","Barry"]
    test_graph["Alice"]=["Bob","Tom"]
    test_graph["Abby"]=["Cart","Jay"]
    test_graph["Barry"]=["Welf","Zos"]
    print(search_fireman(test_graph))

image