时间复杂度
时间复杂度是用来估计算法运行时间的式子（单位）。
image.png
时间复杂度小结
image.png
空间复杂度
用来计算一个算法临时占用内存的式子
递归复习
1、调用自身
2、结束条件
lowB三人组
冒泡排序
冒泡排序：列表在内存重只存一份，所以不需要重复赋值
import random
from timewrap import * #时间装饰器
# 初级版本
@cal_time
def bubble_sort(li):
for i in range(len(li) - 1): #循环的躺数为总的躺数-1，因为最后一步没必要走
# i 表示趟数
# 第 i 趟时： 无序区：(0，len(li) - i)
for j in range(0, len(li) - i - 1): #循环i次之后就还有总长度-1-i次
if li[j] > li[j+1]: #如果低j个数比j+1个数还要大，说明j在j+1的上边
li[j], li[j+1] = li[j+1], li[j] #交换位置
# 优化版，和上边的基本一样，只是在他的基础上增加了一层判断，如果刚刚开始列表就是有序的则不需要进行排序
@cal_time
def bubble_sort_2(li):
for i in range(len(li) - 1):
# i 表示趟数
# 第 i 趟时： 无序区：(0，len(li) - i)
change = False
for j in range(0, len(li) - i - 1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
change = True #排序成功返回True
if not change: #如果没有change的值代表没有排序，
return
li = list(range(10000)) #随机产生10000个数
# random.shuffle(li) #打乱后的结果
# print(li)
bubble_sort_2(li) #没有打乱排序，直接走if not change：
print(li)
选择排序
#选择排序
import random
from timewrap import * #时间装饰器，用来判断函数执行的时间长度
@cal_time
def select_sort(li):
for i in range(len(li) - 1):
# i 表示趟数，也表示无序区开始的位置
min_loc = i # 最小数的位置 的到一个最小值
for j in range(i + 1, len(li)): #此时i就是最小值
if li[j] < li[min_loc]: #如果li[j]<li[min_loc] 说明j就是最小值
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i] #交换位置，最小值放在前边
li = list(range(10000)) #随机产生1000个数字
random.shuffle(li) #打乱
print(li)
select_sort(li) #调用函数，排序
print(li)
插入排序
#插入排序
import random
from timewrap import *
@cal_time
def insert_sort(li):
for i in range(1, len(li)):
# i 表示无序区第一个数
tmp = li[i] # 摸到的牌 随机去到一支歌
j = i - 1 # j 指向有序区最后位置
while li[j] > tmp and j >= 0: # 有序区最下的值
#循环终止条件： 1. li[j] <= tmp; 2. j == -1
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
li = list(range(10000))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)
