本文介绍基本算法。
算法图解：
数组
1. 是固定大小的，申请的个数是一定的。
2. 弊端：如果存储的个数不足申请的个数，则是浪费内存；如果是超过了申请的个数，则还需要转移数据。
3. 跳跃获取元素的时候，只要指定索引即可。支持随机访问，（和链表相反）
4. 删除某元素后，后面的元素必须要向前移动。所以是O(n)。
链表
1. 存储的是元素在内存中的存储地址，而非元素本身。
2. 插入元素方便，指定地址即可。
3. 要想跳跃的读取元素，效率很低，只能一个接一个的获取元素直到找到想要的元素。支持顺序访问，不能随机访问
4. 删除时指定元素地址即可。仅仅只有能够立即访问要删除的元素时，操作时间才为O(1)，通常记录的是第一个和最后一个元素，所以删除这2个元素时运行时间为O(1)。
只考虑最坏情况，根据大O标记法，得出：
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
O(1)：常量时间
O(n)：线性时间
查找方法
二分查找
注意：要查找的列表对象必须是已经排序的。
上代码：
def find(item: int, aim_list: list):
low = 0
high = len(aim_list) - 1
while low <= high:
mid = (low + high) / 2
aim = aim_list[int(mid)] # 使用的py3，此处使用int向下取整
if item == aim:
return 'OK'
if item > aim:
low = mid + 1
if item < aim:
high = mid - 1
return None
aim_list = [1, 2, 7, 8, 9, 32, 33, 34, 55, 65, 87, 98]
item = 87
print(find(item, aim_list))
二分查找运行时间为：O(log n)
排序方法
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 把第一个元素作为最小的元素，和第二个比较：1大于2则2作为最小的元素；1小于2则1还是最小的，再和第三个比较。同时要记录下索引。
列表的pop方法：指定索引删除，并返回索引对应的值。
例如：
In [1]: d = [1,2,3,4]
In [2]: d.pop(1) # 1是索引值
Out[2]: 2 # 2是返回所删除的值
In [3]: d
Out[3]: [1, 3, 4]
上代码：
def findsmaller(array): # 找出最小值
smaller = array[0]
smaller_index = 0
for i in range(1, len(array)):
if array[i] < smaller:
smaller = array[i]
smaller_index = i
return smaller_index # 返回最小值的索引
def sort(array):
new_list = []
for x in range(len(array)):
smaller_index = findsmaller(array) # 返回最小值的索引
new_list.append(array.pop(smaller_index)) # 添加到新的列表中
return new_list
array_new = [2, 3, 54, 6, 76, 4, 62, 1, 4, 67, 8]
print(sort(array_new))
选择排序最坏复杂度: O(n^2)
稳定性：不稳定
快速排序
上代码：
# coding=utf8
def quicksort(array):
if len(array) < 2: # 设定返回条件
return array
else:
poivt = array[0] # 设定基准值
less = [i for i in array[1:] if i < poivt] # 得出比基准值小的数组
bigger = [i for i in array[1:] if i > poivt] # 得出比基准值大的数组
return quicksort(less) + [poivt] + quicksort(bigger) # 递归
array = [2, 1, 55, 33, 65, 232, 65, 7, 454, 87, 798, 32, 99, 65, 98, 98, 65, 9, 34, 879, 454, 875, 344, 8, 454, 675675]
print(quicksort(array))
输出结果：
[1, 2, 7, 8, 9, 32, 33, 34, 55, 65, 87, 98, 99, 232, 344, 454, 798, 875, 879, 675675]
Process finished with exit code 0
递归
递归只是程序更简洁，不会提升性能。
为了不让函数无线循环，添加基线条件和递归条件。
def countdown(i):
print (i)
if i < 0: # 作为基线条件，防止无限循环
return
else: # 递归条件
countdown(i - 1) # 实现递归，自己调用自己
栈
栈：先进的后出
一个函数的执行，就是出栈的过程。
例如：
def greet(name):
print ('Hello, %s' %name)
greet2(name)
print( 'Lets Go' )
bye()
def greet2(name):
print( 'How are %s ' %name )
def bye()
print( 'Bye Bye' )
当首先调用greet函数的时候，计算机会为其分配一块内存，其中存放变量等内容；当执行到调用函数greet2时，计算机会同样为greet2函数分配内存。
计算机使用一个栈表示这些内存块，其中第二块内存（greet2函数的内存）是在第一个内存（greet函数的neicun）之上的。当greet2函数调用并执行完毕，会将这块内存从栈顶弹出。此时，栈顶的内存块是greet函数的，即返回到了函数greet。并且从先前停止的位置再继续执行。执行到调用函数bye时，bye函数的内存块被放置到栈顶，执行完毕后同样被弹出，返回greet函数。
这个栈用于存储多个函数的变量，称为调用栈。
递归函数调用栈
代码：
def fact(x):
print (x)
if x == 1:
return 1
else:
return x * fact( x -1)
exp: fact(3)
整个函数调用以及调用栈的过程和上述的类似。先弹出fact(1), 再fact(2)， 最后 fact(3)。
栈很方便，但是会占用很大的内存。如果出现占用内存大了，只能：
1. 重写代码，使用循环。
2. 使用尾递归。（高级递归）
编写涉及数组的递归函数时，基线条件是数组为空或者包含一个元素。一定要多检查基线条件。
大O标记是基于最坏情况得出：
| 算法 | 二分查找 | 简单查找 | 快速排序 | 选择排序 | 旅行商问题算法 |
|---|---|---|---|---|---|
| 大O标记法 | O(log n) | O(n) | O(n log n) | O(n^2) | O(n!) |
合并排序和快速排序的复杂度都是O(n log n)
整个算法所需的时间 = 每层栈运行所需的时间 * 栈的层数
例如： 快速排序运行时间 = O(n)[每层栈运行的时间] + O(log n)[栈的层数] = O(n log n)
调用栈的高度： 即栈的层数
大O表示法中常量有时候很重要。
数据结构：数组，链表，栈（不能用于查找）
散列表：
散列函数是将输入映射到数字。散列函数和数组共同创建称为散列表的数据结构。
python中字典就是散列表的实现。即，散列表的键作为输入，得出的是值。
散列表是一种包含额外逻辑的数据结构。数组和链表是直接映射到内存。散列表使用散列函数确定元素的位置。
散列表和数组获取元素的速度是一样的。
缓存是常见的加速方式。而缓存的数据存储在散列表中。
填装因子 = 要填装到散列表的元素数 / 位置总数
填装因子度量的是散列表中有多少位置是空的。
填装因子部分略过
广度优先搜索：
最短路径问题
解决最短路径问题的算法称为广度优先搜索。
广度优先解决的2个问题：
1. 从A节点出发，有前往B节点的路么
2. 从A出发，到B节点那个路径最短
查找最短路径：
一度关系> 二度关系>三度关系…………
先查找一度关系，再二度关系，依次查询。
反转一个链表：
#!/usr/bin/env python3
#!-*-encoding:utf-8-*-
#定义一个基于节点类的单链表对象类
class LNode:
#_next防止与python标准函数next重名
def __init__(self,elem,_next=None):
self.elem=elem
self.next=_next
#定义单链表
class LList:
def __init__(self):
#初始化为None表示建立的为空表
self._head=None
#判断单链表是否为空
def is_empty(self):
return self._head is None
#表头插入数据
def prepend(self,elem):
self._head=LNode(elem,self._head)
#删除表头节点并返回节点里边的数据
def pop(self):
if self._head is None: #无节点引发异常
raise LinkedListUnderflow('in pop')
e=self._head.elem
self._head=self.head.next
return e
#后端操作，后端加入
def append(self,elem):
if self._head is None:
self._head=LNode(elem)
return
p=self._head
while p.next is not None:
p=p.next
p.next=LNode(elem)
#删除最后一个元素
def pop_last(self):
#如果链表为空表
if self._head is None:
raise LinkedListUnderflow('in pop_last')
#如果链表只有一个元素
p=self._head
if p.next is None:
e=p.elem
self._head=None
return e
while p.next.next is not None: #直到p.next是最后一个元素
p=p.next
e=p.next.elem
p.next=none
return p
def find(self,pred):
p=self._head
while p is not None:
if pred(p.elem):
return p.elem
p=p.next
#打印所有的节点元素
def print_all(self):
p=self._head
while p is not None:
print(p.elem)
print('end')
p=p.next
#应用实例：
mlist1=LList()
for i in range(1,10):
mlist1.prepend(i)
for i in range(11,20):
mlist1.append(i)
mlist1.print_all()