chap9 中位数和顺序统计量

选择算法 顺序统计量 算法导论

内容

期望为线性时间的选择算法

1. 利用了快速排序算法的思想，只不过这里不需要进行全排序，只需要找到第i小的数，因而每轮递归只需要进入一个分支，因而算法期望时间为$\Theta(n)$
2. 适用于元素各异的情形
3. 伪代码：

Randomized-Select(A,p,r,i)

if p == r
    return A[p]
q = Randomized-Partiton(A,p,r)
k = q - p + 1
if i == k
    return A[q]
else if i < k
    return Randomized-Partition(A,p,q-1,i)
esle return Randomized-Partition(A,q+1,r,i-k)

最坏情形为线性时间的选择算法

1. 思想还是快排的思想，和上一个选择算法不同的是，这里对主元的选择进行了规定，代替了上一个算法中的随机选择
2. 过程：
   
   1. Divide the n elements of the input array into $\lfloor n=5 \rfloor$ groups of 5 elements each
      and at most one group made up of the remaining n mod 5 elements.
   2. Find the median of each of the $\lfloor n=5 \rfloor$ groups by first insertion-sorting the elements of each group (of which there are at most 5) and then picking themedian from the sorted list of group elements.
   3. Use SELECT recursively to find the median x of the $\lfloor n=5 \rfloor$ medians found in step 2. (If there are an even number of medians, then by our convention, x is the lower median.)
   4. Partition the input array around the median-of-medians x using the modified
      version of PARTITION. Let k be one more than the number of elements on the low side of the partition, so that x is the kth smallest element and there are n-k elements on the high side of the partition.
   5. If $i = k$, then return x. Otherwise, use SELECT recursively to find the $i$ th smallest element on the low side if $i < k$, or the $(i - k)$th smallest element on the high side if $i > k$.

习题中的算法

9.3-8 寻找两个有序数组的中位数

1. 问题：Let $X[1...n]$ and $Y[1...n]$ be two arrays, each containing n numbers already in sorted order. Give an$O(\lg n)$-time algorithm to find the median of all 2n elements in arrays $X$ and $Y$
2. 基本思路：假设中位数位于X，则选取A的中位数m，并判断B中有多少个数比m小，如果加起来恰好为n，就找到了；否则根据多余n还是小于n，进入不同的分支迭代；
3. 伪代码：

--

Two-Array-Median(X,Y)
n = X.length
median = Find-Median(X,Y,n,1,n)
if median == not_found
    median = Find-Median(Y,X,n,1,n)
return median

Find-Median(X,Y,n,low,high)
if low > high
    return not_found
else k = (low+high)/2 #向下取整
    if k == n and A[n] <= B[1]
        return A[n]
    else if k < n and B[n-k] <= A[k] <= B[n-k+1]
        return A[k]
    else if A[k] > B[n-k+1]
        return Find-Median(X,Y,n,low,k-1)
    else return Find-Median(X,Y,n,k+1,high)

9-2 带权中位数和邮局位置问题

1. 时间为$\Theta(n)$

Weighted-Median(X)

if n == 1
    return x1
else if n == 2
    if w1 >= w2
        return x1
    else return x2
else find the median xk of X
    partition X around xk
    WL = the sum of weights whose element is less than xk
    WG = the sum of weights whose element is greater than xk
    if WL < 1/2 and WG < 1/2
        return xk
    else if WL > 1/2
        wk = wk + WG
        X' = {x belong to X where x <= xk}
        return Weighted-Median(X')
    ekse wk = wk + WL
        X' = {x belong to X where x >= xk}
        return Weighted-Median(X')

代码实现

java