算法导论第七章习题解答

import random def RANDOMIZED_PARTITION(A, p, r): i = random.randint(p, r) temp = A[i] A[i] = A[r] A[r] = temp return PARTITION(A, p, r) def RANDOMIZED_QUICKSORT(A, p, r): if p < r: q = RANDOMIZED_PARTITION(A, p, r) RANDOMIZED_QUICKSORT(A, p, q-1) RANDOMIZED_QUICKSORT(A, q+1, r) def QUICKSORT(A, p, r): if p < r: q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r) def PARTITION(A, p, r): """ a) 当所有元素都相同时，p = r 有T(n) = T(n - 1) + theta(n) """ x = A[r] i = p for j in range(p, r): if A[j] <= x: temp = A[i] A[i] = A[j] A[j] = temp i = i + 1 temp = A[i] A[i] = A[r] A[r] = temp return i def QUICKSORT1(A, p, r): """ d) """ if p < r: q,t = PARTITION1(A, p, r) QUICKSORT1(A, p, t-1) QUICKSORT1(A, q+1, r) def PARTITION1(A, p, r): """ b) 去掉注释的内容 """ x = A[r] i = p t = 0 for j in range(p, r): #print(" < ", A[p:t]) #print(" = ", A[t: i]) #print(" > ", A[i:j]) #print(" ", A[j:r]) if A[j] == x: temp = A[i] A[i] = A[j] A[j] = temp i = i + 1 elif A[j] < x: cur = A[j] begin = A[p+t] end = A[i] A[i] = x A[p+t] = cur A[j] = end i = i + 1 t = t + 1 temp = A[i] A[i] = A[r] A[r] = temp return i, p+t def RANDOMIZED_PARTITION1(A, p, r): """ c1) """ i = random.randint(p, r) temp = A[i] A[i] = A[r] A[r] = temp return PARTITION1(A, p, r) def RANDOMIZED_QUICKSORT1(A, p, r): """ c2) """ if p < r: q,t = RANDOMIZED_PARTITION1(A, p, r) RANDOMIZED_QUICKSORT1(A, p, t-1) RANDOMIZED_QUICKSORT1(A, q+1, r) if __name__ == "__main__": array = [9,9,0,0,9,9,9,10,2,7,3,0,17,42,19,9,0,0,0,79,9,9,9] print(array) QUICKSORT1(array, 0, len(array)-1) print(array)