线性时间选择.cpp

来自「常见算法」· C++ 代码 · 共 49 行

#include<iostream>
#include<math.h>
using std::cout;
using std::cin;
using std::endl;
#define N 10
//用快速排序法随机化版本将数组分成两组，一直分到第i小的元素，输出这个元素



//快速排序随机化版本

	
	int rand_partition(int a[],int p,int r)
	{
		int key,x;                                        //x是划分值                                       //
		x=a[p+rand()/(r-p+1)];          
		while (p<r)
		{
			while(a[r]>x)
				r--;
			while(a[p]<x)
			{
				p++;
			}
			if(p<r)
			{
				key=a[p];
				a[p]=a[r];
				a[r]=key;
			}
		}
		return r;
	}
int randomized_select(int a[N],int start,int end,int i)
{
	int q,k;
	if(start==end)
		return a[end];
    q=rand_partition(a,start,end);
	k=end-q+1;
    
    
}