期望为线性时间选择算法

选择算法

        一般选择问题看起来要比我么找最小值这样的简单问题更难。但这两个问题的渐进运行时间却是相同的Θ(n)。RANDOMIZED_SELECT算法，以快速排序算法为模型。与快速排序不同的是，快速排序会递归处理划分的两边，而RANDOMIZED_SELECT只处理划分的一边。快速排序运行的时间是Θ(n ㏒n),而RANDOMIZED_SELECT的期望运行时间是Θ(n).

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

void exchange(int &a,int &b){
	int temp=a;
	a=b;
	b=temp;
}

int PARTITION(int *arry,int p,int r){
	int x=arry[r];  
	int i=p-1;
	for(int j=p;j<r;j++){
		if(arry[j]<x){
			i++;
			exchange(arry[i],arry[j]);
		}
	} 
	exchange(arry[i+1],arry[r]);
	return i+1;
}

int RANDOM_PARTITION(int *arry,int p,int r){
	time_t t;
  	srand((unsigned) time(&t));
	int i=rand()%(r-p)+p;
	exchange(arry[i],arry[r]);
	return PARTITION(arry,p,r);	
}


int RANDOMIZED_SELECT(int *arry,int p,int r,int i){
	if(p==r)
		return arry[p];
	int q=RANDOM_PARTITION(arry,p,r);
	int k=q-p+1; 
	
	if(i==k)
		return arry[q];
	else if (i<k)
		return RANDOMIZED_SELECT(arry,p,q-1,i);
	else
		return RANDOMIZED_SELECT(arry,q+1,r,i-k);
} 


int main(){
	int arry[12]={0,10,31,4,5,9,6,1,2,3,8,-9};
	cout<<RANDOMIZED_SELECT(arry,0,11,3)<<endl;
	return 0;	
}

RANDOMIZED_SELECT的最坏运行时间为Θ(n^2)，即使是找最小元素也是如此，因为在每次划分时可能极不走运地总是按余下的元素中最大的来划分，而划分操作需要Θ(n)，我们也将看到该算法有线性的期望运行时间，应为他是随机化的，所以不存在一个特定会导致其最坏情况发生的输入数据。
,