插入排序
插入排序是一種簡單直觀的排序算法恨樟。它的工作原理是通過構(gòu)建有序序列，對于未排序的數(shù)據(jù)缩多，在已排序序列中從后向前掃描，找到對應(yīng)位置并插入衬吆。插入排序在實現(xiàn)上，在從后向前掃描過程中陈轿，需要反復(fù)把已排序元素逐步向后挪動秦忿，為新元素提供插入空間蛾娶。
代碼
def insert_sort(list):
#從第二個位置，即下標為1的元素開始向前插入
for i in range(1,len(list)):
#從第i個元素開始向前比較蛔琅，如果小于前一個元素，交換位置
for j in range(i,0,-1):
if list[j]<list[j-1]:
list[j],list[j-1]=list[j-1],list[j]
list=[2,6,3,1,5,8,9,4,7,10]
print(list)
insert_sort(list)
print(list)
時間復(fù)雜度
- 最優(yōu)時間復(fù)雜度：O(n) （升序排列辜窑，序列已經(jīng)處于升序狀態(tài) ）
- 最壞時間復(fù)雜度：O(n^2)
- 穩(wěn)定性：穩(wěn)定
插入排序分析
插入排序分析
參考：數(shù)據(jù)結(jié)構(gòu)與算法（python語言描述）
