python算法-插入排序

时间:2024-08-10 14:03:26

插入排序

一、核心思想:在一个有序的数组中,通过逐一和前面的数进行比较,找到新数的位置。

例子:数组有有一个数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)