#include<iostream>    //求第i个小的元素 时间复杂度O(n)

#include<cstdlib>

#include<ctime>

using namespace std;

void swap(double *dPara1, double *dPara2)

{

    double temp = 0.0;

    temp = *dPara1;

    *dPara1 = *dPara2;

    *dPara2 = temp;

}  

int randompartitionA( double dArr[], int p, int q)   //划分

{

   srand((unsigned)time(NULL));

   int account = q-p+1;

   int index = 0;

   int i = p;

   index = rand()%account+p;

   swap(dArr[p], dArr[index]);

   int x = dArr[p];

   for( int j=p+1; j<=q; j++)

   {

	   if( dArr[j]<=x )

	   {

		   i++;

		   swap(dArr[i], dArr[j]);

	   }

   }

   swap(dArr[i], dArr[p]);

   return i;

}

int randompartitionB( double dArr[], int p, int q) //划分

{

   srand((unsigned)time(NULL));

   int account = q-p+1;

   int index = 0;

   index = rand()%account+p;

   swap(dArr[p], dArr[index]);

   double x = dArr[p];

   int low = p;

   int high = q;

   while( low<high )

   {

	   while(low<high&&x<dArr[high]) --high;

	   dArr[low]=dArr[high];

	   while(low<high&&x>dArr[low]) ++low;

	   dArr[high]=dArr[low];

   }

   dArr[low] = x;

   return low;

}

double RANDOMIZED_SELECT( double dArr[], int p, int q, int i)

{

    if( p==q )

	{

		return dArr[p];

	}

	int r = randompartitionB( dArr, p, q);  // int r = randompartition( dArr, p, q);

	int k = r-p+1;

	if( i==k )

	{

		return dArr[r];

	}

	else if( i<k )

	{

		return RANDOMIZED_SELECT( dArr, p, r-1, i);

	}

	else

	{

	    return RANDOMIZED_SELECT( dArr, r+1, q, i-k);

    }

}

int main()

{

   double darr[9] = { 1.0, 2.0 ,6.3, 3.5, 8.3, 0.43, 9, 10, 2.2 };

   cout<<RANDOMIZED_SELECT( darr, 0, 8, 5);

   cout<<endl;

   return 0;

}