Insertion Sort - 插入排序

     插入排序算法的 '时间复杂度' 是输入规模的二次函数, 深度抽象后表示为, n 的二次方.

 import time, random

 F = 0

 alist = []

 while F < 13:

     F += 1

     alist.append(random.randrange(0,100))

 j =1

 print("List-O",alist)

 startT =time.time()

 while j < alist.__len__():

     factor = alist[j]

     j += 1

     print("-",factor)

     i = j -1

     while i > 0:

         i -= 1

         if alist[i] > factor:

             alist[i],alist[i+1] = alist[i+1],alist[i]

         print("Steps", alist)

 endT = time.time()

 print("List-S", alist)

 print("Time elapsed :", endT - startT)

 Output,

 List-O [67, 22, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 - 22

 Steps [22, 67, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 - 94

 Steps [22, 67, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 67, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 - 33

 Steps [22, 67, 33, 94, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 94, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 94, 81, 92, 65, 94, 56, 10, 55, 5, 64]

 - 81

 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]

 - 92

 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]

 - 65

 Steps [22, 33, 67, 81, 92, 65, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 81, 65, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 67, 65, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 - 94

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]

 - 56

 Steps [22, 33, 65, 67, 81, 92, 94, 56, 94, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 92, 56, 94, 94, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 81, 56, 92, 94, 94, 10, 55, 5, 64]

 Steps [22, 33, 65, 67, 56, 81, 92, 94, 94, 10, 55, 5, 64]

 Steps [22, 33, 65, 56, 67, 81, 92, 94, 94, 10, 55, 5, 64]

 Steps [22, 33, 56, 65, 67, 81, 92, 94, 94, 10, 55, 5, 64]

 Steps [22, 33, 56, 65, 67, 81, 92, 94, 94, 10, 55, 5, 64]

 Steps [22, 33, 56, 65, 67, 81, 92, 94, 94, 10, 55, 5, 64]

 - 10

 Steps [22, 33, 56, 65, 67, 81, 92, 94, 10, 94, 55, 5, 64]

 Steps [22, 33, 56, 65, 67, 81, 92, 10, 94, 94, 55, 5, 64]

 Steps [22, 33, 56, 65, 67, 81, 10, 92, 94, 94, 55, 5, 64]

 Steps [22, 33, 56, 65, 67, 10, 81, 92, 94, 94, 55, 5, 64]

 Steps [22, 33, 56, 65, 10, 67, 81, 92, 94, 94, 55, 5, 64]

 Steps [22, 33, 56, 10, 65, 67, 81, 92, 94, 94, 55, 5, 64]

 Steps [22, 33, 10, 56, 65, 67, 81, 92, 94, 94, 55, 5, 64]

 Steps [22, 10, 33, 56, 65, 67, 81, 92, 94, 94, 55, 5, 64]

 Steps [10, 22, 33, 56, 65, 67, 81, 92, 94, 94, 55, 5, 64]

 - 55

 Steps [10, 22, 33, 56, 65, 67, 81, 92, 94, 55, 94, 5, 64]

 Steps [10, 22, 33, 56, 65, 67, 81, 92, 55, 94, 94, 5, 64]

 Steps [10, 22, 33, 56, 65, 67, 81, 55, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 56, 65, 67, 55, 81, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 56, 65, 55, 67, 81, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 56, 55, 65, 67, 81, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]

 - 5

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 5, 94, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 5, 94, 94, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 81, 5, 92, 94, 94, 64]

 Steps [10, 22, 33, 55, 56, 65, 67, 5, 81, 92, 94, 94, 64]

 Steps [10, 22, 33, 55, 56, 65, 5, 67, 81, 92, 94, 94, 64]

 Steps [10, 22, 33, 55, 56, 5, 65, 67, 81, 92, 94, 94, 64]

 Steps [10, 22, 33, 55, 5, 56, 65, 67, 81, 92, 94, 94, 64]

 Steps [10, 22, 33, 5, 55, 56, 65, 67, 81, 92, 94, 94, 64]

 Steps [10, 22, 5, 33, 55, 56, 65, 67, 81, 92, 94, 94, 64]

 Steps [10, 5, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 64]

 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 64]

 - 64

 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 64, 94]

 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 92, 64, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 64, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 65, 67, 64, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 65, 64, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 List-S [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]

 Time elapsed : 0.015672683715820312