#include <iostream>

using namespace std;

int Partition(int *num, int start, int end);
void QSort(int *num, int start, int end);

int main()
{
	int N;
	cin >> N;
	int *num = new int[N + 1];
	for(int i = 1; i != N + 1; ++i)
		cin >> num[i];
	int pos = Partition(num, 1, N);
	int target = N / 2 + 1;
	int start = 1, end = N;
	while(pos != target)
	{
		if(start <= target && target <= pos - 1)
		{
			end = pos - 1;
			pos = Partition(num, start, end);
		}
		else
		{
			start = pos + 1;
			pos = Partition(num, start, end);
		}
	}
	cout << num[target];
	return 0;
}

void QSort(int *num, int start, int end)
{
	if(start < end)
	{
		int middle = Partition(num, start, end);
		QSort(num, start, middle - 1);
		QSort(num, middle + 1, end);
	}
}

int Partition(int *num, int start, int end)
{
	int r = num[end];
	int i = start - 1;
	int temp;
	int j;
	for(j = start; j != end; ++j)
	{
		if(num[j] <= r)
		{
			temp = num[++i];
			num[i] = num[j];
			num[j] = temp;
		}
	}
	temp = num[++i];
	num[i] = num[j];
	num[j] = temp;
	return i;
}

• Re:快排AC的,做了点改进,不过除了代码长度长了,运行时间内存都一样,郁闷中!!! (11) y09rong 2010-08-10 09:29:14