中位数在Java中位数 [英] Median of Medians in Java

问题描述

我想实现中位数在Java中的中位数的方法是这样的：

I am trying to implement Median of Medians in Java for a method like this:

Select(Comparable[] list, int pos, int colSize, int colMed)

• 列表是值的列表，以找到一个指定的位置
• POS 在指定的位置
• colSize 是我在第一阶段创建列的尺寸
• colMed 是那些我用的MEDX
列的位置
• list is a list of values of which to find a specified position
• pos is the specified position
• colSize is the size of the columns that I create in the first stage
• colMed is the position in those columns that I use as the medX

我不知道它的排序算法将是最好的使用或如何实现这种完全..

I am not sure which sorting algorithm would be the best to use or how to implement this exactly..

推荐答案

我不知道你是否还需要这个问题解决了，但<一个href="http://www.ics.uci.edu/~eppstein/161/960130.html">http://www.ics.uci.edu/~eppstein/161/960130.html有一个算法：

I don't know if you still need this problem solved, but http://www.ics.uci.edu/~eppstein/161/960130.html has an algorithm:

select(L,k)
{
    if (L has 10 or fewer elements)
    {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    partition L into L1<M, L2=M, L3>M
    if (k <= length(L1))
        return select(L1,k)
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))
    else return M
}

祝你好运！

这篇关于中位数在Java中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！