---

（1）快速排序迭代

    ARTITION(A, p, r)
    x = A[r] // the pivot
    i = p - 1
    for j = p to r - 1
        if A[j] ≤ x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1  // new index of pivot

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[i] with A[r]
    return PARTITION(A, p, r)

RANDOMIZED-SELECT(A, n, i)
    p = 1
    r = n
    q = 0
    k = 0
    while TRUE 
        q = RANDOMIZED-PARTITION(A, p, r);
        k = q - p + 1;
        if i == k 
            return A[q]  // the pivot value is the answer
        elseif i < k
  &n...