9 Medians and Order Statistics

未分类

前提：每一个数都不一样
最大最小中位数
加入lower median和upper median，取下界上界之分

9.1 Minimum and maximum

常规算法：使用这种算法同时找到最大最小值每个元素比较两次

int minmum(int A[],int length){
    min=A[0];
    for(int i=1;i<length;i++){
        if(min>A[i]) min=A[i];
    }
    return min;
}

We compare pairs of elements from the input first
with each other, and then we compare the smaller with the current minimum and
the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
这样只要3[n/2] (取下界)

9.1-1

Show that the second smallest of n elements can be found with n C dlg ne  2
comparisons in the worst case. (Hint: Also find the smallest element.)

9.1-2 ?

Prove the lower bound of d3n=2e  2 comparisons in the worst ca
se to find both
the maximum and minimum of n numbers. (Hint: Consider how many numbers
are potentially either the maximum or minimum, and investigate how a comparison
affects these counts.)

9.2 Selection in expected linear time

分治找到第几个最小值
用到的函数实现在这里

RANDOMIZED-SELECT(A; p; r; i )//i是第几个
    if p == r//p、r是左右边界，分到不能分了就返回仅有元素
        return A[p]
    q=RANDOMIZED-PARTITION(A; p; r)//q是分解的下标
    k=q-p+1
    if i = = k // the pivot value is the answer
        return A[q]
    elseif i<k
        return RANDOMIZED-SELECT(A; p; q-1; i )
    else return RANDOMIZED-SELECT(A; q C 1; r; i-k)

跳证明，以后补

9.3 Selection in worst-case linear time

1. Divide the n elements of the input array into bn=5c 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 dn=5e groups by first insertion-sorting the elements
   of each group (of which there are at most 5) and then picking the median
   from the sorted list of group elements.
3. Use SELECT recursively to find the median x of the dn=5e 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 nk
   elements on the high side of the partition.
5. If i D k, then return x. Otherwise, use SELECT recursively to find the ith
   smallest element on the low side if i the high side if i>k.

大意是说，先分成n/5组，每组五个元素（最后一组有n%5个）。然后找出每组的中位数，找出这些中位数的中位数，围绕这个中位数分数组（一边全部小于这个数，一边全部大于这个数）。递归直到找到要找的某个最小值。