aptenodytesfosteri 于 2016.04.03 22:17 提问

#define MAX 8365000
#include //中位数
#include
#include

long long int randomizedselect(long long int a[],long long int left,long long int right,long long int i);
long long int randomizedpartition(long long int a[],long long int left,long long int right);
long long int partition(long long int a[],long long int left,long long int right);
int swap(long long int,long long int);

long long int a[MAX];
int main()
{
long long int n,m,m1,m2,i;

``````scanf("%lld",&n);
for (i = 1;i <= n;++i)
{
scanf("%d",&a[i]);
}

if(n%2 == 1)
m = randomizedselect(a,1,n,(n+1)/2);
else if(n%2 == 0)
{
m1 = randomizedselect(a,1,n,n/2);
m2 = randomizedselect(a,1,n,(n+2)/2);
m = (m1 + m2)/2;
}

printf("%lld",m);
``````

}

long long int randomizedselect(long long int a[],long long int left,long long int right,long long int i)
{
long long int q,k;
if(left == right)
return a[left];

``````q = partition(a,left,right);//返回是划分哨兵的最后位置
k = q-left+1;
if(i == k)
return a[q];
else if (i < k)
return randomizedselect(a,left,q-1,i);
else
return randomizedselect(a,q+1,right,i-k);
``````

}

/*long long int randomizedpartition(long long int a[],long long int left,long long int right)
{
long long int i;
srand((unsigned)time(NULL));
i = rand()%(right - left + 1)+left;//产生left和right之间的随机值
swap(right,i);

``````return partition(a,left,right);
``````

}*/

long long int partition(long long int a[],long long int left,long long int right)
{
long long int x,i,j;
x = a[right];
i = left - 1;
for (j = left;j <= right-1;++j)
{
if(a[j] <= x)
{
i++;
swap(i,j);
}
}
swap(i+1,right);
return i+1;//划分值的位置
}
int swap(long long int x,long long int y)
{
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}