一才菠、概念及原理
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法渠欺。它的工作原理是通過構建有序序列虱颗，對于未排序數據，在已排序序列中從后向前掃描聪黎，找到相應位置并插入罕容。插入排序在實現上，在從后向前掃描過程中稿饰，需要反復把已排序元素逐步向后挪位锦秒，為最新元素提供插入空間。
二喉镰、分析以及實現
插入排序主要是將列表分為兩部分旅择，左邊為已經插入排好序的，右邊是待排序的侣姆。每次從右邊依次拿一個到左邊尋找合適的位置插入生真，在左邊（有序序列）尋找合適位置時其實就是一次循環(huán)。
特別注意：因為插入一個元素后捺宗，前面的元素會往后面移動一個位置柱蟀，所以需要比較一次就交換位置
image.png
原理動圖
步驟分析（順序小到大）
1.從第二個位置開始（第一個元素坑定有序對吧），取一個元素
2.和第一個元素比較偿凭，比它大就不變产弹，比它小就交換位置
for i in range(1, len(listA)):
for j in range(i,0,-1):
if listA[j] < listA[j-1]:
listA[j], listA[j-1] = listA[j-1], listA[j]
else:
break
3.循環(huán)到取到最后一個元素為止
def insert_sort(listA):
"""插入排序（逆序）"""
for i in range(1, len(listA)):
for j in range(i,0,-1):
if listA[j] < listA[j-1]:
listA[j], listA[j-1] = listA[j-1], listA[j]
else:
break
return listA
def main():
listA = [2,5,7,4,6,9,1,3,8,7]
insert_sort(listA)
print(insert_sort(listA))
# for li in listA[6::-1]:
# print(li)
if __name__ == '__main__':
main()
