#include "stdafx.h"
#include<iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

#define SB -1

int RANDOM(int p, int r)
{
	srand((unsigned)time(NULL));
	return (rand() % (r - p + 1)) + p;
}

int partition(int a[], int p, int r) {
	int x, i, t;
	x = a[r];
	i = p - 1;
	t = 0;
	for (int j = p; j <= r - 1; j++)
	{
		if (a[j]< x)
		{
			i = i + 1;
			int ti;
			ti = a[i];
			a[i] = a[j];
			a[j] = ti;
		}
		if (a[j] == x)
		{
			t = t + 1;
			int ti;
			ti = a[i + t];
			a[i + t] = a[j];
			a[j] = ti;
		}
	}
	int tii;
	tii = a[i + t + 1];
	a[i + 1 + t] = a[r];
	a[r] = tii;
	if (i == r - 1)return (p + r) / 2;
	else
		return i + 1;
}

int random_partion(int a[], int p, int r)
{

	int i = RANDOM(p, r);
	int tii;
	tii = a[i];
	a[i] = a[r];
	a[r] = tii;
	return partition(a, p, r);
}

/*int random_select(int a[], int p, int r, int i)  //随机选择算法递归实现
{
	if (p == r)
		return a[p];
	int q;
	q = random_partion(a, p, r);
	int k = q - p + 1;
	if (i == k)
		return a[q];
	else if (i < k)
		return random_select(a, p, q - 1, i);
	else
		return random_select(a, q+1, r, i-k);
}*/

int random_select2(int a[], int p, int r, int i)  //随机选择算法循环实现
{
	if (p == r)
		return a[p];
	int q;
	int head = p, end = r;
	q = random_partion(a, head, end);
	int k = end - head + 1;
	while (i != k) {
		if (i < k) {
			end = q - 1;
			q = random_partion(a, head, end);
			k = q - head + 1;
		}
		else {
			head = q + 1;
			q = random_partion(a, head, end);
			k = q - head + 1;
			i = i - head + 1;
		}
	}
	return a[q];
}

int main()
{
	int a[] = { SB ,3 ,2 ,4 ,5 ,6 };   //SB为哨兵，不包括在选择项
	cout << random_select2(a, 1, 5, 2);
	while (1);
    return 0;
}