跟我一起學 - 算法導論 - 插入排序

算法導論 - 算法入門 ,一小節（插入排序,複雜度）

#  插入排序                -         複雜度

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]

[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]            

        i=j-1                

        while i>=0 and arr[i]> key :    

            ii+=1

            arr[i+1] = arr[i]    

            i=i-1            

        arr[i+1] = key            

        print arr            

    print "----",str(ii)

>>> arr=[6,5,4,3,2,1]

[5, 6, 4, 3, 2, 1]

[4, 5, 6, 3, 2, 1]

[3, 4, 5, 6, 2, 1]

[2, 3, 4, 5, 6, 1]

---- 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

..