感觉作业越来越难了，每天花的时间越来越多了。 改用Python写代码，没有在用伪代码了。

2.3-1

2.3-1.PNG

2.3-2

def Merge(A, p, q, r):
    L = A[p:q+1]
    R = A[q+1:r+1]

    i = 0
    j = 0
    
    for k in range(p, r+1):
        if i >= len(L):
            A[k:r+1] = R[j:r+1]
            return A
        
        elif j >= len(R):
            A[k:r+1] = L[i:q+1]
            return A
            
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1

        else:
            A[k] = R[j]
            j += 1

def Merge_sort(A, p, r):
    if p < r:
        q = int((p + r)/2)
        Merge_sort(A, p, q)
        Merge_sort(A, q+1, r)
        Merge(A, p, q, r)


A = [3, 41, 52, 26, 38, 57, 9, 49]
print('Before sort:', A)
Merge_sort(A, 0, len(A)-1)
print('After sort:', A)

2.3-3

当k>1, T(n) = 2T(n/2) + n = 2x(2xT(n/4) + n) + n = 2^2xT(n/4) + 2n + n = ...
T(n) = 2^(k - 1)xT(2) + 2^kxn + 2^(k-1)xn + ... + n
=n(2^(k - 1) + 2^(k - 2) + ... + 2 + 1)
=nlgn

2.3-4

def Insert_Sort(A, q):
    if q > 1:
        Insert_Sort(A, q-1)
        MyInsert(A, q)

def MyInsert(A, q):
    key = A[q+1]
    j = q
    while j >= 0 and A[j] >= key:
        A[j+1] = A[j]
        j = j - 1

    A[j+1] = key

A = [3, 41, 52, 26, 38, 57, 9, 49]
print('Before sort:', A)
Insert_Sort(A, len(A)-2)
print('After sort:', A)