#include<iostream>
#include<algorithm>
#include<time.h>
using namespace std;
int n;
int* milk;
void swap(int i,int j)
{
	int temp=milk[i];
	milk[i]=milk[j];
	milk[j]=temp;
}
int findKth(int start,int end,int k)
{
	if(start>= end)
		return milk[start];
	srand((unsigned)time(NULL));
	int index=(rand() % (end-start)) + start;
	int key=milk[index];
	swap(start,index);

	int i=start;
	int j=end;
	while(i!=j)
	{
		while(j!=i)
		{
			if(milk[j]>=key)
				j--;
			else
			{
				swap(i,j);
				break;
			}
		}
		while(i!=j)
		{
			if(milk[i]<=key)
				i++;
			else
			{
				swap(i,j);
				break;
			}
		}
	}
	if(i+1==k)
		return milk[i];
	else if(i+1 > k)
		return findKth(start,i-1,k);
	else
		return findKth(i+1,end,k);
}
int main(void)
{
	cin>>n;
	milk=new int[n];
	for(int i=0;i<n;i++)
		cin>>milk[i];
	int k=n/2+1;
	int result=findKth(0,n-1,k);
	cout<<result<<endl;
	system("pause");
	return 0;
}

• Re:O（n）的算法怎么也要32MS (1133) 1141482126 2012-12-29 15:33:52