python算法-插入排序

插入排序

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

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