算法分析--顺序统计量

Minimum and maximum 最小值和最大值

最小值 Minimum

Minimum(A,n)
    mim = A[1]
    for i = 2 to n
        if A[i] < mim
            mim = A[i]
    return min

最大值 Maximum

Maximum(A,n)
    max = A[1]
    for i = 2 to n
        if A[i] > max
            max = A[i]
    return max

同时搜索最大最小值

MINIMUM-AND-MAXIMUM(A,n)
    max = A[1]
    min = A[1]
    for i = 2 to n
        if A[i] > max
            max = A[i]
        if A[i] < mim
            mim = A[i]
    return min and max

找出中位数 Median

很多分治策略中都可以使用中位数而不需要排序。

MEDIAN-SELECT(A)
    Sort the array A
    if n is odd:
        return A[(n // 2)]
    else
        return (A[(n // 2) - 1] + A[(n // 2)]) / 2

顺序统计量

RANDOMIZED-SELECT 随机选择算法（线性时间）

找出第i个顺序统计量,找出数组A[p:r ]中第i小的元素 平均情况下为 $O(lgn)$ ,最坏情况为 $O(n^2)$ ,期望运行时间 $O(n)$

RANDOMIZED-SELECT(A,p,r,i)
    if p == r 
        return A[p]
    q = Rand-Partitian(A,p,r) 
    k = q - p + 1 
    if i == k
        return A[q]  
    else if i < k
        return RANDOMIZED-SELECT(A, p, q - 1, i)
    else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

//迭代版
RANDOMIZED-SELECT(A, p, r, i)
    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
            r = q - 1
        else p = q + 1
            i = i - k