-1

here is my version of code for median selection

#include<iostream>
using namespace std;
#define max 1000
int a[max];
int n;//number of elements
void Swap(int i,int j)
{
    int k=a[i];
    a[i]=a[j];
    a[j]=k;


}
int randint(int l, int u)
{   return l + (RAND_MAX*rand() + rand()) % (u-l+1);
}

void read()
{
    cout<<"  enter number of elements ";
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];

}

void select(int l,int u,int k)
{
    int i,j;
    int t,temp;
    if(l>=u)
         return;
    Swap(l,randint(l,u));
    t=a[l];
    i=l;
    j=u+1;
    for(;;)
    {
        do i++; while(i<=u && a[i]<t);
        do j--;while(a[j]>t);
        if(i>j)
             break;
        temp=a[i];a[i]=a[j];a[j]=temp;
    }
    Swap(i,j);
    if(j<k)
        select(j+1,u,k);
    else if(j>k)
        select(l,j-1,k);



}
int main()
{
    read();
    int l=0;
    int u=n-1;
    int k=int(n/2);
    select(l,u,k);
    if((n&1)==1)
        cout<<a[k]<<endl;
    else
        cout<<(a[k]+a[k-1])/2<<endl;


    return 0;
}

but when i run this code,i have input number of element 5 and input 

5 3 1 7 2

result is 5,i dont undertsand why it shows me 5?i think result must be 3 is not it?

4

1 回答 1

9

如果您有兴趣以最少的麻烦计算中位数，我建议使用具有线性复杂度的std::nth_element 。这是一个奇数大小向量的示例，很容易与数组一起使用，尽管我建议调整您的代码以使用std::vector：

#include <algorithm> // for std::nth_element
#include <vector> // for std::vector

std::vector<int> v = ....;
size_t midIndex = v.size()/2;
std::nth_element(v.begin(), v.begin() + midIndex, v.end());

中值为

v[midIndex];

这也可以很容易地适应于覆盖偶数阵列的情况。

于 2012-09-03T07:56:59.770 回答