插入排序分析
輸入： 長(zhǎng)度為length的無序列表
返回值： 按照升序排好序的數(shù)組
插入排序的基本原理梦鉴，是從第2項(xiàng)開始遍歷到最后一項(xiàng)，每次遍歷的起始項(xiàng)之前是一個(gè)排好序的列表魏宽，在第n次遍歷的時(shí)候塔插，在排序好的長(zhǎng)度n列表中找到正確的位置，將第n個(gè)元素插入扳抽，得到一個(gè)長(zhǎng)度為n+1的數(shù)組，接著開始n+1次遍歷殖侵。
圖解
例： [4, 9, 3, 5, 0, 2]
插入排序圖示
代碼實(shí)現(xiàn)
def insert_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
if __name__ == '__main__':
arr = [4, 9, 3, 5, 0, 2]
insert_sort(arr)
print(arr)
在Python中贸呢，List是可變類型，所以上述函數(shù)的寫法將會(huì)在列表的原處改動(dòng)拢军，如果不希望改動(dòng)楞陷，可以使用深拷貝將列表復(fù)制后排序，或?qū)⒃靥砑拥叫碌牧斜怼?/p>
