插入排序分析
输入： 长度为length的无序列表
返回值： 按照升序排好序的数组
插入排序的基本原理，是从第2项开始遍历到最后一项，每次遍历的起始项之前是一个排好序的列表，在第n次遍历的时候，在排序好的长度n列表中找到正确的位置，将第n个元素插入，得到一个长度为n+1的数组，接着开始n+1次遍历。
图解
例： [4, 9, 3, 5, 0, 2]
插入排序图示
代码实现
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是可变类型，所以上述函数的写法将会在列表的原处改动，如果不希望改动，可以使用深拷贝将列表复制后排序，或将元素添加到新的列表。
网友评论