算法导论第二章习题解答

def INSERTION_SORT(A, p, r): """ a) k = r - p 执行时间为theta(k*k)， 共执行n/k次， 则有执行时间为theta(nk) """ print(A[p:r]) for j in range(p + 1, r): key = A[j] i = j - 1 while i >= p and A[i] > key: A[i + 1] = A[i] i = i - 1 A[i + 1] = key print(A[p:r]) def MERGE(A, p, q, r): """ b) 每一层的执行时间为cn，共有lg(n/k) + 1层，则执行时间为theta(nlg(n/k)) """ L = A[p:q] L.append(float("inf")) R = A[q:r] R.append(float("inf")) i = 0 j = 0 for k in range(p, r): if L[i] <= R[j]: A[k] = L[i] i = i + 1 else: A[k] = R[j] j = j + 1 def MERGE_INSERTION_SORT(A, p, r, k): """ c)1.分解需要时间theta(1) 2. 分解为n/2的子问题直到问题规模减小到n/k，执行插入排序执行时间为 theta(nk) 3.合并所有子序列，执行时间为theta(nlg(n/k)) 求和则有 theta(nk + nlg(n/k)) 若其等于theta(nlg(n)) 则需使得 k < lg(n) """ assert(k > 0) if r - p > k: q = (p + r) // 2 MERGE_INSERTION_SORT(A, p, q, k) MERGE_INSERTION_SORT(A, q, r, k) MERGE(A, p, q, r) else: print(p, r) INSERTION_SORT(A, p, r) if __name__ == "__main__": """ d)在实际中,在满足插入排序比合并排序更快的情况下，k取最大值。 """ array = [31,41,59,26,41,58,1,20,92,3,98,10,2] print (array) MERGE_INSERTION_SORT(array, 0, len(array), 3) print (array)