插入排序
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列鞍爱，對于未排序數(shù)據(jù)伊约，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上尤蛮，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位斯议，為最新元素提供插入空間产捞。
插入排序分析
day27_排序與搜索-01.png
day27_排序與搜索-02.gif
def insert_sort(alist):
# 從第二個(gè)位置，即下標(biāo)為1的元素開始向前插入
for i in range(1, len(alist)):
# 從第i個(gè)元素開始向前比較哼御，如果小于前一個(gè)元素坯临，交換位置
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)
時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
- 最壞時(shí)間復(fù)雜度：O(n2)
- 穩(wěn)定性：穩(wěn)定
插入排序演示
day27_排序與搜索-03.gif
