select.cpp

用分治法编程求出了n个不同元素中的第k 个最小元素

#include "iostream"
#include "cstdlib"
using namespace std;


class Select
{
public:
	void swap(int i, int j)
	{
		int temp;
		temp = i;
		i = j;
		j = temp;
	}
	int partition(int a[100], int p, int r)
	{
		int i = p, j = r + 1;
		int x = a[p];
		while(true)
		{
			while(a[++i] < x && i < r);
			while(a[--j] > x);
			if (i >= j) break;
			swap(a[i], a[j]);
		}
		a[p] = a[j];
		a[j] = x;
		return j;
	}
	int random1(int p, int r)
	{
		int m = rand()%(r - p) + p;
		return m;
	}
	int randomizedpartition(int a[100], int p, int r)
	{
		int i = random1(p, r);
		swap(a[i], a[p]);
		return partition(a, p, r);
	}
	int randomizedselect(int a[100], int p, int r, int k1)
	{

		if (p == r)
			return a[p];
		int i = randomizedpartition(a,p, r);
		int j = i - p + 1;
		if (k1 <= j)
			return randomizedselect(a, p, i, k1);
		else return randomizedselect(a, i + 1, r, k1 - j);
	}
};

void main()
{
	int p, r;
	int n;
	int a[100];
	cout<<"please input the size of the array:";
	cin>>n;
//	int a[] = {10, 5, 9, 100, 7, 80, 50, 101};
	cout<<"please input the array:";
	for (int i = 0; i < n; i++)
	{
		cin>>a[i];
	}
	int k;
	cout<<"please input k = ";
	cin>>k;
	Select a1;
	p = 0;
	r = 8;
	int x = a1.randomizedselect(a, p, r - 1, k);
	cout<<x<<endl;
}