插入排序
列表被分为有序区和无序区两个部分，最初有序区只有一个元素
每次从无序区选择一个元素，插入到有序区的位置，直到无需去变空

代码实现

# -*- 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]
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/80659414