時間復(fù)雜度
時間復(fù)雜度是用來估計算法運(yùn)行時間的式子（單位）。
image.png
時間復(fù)雜度小結(jié)
image.png
空間復(fù)雜度
用來計算一個算法臨時占用內(nèi)存的式子
遞歸復(fù)習(xí)
1、調(diào)用自身
2、結(jié)束條件
lowB三人組
冒泡排序
冒泡排序：列表在內(nèi)存重只存一份，所以不需要重復(fù)賦值
import random
from timewrap import * #時間裝飾器
# 初級版本
@cal_time
def bubble_sort(li):
for i in range(len(li) - 1): #循環(huán)的躺數(shù)為總的躺數(shù)-1，因為最后一步?jīng)]必要走
# i 表示趟數(shù)
# 第 i 趟時： 無序區(qū)：(0，len(li) - i)
for j in range(0, len(li) - i - 1): #循環(huán)i次之后就還有總長度-1-i次
if li[j] > li[j+1]: #如果低j個數(shù)比j+1個數(shù)還要大，說明j在j+1的上邊
li[j], li[j+1] = li[j+1], li[j] #交換位置
# 優(yōu)化版，和上邊的基本一樣，只是在他的基礎(chǔ)上增加了一層判斷，如果剛剛開始列表就是有序的則不需要進(jìn)行排序
@cal_time
def bubble_sort_2(li):
for i in range(len(li) - 1):
# i 表示趟數(shù)
# 第 i 趟時： 無序區(qū)：(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)) #隨機(jī)產(chǎn)生10000個數(shù)
# random.shuffle(li) #打亂后的結(jié)果
# print(li)
bubble_sort_2(li) #沒有打亂排序，直接走if not change：
print(li)
選擇排序
#選擇排序
import random
from timewrap import * #時間裝飾器，用來判斷函數(shù)執(zhí)行的時間長度
@cal_time
def select_sort(li):
for i in range(len(li) - 1):
# i 表示趟數(shù)，也表示無序區(qū)開始的位置
min_loc = i # 最小數(shù)的位置 的到一個最小值
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)) #隨機(jī)產(chǎn)生1000個數(shù)字
random.shuffle(li) #打亂
print(li)
select_sort(li) #調(diào)用函數(shù)，排序
print(li)
插入排序
#插入排序
import random
from timewrap import *
@cal_time
def insert_sort(li):
for i in range(1, len(li)):
# i 表示無序區(qū)第一個數(shù)
tmp = li[i] # 摸到的牌 隨機(jī)去到一支歌
j = i - 1 # j 指向有序區(qū)最后位置
while li[j] > tmp and j >= 0: # 有序區(qū)最下的值
#循環(huán)終止條件： 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)
