插入排序（Insertion sort）

插入排序（Insertion sort）是一种简单直观且稳定的排序算法

算法原理：

它的原理是 每插入一个数 都要将它 和 之前的 已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O（n²）。 这种算法是稳定的排序方法。

举例：

　　　　　　第一趟排序：取出第2个数据10，与第1个数据排序 　　 　 [1,10 | 35,61,89,36,55]

　　　　　　第二趟排序：取出第3个数据35，与前2数据排序 　　 [1,10, 35 | 61,89,36,55]

　　　　　　第三趟排序：取出第4个数据61，与第3个数据排序 　 [1,10,35,61 | 89,36,55]

　　　　　　第四趟排序：取出第5个数据89，与第4个数据排序　 [1,10,35,61,89 | 36,55]

　　　　　 第五趟排序：取出第6个数据36，与第5个数据排序　　　 [1,10,35,36, 61,89 | 55]

　　　　　　第六趟排序：取出第7个数据55，与第6个数据排序　　　 [1,10,35,36,55,61,89]

　　　　　　第一趟总共进行了六次比较，排序结果： [1,10,35,36,55,61,89]

代码：

def insert_sort(list):
  for i in range(1,Length):                   #默认第一个元素已经在有序序列中，从后面元素开始插入    
      for j in range(i,0,-1):                 #逆向遍历比较，交换位置实现插入        
          if list[j] < list[j-1]:            
              list[j],list[j-1] = list[j-1],list[j]
print('after sort:',list)