插入排序
一、核心思想：在一个有序的数组中，通过逐一和前面的数进行比较，找到新数的位置。
例子：数组有有一个数21
插入一个3，3<21，因此结果为 3,21
再插入一个34,34>21,因此结果为 3,21,34
再插入一个6,34>6,向前移动，21>6,再向前移动，3<6,因此结果为 3,6,21,34
问题1：对于一个有n个数的数组，需要插入多少次，才能完成插入排序？
N-1次
二、核心代码：
def Insert_Sort(lista):
for i in xrange(1,len(lista)): #用i控制从第二个数字开始到最后一个数字的下标
j = i -1 #用j去控制i前面一个数和i做比较
while j >= 0: #j<0是一种退出循环的判定条件
if lista[j] > lista[j+1]: #如果前数大于后数，就交换位置
lista[j],lista[j+1] = lista[j+1],lista[j]
j -= 1 #j依次减一，去跟前面的值作比较
else:
break #只要出现一个j>j+1，交换后就跳出本次循环即可
return lista
if __name__ == '__main__':
print Insert_Sort([2,15,6,29,0])
三、时间复杂度：
最差的比较情况 1+2+...... +n-2 + n-1 = n(n-1)/2 n^2/2
最好的比较情况 n-1 ............ 恰好都在对应的位置
平均的情况就是 [n(n-1)/2 + (n-1)]/2 = n^2/4
最后的结果就是O(n^2)