C数学库中的中值函数？

Question

C库中是否有计算'n'数字MEDIAN的数学函数？

Answer 1

获得中位数就可以数的数组进行排序，并采取：

的情况下，1）当项目的数量为奇数 - 万一中间

2）的数量时，项目数是偶数 - 中间两个数字的平均值

Answer 2

Here you go。

Answer 3

不，标准C库中没有中值函数。

Answer 4

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

但是，您可以实现一个（或确实在线查找代码）。用于查找中位数的高效O（n）算法被称为“选择算法”，并且与快速排序有关。详细了解它here。

Answer 5

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

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

你必须写自己的compare功能，这将依赖于数组元素的类型。有关详细信息，请参阅手册页qsort或在Kernighan和Ritchie的索引中查找。

Answer 6

常规方法：（不推荐，如果您正在使用的图像处理）

/* 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等）

Answer 7

std::nth_element？如果我正确地理解中位数的性质，这会给你一个奇数的元素。