Python编程:排序算法之插入排序

插入排序

列表被分为有序区和无序区两个部分,最初有序区只有一个元素

每次从无序区选择一个元素,插入到有序区的位置,直到无需去变空

代码实现

# -*- coding: utf-8 -*-
# 4;File : insert_sort_demo.py
# 4;Date : 2018-06-11
import random
# 插入排序 O(n^2)
def insert_sort(lst):
count = 0
for i in range(1, len(lst)):
tmp = lst[i]
j = i - 1
while j >=0 and tmp < lst[j]:
lst[j+1] = lst[j]
j -= 1
count += 1
lst[j+1] = tmp
print("count: %s"% count)
lst = list(range(10))
random.shuffle(lst)
insert_sort(lst)
print(lst)
# count: 20
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]