算法导论 - 算法入门 ,一小节（插入排序,复杂度）
>>> arr=[5,2,4,6,1,3]
>>> insertion_sort(arr)
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6]
验证复杂度：
z = 5(n-1)+1+3n(n-1)/2
我们测试数据 为 n=6
当数据极端情况就是需要全部重新排列
就是 [6,5,4,3,2,1] 要排出 [1,2,3,4,5,6] 这样
>> z = 71
一种比较笨的 验证方法 供大家拍砖 :
>>> insertion_sort(arr)
[5, 6, 4, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
[3, 4, 5, 6, 2, 1]
[2, 3, 4, 5, 6, 1]
[1, 2, 3, 4, 5, 6]
---- 71 #复杂度验证为 71
罗嗦下 n(n-1)/2
极端情况下
i=1 ; j 需要挪动 1次
i=2 ; j 挪动 1+2次
i=3 ; j 挪动 1+2+3次
....
i=n ; j 挪动 1+2....+n
我们又找到 (1+n)+(2+n-1)+(3+n-2).... = (1+n)n/2
我们这 的 i 是从 2 次开始的 也就是说 (n-1)n/2 了
本文转自博客园刘凯毅的博客，原文链接：跟我一起学 - 算法导论 - 插入排序，如需转载请自行联系原博主。
#
插入排序 - 复杂度
def insertion_sort(arr): # 1
for j in xrange( 1 ,len(arr) ): # n-1
key = arr[j] # n-1
i = j - 1 # n-1
while i >= 0 and arr[i] > key : # n(n-1)/2
arr[i + 1 ] = arr[i] # n(n-1)/2
i = i - 1 # n(n-1)/2
arr[i + 1 ] = key # n-1
print arr # n-1
验证结果 :
def insertion_sort(arr): # 1
for j in xrange( 1 ,len(arr) ): # n-1
key = arr[j] # n-1
i = j - 1 # n-1
while i >= 0 and arr[i] > key : # n(n-1)/2
arr[i + 1 ] = arr[i] # n(n-1)/2
i = i - 1 # n(n-1)/2
arr[i + 1 ] = key # n-1
print arr # n-1
>>> arr=[5,2,4,6,1,3]
>>> insertion_sort(arr)
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6]
验证复杂度：
z = 5(n-1)+1+3n(n-1)/2
我们测试数据 为 n=6
当数据极端情况就是需要全部重新排列
就是 [6,5,4,3,2,1] 要排出 [1,2,3,4,5,6] 这样
>> z = 71
一种比较笨的 验证方法 供大家拍砖 :
def
insertion_sort(arr):
ii = 0
ii += 1
for j in xrange( 1 ,len(arr) ):
ii += 1
key = arr[j]
ii += 1
i = j - 1
ii += 1
while i >= 0 and arr[i] > key :
ii += 1
arr[i + 1 ] = arr[i]
ii += 1
i = i - 1
ii += 1
arr[i + 1 ] = key
ii += 1
print arr
ii += 1
print " ---- " ,str(ii)
>>> arr=[6,5,4,3,2,1]
ii = 0
ii += 1
for j in xrange( 1 ,len(arr) ):
ii += 1
key = arr[j]
ii += 1
i = j - 1
ii += 1
while i >= 0 and arr[i] > key :
ii += 1
arr[i + 1 ] = arr[i]
ii += 1
i = i - 1
ii += 1
arr[i + 1 ] = key
ii += 1
print arr
ii += 1
print " ---- " ,str(ii)
>>> insertion_sort(arr)
[5, 6, 4, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
[3, 4, 5, 6, 2, 1]
[2, 3, 4, 5, 6, 1]
[1, 2, 3, 4, 5, 6]
---- 71 #复杂度验证为 71
罗嗦下 n(n-1)/2
极端情况下
i=1 ; j 需要挪动 1次
i=2 ; j 挪动 1+2次
i=3 ; j 挪动 1+2+3次
....
i=n ; j 挪动 1+2....+n
我们又找到 (1+n)+(2+n-1)+(3+n-2).... = (1+n)n/2
我们这 的 i 是从 2 次开始的 也就是说 (n-1)n/2 了
def
tn(ii):
ti = 0
for i in xrange(ii) :
for j in xrange(i) :
ti += 1
print ti
print tn( 2 ) # 1 = 1
print tn( 3 ) # 3 = 1+2
print tn( 4 ) # 6 = 1+2+3
..
ti = 0
for i in xrange(ii) :
for j in xrange(i) :
ti += 1
print ti
print tn( 2 ) # 1 = 1
print tn( 3 ) # 3 = 1+2
print tn( 4 ) # 6 = 1+2+3
..
本文转自博客园刘凯毅的博客，原文链接：跟我一起学 - 算法导论 - 插入排序，如需转载请自行联系原博主。
