程序 = 数据结构 + 算法
计算机一秒能进行约10^7次运算
时间复杂度：用来评估算法运行效率的一个式子
O(1)、O(n)时间规模，保留量级。
while n>1:
print(n)
n = n//2
# 时间复杂度记为O(logn)常见：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
如何判断算法复杂度
- 确定问题规模n
- 循环减半过程->logn
- k层关于n的循环—>n↑k
空间复杂度：用来评估算法内存占用大小的式子
表示方式和时间复杂度一样，空间换时间
递归
调用自身、结束条件
def fun(x):
if x > 0:
fun(x-1)
print(x)
def fun1(x):
if x > 0:
print(x)
fun1(x-1)
fun(4)
print()
fun1(4)先递归后打印 和 先打印后递归
递归实例：汉诺塔问题
n个盘子时：
- 把n-1个圆盘从A经过C移动到B
- 把第n个圆盘从A移动到C
- 把n-1个圆盘从B经过A移动到C
def hanoi(n, a, b ,c):
if n>0:
hanoi(n-1, a, c, b)
print("moving from %s to %s" % (a, c))
hanoi(n-1, b, a, c)
hanoi(3, 'A', 'B', 'C')查找
- 输入：列表、待查找元素
- 输出：元素下标（未找到时返回None或者-1）
- 内置列表查找函数index（）
顺序查找（线性）
def linear_search(data_set, value):
for i in range(len(data_set)):
if data_set[i] == value:
return i
else:
return None二分查找（折半）
def binary_search(li, val):
left = 0
right = len(li)-1
while (left <= right): # 候选区有值
mid = (left+right)//2
if li[mid] == val:
return mid
elif li[mid] > val: # 待查找的值在mid左侧
right = mid - 1
else:
left = mid + 1 # 待查找的值在mid右侧
else:
return None排序
将一组“无序”的记录序列调整为“有序”的记录序列
列表排序：将无序列表变为有序列表
- 输入：列表
- 输出：有序列表
- 升序和降序
- 内置排序函数：sort()
| 排序Low B三人组 | 排序NB三人组 | 其他排序 |
|---|---|---|
| 冒泡排序 | 快速排序 | 希尔排序 |
| 选择排序 | 堆排序 | 计数排序 |
| 插入排序 | 归并排序 | 基数排序 |
排序Low B三人组
冒泡排序（O（n2））
- 列表每两个相邻的数，如果前面比后面大，则交换这两个数
- 一趟排序完成后，则无序区减少一个数，有序区增加一个数
- 代码关键点：趟、无序区范围
def double_sort(li):
for i in range(len(li)-1): # 第一趟
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
# temp = li[j]
# li[j] = li[j+1]
# li[j+1] = temp
li[j], li[j+1] = li[j+1], li[j]选择排序（O（n2））
- 一趟排序记录最小的数，放到第一个位置
- 再一趟排序记录记录列表无序区最小的数，放到第二个位置
- 算法关键点：有序区和无序区、无序区最小数的位置
def select_sort_simple(li):
li_new=[]
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
if min_loc != i:
li[i], li[min_loc] = li[min_loc], li[i]插入排序（O（n2））
- 初始时手里（有序区）只有一张牌
- 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
def insert_sort(li):
for i in range(1,len(li)): # i表示摸到的牌的下标
temp = li[i]
j = i - 1 # j指的是手里的牌，下标
while j >= 0 and li[j] >temp:
li[j+1] = li[j]
j -= 1
li[j+1] = temp排序NB三人组
快速排序（快）
- 取第一个元素p，使元素p归位
- 列表被p分为两部分，左边都比p小，右边都比p大；
- 递归完成排序
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: # 从右边找找比tmp的数
right -= 1 # 向左走一步
li[left] = li[right] # 把右边的值放到左边的空位置
while left < right and li[left] <= tmp:
left += 1 # 向右走一步
li[right] = li[left] # 把左边的值放到右边的空位置上
li[left] = tmp # 把tmp归位
return left
def quick_sort(li, left, right):
if left < right:
mid = partition(li, left ,right)
quick_sort(li, left , mid-1)
quick_sort(li, mid+1, right)时间复杂度O（nlogn）
堆排序
前传：树与二叉树。数是一种数据结构，比如目录结构，可以进行递归定义。树是由n个节点组成的集合：如果n=0，那是一颗空树，如果n>0，那么存在一个节点作为树的根节点，其他节点可以分为m个集合。
Pass占位。。。
