Algorithms

  1 Insertion Sort - 插入排序
  2     插入排序算法的 '时间复杂度' 是输入规模的二次函数, 深度抽象后表示为, n 的二次方.
  3 
  4 import time, random
  5 F = 0
  6 alist = []
  7 while F < 13:
  8     F += 1
  9     alist.append(random.randrange(0,100))
 10 j =1
 11 print("List-O",alist)
 12 startT =time.time()
 13 while j < alist.__len__():
 14     factor = alist[j]
 15     j += 1
 16     print("-",factor)
 17     i = j -1
 18     while i > 0:
 19         i -= 1
 20         if alist[i] > factor:
 21             alist[i],alist[i+1] = alist[i+1],alist[i]
 22         print("Steps", alist)
 23 endT = time.time()
 24 print("List-S", alist)
 25 print("Time elapsed :", endT - startT)
 26 
 27 Output,
 28 List-O [67, 22, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 29 - 22
 30 Steps [22, 67, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 31 - 94
 32 Steps [22, 67, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 33 Steps [22, 67, 94, 33, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 34 - 33
 35 Steps [22, 67, 33, 94, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 36 Steps [22, 33, 67, 94, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 37 Steps [22, 33, 67, 94, 81, 92, 65, 94, 56, 10, 55, 5, 64]
 38 - 81
 39 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]
 40 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]
 41 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]
 42 Steps [22, 33, 67, 81, 94, 92, 65, 94, 56, 10, 55, 5, 64]
 43 - 92
 44 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]
 45 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]
 46 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]
 47 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]
 48 Steps [22, 33, 67, 81, 92, 94, 65, 94, 56, 10, 55, 5, 64]
 49 - 65
 50 Steps [22, 33, 67, 81, 92, 65, 94, 94, 56, 10, 55, 5, 64]
 51 Steps [22, 33, 67, 81, 65, 92, 94, 94, 56, 10, 55, 5, 64]
 52 Steps [22, 33, 67, 65, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 53 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 54 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 55 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 56 - 94
 57 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 58 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 59 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 60 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 61 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 62 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 63 Steps [22, 33, 65, 67, 81, 92, 94, 94, 56, 10, 55, 5, 64]
 64 - 56
 65 Steps [22, 33, 65, 67, 81, 92, 94, 56, 94, 10, 55, 5, 64]
 66 Steps [22, 33, 65, 67, 81, 92, 56, 94, 94, 10, 55, 5, 64]
 67 Steps [22, 33, 65, 67, 81, 56, 92, 94, 94, 10, 55, 5, 64]
 68 Steps [22, 33, 65, 67, 56, 81, 92, 94, 94, 10, 55, 5, 64]
 69 Steps [22, 33, 65, 56, 67, 81, 92, 94, 94, 10, 55, 5, 64]
 70 Steps [22, 33, 56, 65, 67, 81, 92, 94, 94, 10, 55, 5, 64]
 71 Steps [22, 33, 56, 65, 67, 81, 92, 94, 94, 10, 55, 5, 64]
 72 Steps [22, 33, 56, 65, 67, 81, 92, 94, 94, 10, 55, 5, 64]
 73 - 10
 74 Steps [22, 33, 56, 65, 67, 81, 92, 94, 10, 94, 55, 5, 64]
 75 Steps [22, 33, 56, 65, 67, 81, 92, 10, 94, 94, 55, 5, 64]
 76 Steps [22, 33, 56, 65, 67, 81, 10, 92, 94, 94, 55, 5, 64]
 77 Steps [22, 33, 56, 65, 67, 10, 81, 92, 94, 94, 55, 5, 64]
 78 Steps [22, 33, 56, 65, 10, 67, 81, 92, 94, 94, 55, 5, 64]
 79 Steps [22, 33, 56, 10, 65, 67, 81, 92, 94, 94, 55, 5, 64]
 80 Steps [22, 33, 10, 56, 65, 67, 81, 92, 94, 94, 55, 5, 64]
 81 Steps [22, 10, 33, 56, 65, 67, 81, 92, 94, 94, 55, 5, 64]
 82 Steps [10, 22, 33, 56, 65, 67, 81, 92, 94, 94, 55, 5, 64]
 83 - 55
 84 Steps [10, 22, 33, 56, 65, 67, 81, 92, 94, 55, 94, 5, 64]
 85 Steps [10, 22, 33, 56, 65, 67, 81, 92, 55, 94, 94, 5, 64]
 86 Steps [10, 22, 33, 56, 65, 67, 81, 55, 92, 94, 94, 5, 64]
 87 Steps [10, 22, 33, 56, 65, 67, 55, 81, 92, 94, 94, 5, 64]
 88 Steps [10, 22, 33, 56, 65, 55, 67, 81, 92, 94, 94, 5, 64]
 89 Steps [10, 22, 33, 56, 55, 65, 67, 81, 92, 94, 94, 5, 64]
 90 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]
 91 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]
 92 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]
 93 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 5, 64]
 94 - 5
 95 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 5, 94, 64]
 96 Steps [10, 22, 33, 55, 56, 65, 67, 81, 92, 5, 94, 94, 64]
 97 Steps [10, 22, 33, 55, 56, 65, 67, 81, 5, 92, 94, 94, 64]
 98 Steps [10, 22, 33, 55, 56, 65, 67, 5, 81, 92, 94, 94, 64]
 99 Steps [10, 22, 33, 55, 56, 65, 5, 67, 81, 92, 94, 94, 64]
100 Steps [10, 22, 33, 55, 56, 5, 65, 67, 81, 92, 94, 94, 64]
101 Steps [10, 22, 33, 55, 5, 56, 65, 67, 81, 92, 94, 94, 64]
102 Steps [10, 22, 33, 5, 55, 56, 65, 67, 81, 92, 94, 94, 64]
103 Steps [10, 22, 5, 33, 55, 56, 65, 67, 81, 92, 94, 94, 64]
104 Steps [10, 5, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 64]
105 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 94, 64]
106 - 64
107 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 92, 94, 64, 94]
108 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 92, 64, 94, 94]
109 Steps [5, 10, 22, 33, 55, 56, 65, 67, 81, 64, 92, 94, 94]
110 Steps [5, 10, 22, 33, 55, 56, 65, 67, 64, 81, 92, 94, 94]
111 Steps [5, 10, 22, 33, 55, 56, 65, 64, 67, 81, 92, 94, 94]
112 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
113 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
114 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
115 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
116 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
117 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
118 Steps [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
119 List-S [5, 10, 22, 33, 55, 56, 64, 65, 67, 81, 92, 94, 94]
120 Time elapsed : 0.015672683715820312
121