if

 a[i]>a[i+1]:

                

a[i],a[i+1]=a[i+1],a[i]

　　
 
【插入排序】
 
复杂度是

n*n

 
#coding:utf8
#author:HaxtraZ
 
 
def insertion_sort1(a):
#线性插入排序

    

for

 j in range(1, len(a)):

        

key = a[j]

        

i = j - 1

        

while

 i>=0 

and

 a[i]>key:

            

a[i+1] = a[i]

            

i = i-1

        

a[i+1] = key

 
def binInsertSort(a):
#二分插入排序

    

n = len(a)

    

for

 j in range(1, n):

        

key = a[j]

        

i = j - 1

 

        

if

 key > a[i]:

            

continue

        

l, r = 0, i

        

while

 l <= r:

            

#

print

 l, r

            

mid = (l + r) / 2

            

if

 key < a[mid]:

                

r = mid - 1

            

else

:

                

l = mid + 1

        

k = j

        

while

 k > l:

            

a[k] = a[k - 1]

            

k = k - 1