lowb三人組
- 冒泡
- 選擇
- 插入
- 算法關(guān)鍵點：有序區(qū)扶平，無序區(qū)
冒泡：
- 首先，列表每兩個相鄰的數(shù)蔬蕊，如果前面的比后面的大结澄，那么交換這兩個數(shù)。
- 關(guān)鍵點：趟，無序區(qū)
# 如果冒泡排序中麻献，執(zhí)行了一趟而沒有交換位置们妥，那么它已經(jīng)是有序狀態(tài)，可以直接結(jié)束算法赎瑰。
def bubble_sort(li):
for i in range(len(li)-1):
# i代表趟
# 第 i 趟時：無序區(qū)range(len(li)-i)
# 因為最后一個是固定的不需要再比較再挪動so -1
flag = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
flag = True
if not flag:
return
選擇：
- 在一堆大小不一的球中王悍，進行選擇(以從小到大，先選最小球為例)餐曼。
- 選擇一個基準(zhǔn)球压储。
- 將剩下的球與基準(zhǔn)球比較如果小于基準(zhǔn)求，則交換位置源譬。
- 第一輪過后集惋，獲得最小的球。
- 執(zhí)行123步踩娘。
時間復(fù)雜度：O(n^2). 需要進行的比較次數(shù)為第一輪 n-1刮刑，n-2....1, 總的比較次數(shù)為 n*(n-1)/2
# 與冒泡只有一點點差別
import random
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)-i-1):
if li[j] > li[min_loc]:
min_loc = j
else:
li[i],li[min_loc] = li[min_loc],li[i]
插入
- 思路：
- 列表被分為有序區(qū)和無序區(qū)兩個部分。最初有序區(qū)只有一個元素养渴。
- 每次從無序區(qū)拿出一個元素雷绢，插入到有序區(qū)的位置，直到無序區(qū)變空理卑。
- 在有序區(qū)翘紊，它也會依次去比較，把最小的排在最前面位置藐唠。
- 時間復(fù)雜度:
o(n^2)
# 思路：列表被分為有序去和無序區(qū)帆疟。最初有序區(qū)只有一個元素。
# 每次從無序區(qū)選擇一個元素宇立，插入到有序區(qū)的位置踪宠，直到無序區(qū)變空。
from timewrap import exe_time
import random
@exe_time
def insert_sort(li):
for i in range(1,len(li)):
# i 是無序區(qū)第一張牌妈嘹，默認(rèn)0位有序
tmp = li[i] # tmp就是無序區(qū)的第一個元素,即摸到的牌
j = i - 1 # 有序區(qū)的最后一個元素的索引
while j >= 0 and tmp < li[j]:
# j >= 0 如果沒有這句柳琢，index 會 outof。
# 因為我要把最小的值放在最前面蟋滴，它是通過和前面一個值比較來的位置染厅。
# 但是第一個元素前面沒有值了，所以只能通過判斷來讓最小的值放在索引為0的位置上津函。
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
# n 是我拿到的值肖粮，
# J 是n前面的一個值，就是要比的值尔苦。
# 其實你看似放在某某前面涩馆，但其實是放在某某某的后面行施。
li = list(range(100))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)
到這，排序lowB三人組完結(jié)魂那。????????????
