1.时间复杂度和空间复杂度
2.查找算法
2.1 二分查询法
2.1.1 非递归代码
def erfen(data,target):
low = 0
high = len(data) - 1
while low < high:
mid = (low + high) // 2
if data[mid] == target:
return mid
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
return
2.1.2 递归代码
def diguierfen(data,target):
low = 0
high = len(data) - 1
if low < high:
mid = (low + high) // 2
if data[mid] == target:
return mid
elif data[mid] < target:
diguierfen(data[mid+1:high],target)
else:
diguierfen(data[0:mid-1],target)
else:
return
3.排序算法
3.1 冒泡排序
def maopao(data):
length = len(data)-1
for i in range(length):
for j in range(length-i):
if data[j]>data[j+1]:
data[j],data[j+1]=data[j+1],data[j]
思路：存在n个数排序时
第1轮 n-1次
第2轮 n-2次
第n-1轮 1次
外层循环n-1次，内存循环从n-1每次减少1直到1
for i in range(length):
for j in range(length-i):
外层是从0开始到n-1，内层是从0开始，每次减少1
i=0时，表示第1轮循环，需要比较n-1次
i=1时，表示第2轮循环，需要比较n-2次
3.2 优化版的冒泡排序
def maopao(data):
length = len(data)-1
for i in range(length):
exchange = False
for j in range(length-i):
print("#")
if data[j]>data[j+1]:
data[j],data[j+1]=data[j+1],data[j]
exchange = True
if not exchange:
break
3.3 选择排序
def xuanze(data):
length = len(data) - 1
for i in range(length):
minindex = i
for j in range(i+1,length+1):
if data[minindex]>data[j]:
data[minindex],data[j] = data[j],data[minindex]
定义第一个索引为最小值，每次遍历找出最小值，每次都是和自己后面一个值比较
3.4 快速排序
4.二叉树遍历
class note:
def __init__(self,data=None,left=None,right=None):
self.data = data
self.left = left
self.right = right class Tree:
def __init__(self,root):
self.root = root def pre(self,tree):
if tree is None:
return
print(tree.data)
self.pre(tree.left)
self.pre(tree.right) def mid(self,tree):
if tree is None:
return
self.mid(tree.left)
print(tree.data)
self.mid(tree.right) def after(self,tree):
if tree is None:
return
self.after(tree.left)
self.after(tree.right)
print(tree.data) if __name__=="__main__":
# node1 = note(data=1)
# node2 = note(node1, 0, 2)
# node3 = note(data=3)
# node4 = note(data=4)
# node5 = note(node3, node4, 5)
# node6 = note(node2, node5, 6)
# node7 = note(node6, 0, 7)
# node8 = note(data=8)
# root = note(node7, node8, 100)
root = note('D',note('E'),note('F'))
# root = note('D', note('B', note('A'), note('C')), note('E', right=note('G', note('F'))))
t = Tree(root)
t.pre(t.root)
t.mid(t.root)
t.after(t.root)
分别为前中后序遍历