C数学库中的中位数函数？

Question

C数学库中的中位数函数？

c

9

C库中是否有数学函数可用于计算'n'个数字的中位数？

- Jitesh Dani

请点击此处：http://ndevilla.free.fr/median/median/index.html。 - Jonathan Feinberg

6个回答

4

要使用标准C库计算中位数，请使用标准库函数qsort()，然后取中间元素。如果数组为a，有n个元素，则：

qsort(a, n, sizeof(a[0]), compare);
return a[n/2];

您需要编写自己的compare函数，该函数将取决于数组元素的类型。有关详细信息，请参阅qsort的man页面或在Kernighan和Ritchie的索引中查找。

- Norman Ramsey

3

标准C库中没有这样的功能。

但是，您可以实现一个（或肯定在线找到代码）。一种高效的O(n)算法用于查找中位数，称为“选择算法”，与快速排序有关。在此处了解所有相关信息。

- Eli Bendersky

1

标准C库中没有中位数函数。

- Thomas Padron-McCarthy

1

那么 std::nth_element 呢？如果我正确理解中位数的性质，这将为奇数个元素提供一个中位数。

- user1552117

0

要获取中位数，您可以对数字数组进行排序并执行以下操作：

1）当项目数量为奇数时 - 取中间的数字

2）当项目数量为偶数时 - 取中间两个数字的平均值

- catwalk

2

@Eli：简单往往胜过高效，我有一种直觉，这正是OP想要的。 - catwalk

1

@catwalk：说得很好，但是在你的回答中明确指出这是简单而不是高效的解决方案是明智的。 - Eli Bendersky

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- enthusiasticgeek · Accepted Answer

传统方法：（如果你正在进行图像处理，不建议使用此方法）

/* median through qsort example */
#include <stdio.h>
#include <stdlib.h>

#define ELEMENTS 6

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, ELEMENTS, sizeof(int), compare);
  for (n=0; n<ELEMENTS; n++)
  {   printf ("%d ",values[n]); }
  printf ("median=%d ",values[ELEMENTS/2]);
  return 0;
}

然而，在不对候选数组进行排序的情况下计算中位数的最快方法有两个函数。以下方法比传统计算中位数的方式至少快600％。不幸的是，它们不是C标准库或C ++ STL的一部分。

更快的方法：

//===================== Method 1: =============================================
//Algorithm from N. Wirth’s book Algorithms + data structures = programs of 1976    

typedef int_fast16_t elem_type ;

#ifndef ELEM_SWAP(a,b)
#define ELEM_SWAP(a,b) { register elem_type t=(a);(a)=(b);(b)=t; }

elem_type kth_smallest(elem_type a[], uint16_t n, uint16_t k)
{
    uint64_t i,j,l,m ;
    elem_type x ;
    l=0 ; m=n-1 ;
    while (l<m) {
    x=a[k] ;
    i=l ;
    j=m ;
    do {
    while (a[i]<x) i++ ;
    while (x<a[j]) j-- ;
    if (i<=j) {
    ELEM_SWAP(a[i],a[j]) ;
    i++ ; j-- ;
    }
    } while (i<=j) ;
    if (j<k) l=i ;
    if (k<i) m=j ;
    }
    return a[k] ;
}

    #define wirth_median(a,n) kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1)))

//===================== Method 2: =============================================
//This is the faster median determination method.
//Algorithm from Numerical recipes in C of 1992

elem_type quick_select_median(elem_type arr[], uint16_t n)
{
    uint16_t low, high ;
    uint16_t median;
    uint16_t middle, ll, hh;
    low = 0 ; high = n-1 ; median = (low + high) / 2;
    for (;;) {
    if (high <= low) /* One element only */
    return arr[median] ;
    if (high == low + 1) { /* Two elements only */
    if (arr[low] > arr[high])
    ELEM_SWAP(arr[low], arr[high]) ;
    return arr[median] ;
    }
    /* Find median of low, middle and high items; swap into position low */
    middle = (low + high) / 2;
    if (arr[middle] > arr[high])
    ELEM_SWAP(arr[middle], arr[high]) ;
    if (arr[low] > arr[high])
    ELEM_SWAP(arr[low], arr[high]) ;
    if (arr[middle] > arr[low])
    ELEM_SWAP(arr[middle], arr[low]) ;
    /* Swap low item (now in position middle) into position (low+1) */
    ELEM_SWAP(arr[middle], arr[low+1]) ;
    /* Nibble from each end towards middle, swapping items when stuck */
    ll = low + 1;
    hh = high;
    for (;;) {
    do ll++; while (arr[low] > arr[ll]) ;
    do hh--; while (arr[hh] > arr[low]) ;
    if (hh < ll)
    break;
    ELEM_SWAP(arr[ll], arr[hh]) ;
    }
    /* Swap middle item (in position low) back into correct position */
    ELEM_SWAP(arr[low], arr[hh]) ;
    /* Re-set active partition */
    if (hh <= median)
    low = ll;
    if (hh >= median)
    high = hh - 1;
    }
    return arr[median] ;
}
#endif

在C++中，我创建了这些模板函数，如果对于这样的函数数字是以单一方向递增或递减的，则使用 int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; 而不是常规的[stdint.h]类型（例如uint16_t; uint32_t等）。