查找中位数而不排序数组

Question

我希望实现一个非常简单的函数，通过计算较小元素的数量和较大元素的数量，如果它们的数量相等，那么找到未排序数组的中值，然后将原始数据视为中位数。

我知道几种算法，如minHeap和Quick Select，但我试图保持简单，就像人类用肉眼做的那样简单地计算更大和更小的数字。到目前为止，我已经实现了下面的功能，但是当我在数组中有重复的条目以及偶数和奇数数组长度时出现问题。

我是C编程的新手，需要了解出了什么问题。下面是代码，我编写了一个函数来返回可变长度的随机数组来测试这个函数。

int med(int count, int *array)
{
int i, j, median = -1, smaller = 0, larger = 0;

for(i = 0; i < count; i++)
{
    for(j = 0; j < count; j++)
    {
        //larger++

        if(array[i] < array[j] && i!=j)
        {
            larger++;
        }
        //Smaller++
        if(array[i] >= array[j] && i!=j)
        {
            smaller++;
        }
    }
    printf("\nFor pivot: %d", array[i]);
    if(larger == smaller)
    {
        printf("\n Smaller: %d", smaller);
        printf(" Larger: %d", larger);
        median = array[i];
        break;
    }
    else
    {
        printf("\n Smaller: %d", smaller);
        printf(" Larger: %d", larger);

        larger = 0;
        smaller = 0;
    }
}
return median;
}

在某些情况下，如{3,5,0,2,3}我的函数返回-1，但实际结果应为3。

编辑最初我开始严格更大或更小，但这个条件（更大==更小）永远不会被重击，因此我认为相等的元素更小。我在处理平等问题时遇到了困难

Answer 1

B. Shefter为你找到了这个bug。但是，我仍然想解决这个问题。

我希望实现一个非常简单的函数，通过计算较小元素的数量和较大元素的数量，如果它们的数量相等，那么找到未排序数组的中值，然后将原始数据视为中位数。

只有这样做，如果你能比O（nlog n）更快，因为那是qsort的时间复杂度。我建议尝试中位数算法的中位数。你可以阅读它here，这里是该网站的代码，但删除了注释：

int select(int *a, int s, int e, int k){
    if(e-s+1 <= 5){
        sort(a+s, a+e);
        return s+k-1;
    }

    for(int i=0; i<(e+1)/5; i++){
        int left = 5*i;
        int right = left + 4;
        if(right > e) right = e;
        int median = select(a, 5*i, 5*i+4, 3);
        swap(a[median], a[i]);
    }

    return select(a, 0, (e+1)/5, (e+1)/10);
}

我知道几种算法，比如使用minHeap和Quick Select，但我试图保持简单，就像人类用肉眼做的那样简单地计算更大和更小的数字。

虽然保持简单是件好事，但要确保这就是你的所作所为。 C标准库具有内置的快速排序。如果您使用那个，代码可能如下所示：

int int_cmp(const void *a, const void *b) 
{ 
    const int ia = *(const int *)a; 
    const int ib = *(const int *)b;

    if (ia > ib) return 1;
    else if(ia < ib) return -1;
    else return 0;
}

int med(int count, int *array)
{
    int tmp[count];

    memcpy(tmp, array, count * sizeof(*array));

    qsort(tmp, count, sizeof(tmp[0]), int_cmp);

    return tmp[count/2];
}

它更快更容易阅读。您的代码是O（n²），而这是O（nlog n）。

您在评论中提到要将其用于新的排序方法。然后我想提一下，具有奇数个元素的集合的中位数通常不是集合的成员，因此您需要更改中位数的定义以满足您的需要。

下面是一个示例，说明如何以一种可读的方式实现您想要的，同时仍然保持您的想法。我首先添加一个子问题，而不是“数组中的中位数”是“x是数组的中位数”。然后我们在数组中的每个元素问这个问题，直到我们找到中位数。

int is_median(int x, int *array, int count) {
    int l=0, h=0;

    for(int i=0; i<count; i++) {
        if(array[i] < x) l++;
        else if(array[i] > x) h++;
    }

    if(h == l) return 1; // This is always a sufficient condition
    // Here you need to decide what to do. Just the above is not enough
    // for your purposes.
    else if(<condition>) return 1; 

    else return 0;
}

int med(int count, int *array) {
    for(int i = 0; i < count; i++) {
        if(is_median(array[i], array, count)) return array[i];
    }
    return 0; // This line should never be executed. It't only here
              // to suppress a warning.
}

Answer 2

-1来自以下：您的代码将median初始化为-1，除非larger == smaller，否则它永远不会改变。如果在遍历整个数组之后从未发生过，则代码返回-1。

我认为概念上的错误是你在两个数字相等时任意决定增加smaller。如果你浏览你的代码，你就会明白为什么你在你展示的例子中得到-1：你最终得到larger=1（5）和smaller=3（0,2和3）。因此，由于larger不等于smaller，median不会设置为3并保持-1。

那就是出了什么问题。如何处理修正概念错误的平等权取决于你！