[硕.Love Python] InsertionSort(插入排序)

def insertionSort(a):
    for i in xrange(1, len(a)):
 t = a[i]
 for j in xrange(i, 0, -1):
     if a[j-1] <= t:
  break
     a[j] = a[j-1]
 else:
     j = 0
 a[j] = t

def binaryInsertionSort(a):
    for i in xrange(1, len(a)):
 l, r, t = 0, i - 1, a[i]
 while l <= r:
     m = (l + r) / 2
     if t < a[m]:
  r = m - 1
     else:
  l = m + 1

 for j in xrange(i - 1, l - 1, -1):
     a[j+1] = a[j]

 a[l] = t

if __name__ == '__main__':
    from random import shuffle
    data = range(100)

    shuffle(data)
    print data
    insertionSort(data)
    print data

    shuffle(data)
    print data
    binaryInsertionSort(data)
    print data