# -*- coding: utf-8 -*-
# @File    : insert_sort_demo.py
# @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]