在一堆未排序的的数组中找第x大数

 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void exchange(int *pArray, int l, int r)

{

int tmp;

tmp=pArray[l];

pArray[l] = pArray[r];

pArray[r]=tmp;

}

int position(int *pArray, int p, int r)

{

int x = pArray[r];

int j = p;

int i = j -1;

for(; j < r; j++)

{

if(pArray[j] <= x)

{

i++;

exchange(pArray, i, j);

}

}

exchange(pArray, i+1, r);

return i+1;

 

}

int  randomized_position(int *pArray, int p, int r)

{

if(p < r) 

{

srand(time(0));

int k = rand()%(r-p);

exchange(pArray, p+k, r);

int iter = position(pArray, p, r);

return iter;

}

else

{

return 0;

}

}

int randomized_select(int *pArray, int p, int r, int i)

{

if(p == r)

{

return pArray[p];

}

int k = position(pArray, p, r);

int q = k - p +1;

if(q == i)

{

return pArray[k];

}

if(q < i)

{

randomized_select(pArray,k+1,r,i-k);

}

else

{

randomized_select(pArray, p, k-1, i);

}

}