2019-05-15

书323 页，要求写一个 插入排序，假设右端是排好序的。

借鉴左边，写了右边的代码，注意边界
python 2.7 环境下，

lla =[1,2,4,6,7,3,8,3,9]

lla2 =[8,2,4,6,7,3,8,3,9,1,3,2,5,6,7,5]

list3=[1,8,7,6,5,4,3,2,1,7]

#insert from the left to the right 
def insert_sort(lst):
    for i in range (1,len(lst)):
        x=lst[i]
        j=i
        while (j>0 and lst[j-1]>x):
            lst[j]=lst[j-1]
            j-=1
        lst[j]=x

insert_sort(lla)
print lla

print "this is another way to sort the list"

# from the right to the left ,one by one 
def insert_sort2(lst):
    
    llen =len(lst) -1  # the limit 
    for i in range (llen,-1,-1):
        
        print i #check the limit
        x=lst[i]
        j=i
        while (j< llen and lst[j+1]<x):
            #print "oooo"
            lst[j]=lst[j+1]
            j+=1
        lst[j]=x

insert_sort2(list3)
print list3

结果

[1, 2, 3, 3, 4, 6, 7, 8, 9]
this is another way to sort the list
9
8
7
6
5
4
3
2
1
0
[1, 1, 2, 3, 4, 5, 6, 7, 7, 8]

仅供参考。