随机选择（求中位数，第i 小的元素)

问题定义：

输入：输入一个由n个元素构成的集合a和一个数值i，且1<= i <= n。

输出：一个元素x属于a，它比前面i-1个元素都大，也就是第i个最小的元素。

特列：寻找中位数问题。

随机选择的时间复制度为O(n)。

代码如下：

/*
 *Copyright(c) Computer Science Department of XiaMen University 
 *
 *Authored by laimingxing on: 2012年 03月 02日 星期五 00:47:43 CST
 *
 * @desc:
 *
 * @history
 */
#include <iostream>
#include <stdlib.h>
using namespace std;
const int n = 15; 

void swap( int *data, int i, int j);
int RandomizedSelect( int *data, int l, int u, int index);

int main(int argc, char* argv[])
{
	int data[n];
	int i = 0;
	for( i = 0; i < n; i++)
		data[i] = rand() % (n * 10);

	cout << "Data set: " << endl;
	for( i = 0; i < n; i++)
		cout << data[i] << "\t";	
	cout << endl;

	//Select a number which is ith small in data set.
	int temp = RandomizedSelect(data, 0, n - 1, 5);
	cout << temp << endl;


	return 0;
}

void swap( int *data, int i, int j)
{
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

int RandomizedSelect( int *data, int l, int u, int index)
{
	if( l ==  u ) return data[l];

	int i = l, j = u + 1;
	// Randomize
	swap( data, l, rand() % (u - l)+l );
	int temp = data[l];

	while( true )
	{
		do i++; while( i <= u && data[i] < temp );
		do j--; while( data[j] > temp );

		if( i > j ) break;

		//exchange data[i], data[j]
		// for efficienty , don't use swap function`
		int t = data[i]; data[i] = data[j]; data[j] = t;
	}

	swap( data, l, j);
	int k = j - l + 1;
	if( index == k )
		return data[j];
	else if ( index < k )
		RandomizedSelect( data, l, j - 1, index );
	else
		RandomizedSelect( data, j + 1, u, index - k);
}